{"thread":{"id":"66754","subject":"Strange word diff","startedAt":"2026-11-03T14:14:14Z","lastAt":"2026-11-03T16:38:03Z","messageCount":2,"participants":["Jean Abou Samra","Phillip Wood"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"557319","messageId":"4dd76eef8a2a355ba435e8c784c1e37f3fe47074.camel@abou-samra.fr","threadId":"66754","inReplyTo":null,"subject":"Strange word diff","fromName":"Jean Abou Samra","fromEmail":"jean@abou-samra.fr","sentAt":"2026-11-03T14:14:14Z","receivedAt":"2026-11-03T14:14:14Z","isPatch":false,"sender":{"key":"jean@abou-samra.fr","avatar":null},"body":"Hi,\n\nAttached is an archive with three files. file2.txt differs from file1.txt\nby just a few words, as correctly reported by git diff --word-diff (using\nGit 2.56.0):\n\n```\n$ git diff --no-index --word-diff file1.txt file2.txt \ndiff --git a/file1.txt b/file2.txt\nindex a9eaedc..a75008e 100644\n--- a/file1.txt\n+++ b/file2.txt\n@@ -1,4 +1,4 @@\n\\subparagraph*{Context}\nOur object of study is an extension of Turing degrees where the oracles can\nfeature certain forms of non-determinism, as in this riddle. We call these\ngeneralized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\nexplicit description by Kihara using a three-player game whose players are\nconventionally named Arthur, Nimue and\nMerlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n“extended Turing–Weihrauch degrees”. We prefer to eschew the association with\nWeihrauch's name since we never deal with [-call-once oracles.}-]{+oracles that\ncan only be queried once.}+} Whereas Turing degrees are defined as a quotient of\noracles which are functions $\\N \\to \\N$, Arthur–Nimue–Merlin degrees are a\nquotient of a richer set of oracles, namely functions $\\N \\to \\P(\\P(\\N))$.\nInformally, when a program that uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes\na query $n \\in \\N$ to the oracle, a set $P \\in g(n)$ is chosen in a benevolent\nway (“angelic non-determinism”), then a value $v \\in P$ is chosen in an\nadversarial way (“demonic non-determinism”), and the program receives the answer\n$v$. The mathematical meaning to “benevolent” and “adversarial” is made precise\nby introducing a game where Arthur, a player restricted to computable\nstrategies, is allied to Nimue, the player choosing $P$, and both play against\nMerlin, the player choosing $v$. (The details of the game are recalled in\n\\autoref{section-arthur-nimue-merlin-games}.)\n\nWhile [-this game was-]{+Arthur–Nimue–Merlin games were+} introduced recently by\nKihara, [-the concept-]{+they are a concrete description+} of [-\nArthur–Nimue–Merlin degrees is-]{+objects that arose+} much [-older, having\narised,-]{+earlier,+} in a different guise, in the study of realizability. To\nreassure the reader unfamiliar with realizability from the outset, this paper is\nmeant to be accessible with only a background in basic computability theory,\nexcept for \\autoref{section-topos-theory} where we explain how the proof of our\nmain result can be understood from the point of view of realizability.\nNevertheless, let us recall the historical link.\n```\n\nThe only change between file2.txt and file3.txt is the addition of a\nblank line:\n\n```\n$ git diff --no-index file2.txt file3.txt \ndiff --git a/file2.txt b/file3.txt\nindex a75008e..81c3eb9 100644\n--- a/file2.txt\n+++ b/file3.txt\n@@ -1,4 +1,5 @@\n \\subparagraph*{Context}\n+\n Our object of study is an extension of Turing degrees where the oracles can\nfeature certain forms of non-determinism, as in this riddle. We call these\ngeneralized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\nexplicit description by Kihara using a three-player game whose players are\nconventionally named Arthur, Nimue and\nMerlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n“extended Turing–Weihrauch degrees”. We prefer to eschew the association with\nWeihrauch's name since we never deal with oracles that can only be queried\nonce.} Whereas Turing degrees are defined as a quotient of oracles which are\nfunctions $\\N \\to \\N$, Arthur–Nimue–Merlin degrees are a quotient of a richer\nset of oracles, namely functions $\\N \\to \\P(\\P(\\N))$. Informally, when a program\nthat uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes a query $n \\in \\N$ to the\noracle, a set $P \\in g(n)$ is chosen in a benevolent way (“angelic non-\ndeterminism”), then a value $v \\in P$ is chosen in an adversarial way (“demonic\nnon-determinism”), and the program receives the answer $v$. The mathematical\nmeaning to “benevolent” and “adversarial” is made precise by introducing a game\nwhere Arthur, a player restricted to computable strategies, is allied to Nimue,\nthe player choosing $P$, and both play against Merlin, the player choosing $v$.\n(The details of the game are recalled in \\autoref{section-arthur-nimue-merlin-\ngames}.)\n \n While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a\nconcrete description of objects that arose much earlier, in a different guise,\nin the study of realizability. To reassure the reader unfamiliar with\nrealizability from the outset, this paper is meant to be accessible with only a\nbackground in basic computability theory, except for \\autoref{section-topos-\ntheory} where we explain how the proof of our main result can be understood from\nthe point of view of realizability. Nevertheless, let us recall the historical\nlink.\n```\n\nAnd yet, comparing file1.txt with file3.txt with a word diff gives a strange\ndiff that matches a few words here and there while missing unchanged entire\nlong sentences:\n\n```\n$ git diff --no-index --word-diff file1.txt file3.txt \ndiff --git a/file1.txt b/file3.txt\nindex a9eaedc..81c3eb9 100644\n--- a/file1.txt\n+++ b/file3.txt\n@@ -1,4 +1,5 @@\n\\subparagraph*{Context}\n[-Our object of study is an extension of Turing degrees where the oracles can\nfeature certain forms of non-determinism, as in this riddle. We call these\ngeneralized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\nexplicit description by Kihara using a three-player game whose players are\nconventionally named Arthur, Nimue and\nMerlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n“extended Turing–Weihrauch degrees”. We prefer to eschew the association with\nWeihrauch's name since we never deal with call-once oracles.} Whereas Turing\ndegrees are defined as a quotient of oracles which are functions $\\N \\to \\N$,\nArthur–Nimue–Merlin degrees are a quotient of a richer set of oracles, namely\nfunctions $\\N \\to \\P(\\P(\\N))$. Informally, when a program that uses $g : \\N \\to\n\\P(\\P(\\N))$ as an oracle makes a query $n \\in \\N$ to the oracle, a set $P \\in\ng(n)$ is chosen in a benevolent way (“angelic non-determinism”), then a value $v\n\\in P$ is chosen in an adversarial way (“demonic non-determinism”), and the\nprogram receives the answer $v$. The mathematical meaning to “benevolent” and\n“adversarial” is made precise by introducing a game where Arthur, a player\nrestricted to computable strategies, is allied to Nimue, the player choosing\n$P$, and both play against Merlin, the player choosing $v$. (The details of the\ngame are recalled in \\autoref{section-arthur-nimue-merlin-games}.)-]\n\n[-While-]{+Our object of study is an extension of Turing degrees where the\noracles can feature certain forms of non-determinism, as in+} this [-game was\nintroduced recently-]{+riddle. We call these generalized degrees the\n\\emph{Arthur–Nimue–Merlin degrees}, owing to their explicit description+} by [-\nKihara,-]{+Kihara using a three-player game whose players are conventionally\nnamed Arthur, Nimue and\nMerlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses+} the [-\nconcept-]{+term “extended Turing–Weihrauch degrees”. We prefer to eschew the\nassociation with Weihrauch's name since we never deal with oracles that can only\nbe queried once.} Whereas Turing degrees are defined as a quotient+} of\n{+oracles which are functions $\\N \\to \\N$,+} Arthur–Nimue–Merlin degrees {+are a\nquotient of a richer set of oracles, namely functions $\\N \\to \\P(\\P(\\N))$.\nInformally, when a program that uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes\na query $n \\in \\N$ to the oracle, a set $P \\in g(n)$ is chosen in a benevolent\nway (“angelic non-determinism”), then a value $v \\in P$ is chosen in an\nadversarial way (“demonic non-determinism”), and the program receives the answer\n$v$. The mathematical meaning to “benevolent” and “adversarial”+} is {+made\nprecise by introducing a game where Arthur, a player restricted to computable\nstrategies, is allied to Nimue, the player choosing $P$, and both play against\nMerlin, the player choosing $v$. (The details of the game are recalled in\n\\autoref{section-arthur-nimue-merlin-games}.)+}\n\n{+While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a\nconcrete description of objects that arose+} much [-older, having arised,-\n]{+earlier,+} in a different guise, in the study of realizability. To reassure\nthe reader unfamiliar with realizability from the outset, this paper is meant to\nbe accessible with only a background in basic computability theory, except for\n\\autoref{section-topos-theory} where we explain how the proof of our main result\ncan be understood from the point of view of realizability. Nevertheless, let us\nrecall the historical link.\n```\n\nIs this a bug? It happens with all --diff-algorithm option values.\n\nBest,\nJean\n"},{"id":"557334","messageId":"9fb1cf95-1cfb-4bc9-a722-e98d0a0664df@gmail.com","threadId":"66754","inReplyTo":"4dd76eef8a2a355ba435e8c784c1e37f3fe47074.camel@abou-samra.fr","subject":"Re: Strange word diff","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-11-03T16:38:03Z","receivedAt":"2026-11-03T16:38:03Z","isPatch":false,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Jean\n\nOn 03/11/2026 14:14, Jean Abou Samra wrote:\n> Hi,\n> > Attached is an archive with three files. file2.txt differs from file1.txt\n> by just a few words, as correctly reported by git diff --word-diff (using\n> Git 2.56.0):\n> > Is this a bug? It happens with all --diff-algorithm option values.\n\nYes and No! I think the diff is correct, but it is also pretty useless if one is interested in seeing the word-level changes. The problem is due to the way git calculates word diffs. To calculate the word diff, git first calculates the line by line diff which looks like\n\ndiff --git a/file1.txt b/file3.txt\nindex a9eaedc..81c3eb9 100644\n--- a/file1.txt\n+++ b/file3.txt\n@@ -1,4 +1,5 @@\n \\subparagraph*{Context}\n-Our object of study is an extension of Turing degrees ...\n\n-While this game was introduced recently by Kihara\n+Our object of study is an extension of Turing degrees ...\n+\n+While Arthur–Nimue–Merlin games were introduced recently by Kihara...\n\nthen, it splits the line diff whenever it sees a context line and diffs the words in the '-' and '+' lines it has seen up to that point. As git has chosen the first blank line as a context line, it looks like the entire first paragraph has been deleted which messes up the word diff. We had a similar report a few months ago. I think the solution is to feed whole hunks from the line diff into the word diff instead of splitting the hunk when we see a context line.\n\nAs an aside my local git installation uses a modified implementation of the patience algorithm that removes the fallback to the Myers diff when it cannot find any context lines[1]. That algorithm cannot find any context lines in this example and so gives a sensible word-diff.\n\nThanks\n\nPhillip\n\n[1] https://github.com/phillipwood/git/commit/7eda9d836c8db76ad49b6cc8b5760ff458d81e9c\n\n> ```\n> $ git diff --no-index --word-diff file1.txt file2.txt\n> diff --git a/file1.txt b/file2.txt\n> index a9eaedc..a75008e 100644\n> --- a/file1.txt\n> +++ b/file2.txt\n> @@ -1,4 +1,4 @@\n> \\subparagraph*{Context}\n> Our object of study is an extension of Turing degrees where the oracles can\n> feature certain forms of non-determinism, as in this riddle. We call these\n> generalized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\n> explicit description by Kihara using a three-player game whose players are\n> conventionally named Arthur, Nimue and\n> Merlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n> “extended Turing–Weihrauch degrees”. We prefer to eschew the association with\n> Weihrauch's name since we never deal with [-call-once oracles.}-]{+oracles that\n> can only be queried once.}+} Whereas Turing degrees are defined as a quotient of\n> oracles which are functions $\\N \\to \\N$, Arthur–Nimue–Merlin degrees are a\n> quotient of a richer set of oracles, namely functions $\\N \\to \\P(\\P(\\N))$.\n> Informally, when a program that uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes\n> a query $n \\in \\N$ to the oracle, a set $P \\in g(n)$ is chosen in a benevolent\n> way (“angelic non-determinism”), then a value $v \\in P$ is chosen in an\n> adversarial way (“demonic non-determinism”), and the program receives the answer\n> $v$. The mathematical meaning to “benevolent” and “adversarial” is made precise\n> by introducing a game where Arthur, a player restricted to computable\n> strategies, is allied to Nimue, the player choosing $P$, and both play against\n> Merlin, the player choosing $v$. (The details of the game are recalled in\n> \\autoref{section-arthur-nimue-merlin-games}.)\n> > While [-this game was-]{+Arthur–Nimue–Merlin games were+} introduced recently by\n> Kihara, [-the concept-]{+they are a concrete description+} of [-\n> Arthur–Nimue–Merlin degrees is-]{+objects that arose+} much [-older, having\n> arised,-]{+earlier,+} in a different guise, in the study of realizability. To\n> reassure the reader unfamiliar with realizability from the outset, this paper is\n> meant to be accessible with only a background in basic computability theory,\n> except for \\autoref{section-topos-theory} where we explain how the proof of our\n> main result can be understood from the point of view of realizability.\n> Nevertheless, let us recall the historical link.\n> ```\n> > The only change between file2.txt and file3.txt is the addition of a\n> blank line:\n> > ```\n> $ git diff --no-index file2.txt file3.txt\n> diff --git a/file2.txt b/file3.txt\n> index a75008e..81c3eb9 100644\n> --- a/file2.txt\n> +++ b/file3.txt\n> @@ -1,4 +1,5 @@\n>   \\subparagraph*{Context}\n> +\n>   Our object of study is an extension of Turing degrees where the oracles can\n> feature certain forms of non-determinism, as in this riddle. We call these\n> generalized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\n> explicit description by Kihara using a three-player game whose players are\n> conventionally named Arthur, Nimue and\n> Merlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n> “extended Turing–Weihrauch degrees”. We prefer to eschew the association with\n> Weihrauch's name since we never deal with oracles that can only be queried\n> once.} Whereas Turing degrees are defined as a quotient of oracles which are\n> functions $\\N \\to \\N$, Arthur–Nimue–Merlin degrees are a quotient of a richer\n> set of oracles, namely functions $\\N \\to \\P(\\P(\\N))$. Informally, when a program\n> that uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes a query $n \\in \\N$ to the\n> oracle, a set $P \\in g(n)$ is chosen in a benevolent way (“angelic non-\n> determinism”), then a value $v \\in P$ is chosen in an adversarial way (“demonic\n> non-determinism”), and the program receives the answer $v$. The mathematical\n> meaning to “benevolent” and “adversarial” is made precise by introducing a game\n> where Arthur, a player restricted to computable strategies, is allied to Nimue,\n> the player choosing $P$, and both play against Merlin, the player choosing $v$.\n> (The details of the game are recalled in \\autoref{section-arthur-nimue-merlin-\n> games}.)\n>   >   While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a\n> concrete description of objects that arose much earlier, in a different guise,\n> in the study of realizability. To reassure the reader unfamiliar with\n> realizability from the outset, this paper is meant to be accessible with only a\n> background in basic computability theory, except for \\autoref{section-topos-\n> theory} where we explain how the proof of our main result can be understood from\n> the point of view of realizability. Nevertheless, let us recall the historical\n> link.\n> ```\n> > And yet, comparing file1.txt with file3.txt with a word diff gives a strange\n> diff that matches a few words here and there while missing unchanged entire\n> long sentences:\n> > ```\n> $ git diff --no-index --word-diff file1.txt file3.txt\n> diff --git a/file1.txt b/file3.txt\n> index a9eaedc..81c3eb9 100644\n> --- a/file1.txt\n> +++ b/file3.txt\n> @@ -1,4 +1,5 @@\n> \\subparagraph*{Context}\n> [-Our object of study is an extension of Turing degrees where the oracles can\n> feature certain forms of non-determinism, as in this riddle. We call these\n> generalized degrees the \\emph{Arthur–Nimue–Merlin degrees}, owing to their\n> explicit description by Kihara using a three-player game whose players are\n> conventionally named Arthur, Nimue and\n> Merlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses the term\n> “extended Turing–Weihrauch degrees”. We prefer to eschew the association with\n> Weihrauch's name since we never deal with call-once oracles.} Whereas Turing\n> degrees are defined as a quotient of oracles which are functions $\\N \\to \\N$,\n> Arthur–Nimue–Merlin degrees are a quotient of a richer set of oracles, namely\n> functions $\\N \\to \\P(\\P(\\N))$. Informally, when a program that uses $g : \\N \\to\n> \\P(\\P(\\N))$ as an oracle makes a query $n \\in \\N$ to the oracle, a set $P \\in\n> g(n)$ is chosen in a benevolent way (“angelic non-determinism”), then a value $v\n> \\in P$ is chosen in an adversarial way (“demonic non-determinism”), and the\n> program receives the answer $v$. The mathematical meaning to “benevolent” and\n> “adversarial” is made precise by introducing a game where Arthur, a player\n> restricted to computable strategies, is allied to Nimue, the player choosing\n> $P$, and both play against Merlin, the player choosing $v$. (The details of the\n> game are recalled in \\autoref{section-arthur-nimue-merlin-games}.)-]\n> > [-While-]{+Our object of study is an extension of Turing degrees where the\n> oracles can feature certain forms of non-determinism, as in+} this [-game was\n> introduced recently-]{+riddle. We call these generalized degrees the\n> \\emph{Arthur–Nimue–Merlin degrees}, owing to their explicit description+} by [-\n> Kihara,-]{+Kihara using a three-player game whose players are conventionally\n> named Arthur, Nimue and\n> Merlin \\cite{KiharaLT}.\\footnote{In \\cite{KiharaOracles}, Kihara uses+} the [-\n> concept-]{+term “extended Turing–Weihrauch degrees”. We prefer to eschew the\n> association with Weihrauch's name since we never deal with oracles that can only\n> be queried once.} Whereas Turing degrees are defined as a quotient+} of\n> {+oracles which are functions $\\N \\to \\N$,+} Arthur–Nimue–Merlin degrees {+are a\n> quotient of a richer set of oracles, namely functions $\\N \\to \\P(\\P(\\N))$.\n> Informally, when a program that uses $g : \\N \\to \\P(\\P(\\N))$ as an oracle makes\n> a query $n \\in \\N$ to the oracle, a set $P \\in g(n)$ is chosen in a benevolent\n> way (“angelic non-determinism”), then a value $v \\in P$ is chosen in an\n> adversarial way (“demonic non-determinism”), and the program receives the answer\n> $v$. The mathematical meaning to “benevolent” and “adversarial”+} is {+made\n> precise by introducing a game where Arthur, a player restricted to computable\n> strategies, is allied to Nimue, the player choosing $P$, and both play against\n> Merlin, the player choosing $v$. (The details of the game are recalled in\n> \\autoref{section-arthur-nimue-merlin-games}.)+}\n> > {+While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a\n> concrete description of objects that arose+} much [-older, having arised,-\n> ]{+earlier,+} in a different guise, in the study of realizability. To reassure\n> the reader unfamiliar with realizability from the outset, this paper is meant to\n> be accessible with only a background in basic computability theory, except for\n> \\autoref{section-topos-theory} where we explain how the proof of our main result\n> can be understood from the point of view of realizability. Nevertheless, let us\n> recall the historical link.\n> ```\n> > > Best,\n> Jean\n\n\n"}]}