95
$\begingroup$

Consider the following Turing machine $M$: it searches over valid ZFC proofs, in lexicographic order, and if it finds a proof that $M$ halts, then it halts.

If we fix a particular model of Turing machine (say single-tape Turing machine), and if we fix an algorithm to verify that a given string is a valid ZFC proof of the fact that $M$ halts, this should constitute an unambiguous description of a Turing machine $M$.

(Standard arguments in computability theory, i.e., Kleene's recursion theorem, allows $M$ to compute functions of its own description).

Does $M$ halt?

I find this question puzzling because there's no apparent logical contradiction either way. There could be a proof, in which case it will halt. If there is no proof, then it doesn't halt. What would the answer "depend" on? $M$ either halts or doesn't halt, but could its behavior be independent of ZFC?

I should note that a closely related Turing machine $M'$ can be used to give a simple proof of Godel's incompleteness theorem. It's much more "rebellious" in its behavior, where if it finds a proof that it halts, it doesn't halt, and if it finds a proof that it doesn't halt, it halts. It follows that there cannot be a proof of its halting or non-halting in ZFC (unless ZFC is inconsistent).

However $M$ is just earnestly trying to figure out its fate. Which is it?

Improve this question
$\endgroup$
6
  • 14
    $\begingroup$ I'm not sure you have really described $M$ unambiguously. Doesn't it have to "know how it is coded"? $\endgroup$
    – Sam Hopkins
    Commented Aug 4, 2022 at 0:04
  • 5
    $\begingroup$ @SamHopkins It seems at least to me to be unambiguous, since it is clear that there exists at least one $M$ that meets the informal description of enumerating and checking ZFC proofs, and Kleene's recursion theorem guarantees that it can encode the statement "M halts" in ZFC language $\endgroup$
    – Joe Bebel
    Commented Aug 4, 2022 at 0:12
  • 3
    $\begingroup$ This is a hilariously interesting question! :) :) $\endgroup$
    – paul garrett
    Commented Aug 4, 2022 at 2:18
  • 5
    $\begingroup$ @SamHopkins Here's a simple way to construct $M$. As it stands, $M$ is a zero-input program. Define $M_1$ to be a 1-input program, with the following behavior: if the input is $P$, then $M_1(P)$ interprets $P$ as a 1-input program and searches for a proof that $P(P)$ halts, and halts when it does. Then OP's $M$ is $M_1(M_1)$ (that is, $M_1$ run on itself). Similarly, in my answer, we can construct $N_1$ on similar lines, and let $N$ be $N_1(N_1)$. I leave actually writing the pseudocode (for p in proofs etc) to someone else. $\endgroup$
    – Akiva Weinberger
    Commented Aug 4, 2022 at 13:05
  • $\begingroup$ A bounded version of this problem is considered here: lesswrong.com/posts/TNfx89dh5KkcKrvho/…. It's bounded in the sense that M only searches proofs up to some maximum length. They also consider the case with two programs that each search for a proof the other halts. This is eventually used to construct agents which achieve mutual cooperation in the Prisoner's Dilemma, while still defecting against exploitable opponents. arxiv.org/abs/1401.5577 $\endgroup$
    – Oscar Cunningham
    Commented Aug 4, 2022 at 14:58

2 Answers 2

Reset to default
80
$\begingroup$

It is a very nice question. The answer is yes, the machine will find a proof of its own halting nature, and it will halt when it does so.

I claim this is a consequence of Löb's theorem. Let $M$ be a Turing machine such as you describe. Note that it is not quite correct to say "the" Turing machine that does what you say, since there will be infinitely many different machines $M$ that search for proofs that they themselves halt. It may not be clear initially that they all have the same behavior, but let me show that indeed they do all halt.

Let $\psi$ be the assertion "$M$ halts." Thus, we can prove in ZFC that if $\psi$ is provable, then it is true, since $M$ would discover the proof. Thus, ZFC proves $\text{Pr}_{ZFC}(\ulcorner\psi\urcorner)\to\psi$. But this is exactly the situation that Löb's theorem is about, and it tells us that we can prove $\psi$ directly in ZFC. So we can prove in ZFC that $M$ halts, as I claimed. It follows that we can prove in PA and much less that $M$ halts, since once we have the actual ZFC proof that it halts, then we can prove in a very weak theory that the actual Turing machine computation halts in whatever specific number of steps it would take to verify the finding of it.

That argument uses the ZFC version of Löb's theorem, but we can get by with the standard PA version, even though M is searching for proofs in ZFC. The reason is that in PA we can prove that $\text{Pr}_{PA}(\ulcorner\psi\urcorner)\to\psi$, since if PA proves that $M$ halts, then we can prove that ZFC will prove it as well, and so $M$ will halt. Thus, we need only the standard PA version of Löb's theorem to see that PA proves that $M$ halts.

Incidentally, regarding the negated version and the proof of the incompleteness theorem you mention at the end of the post, these ideas are also the basis of the universal algorithm. See my paper The modal logic of arithmetic potentialism and the universal algorithm.

Improve this answer
$\endgroup$
11
  • 7
    $\begingroup$ I was just about to mention Löb's theorem in a comment! $\endgroup$
    – Steven Stadnicki
    Commented Aug 4, 2022 at 0:38
  • 8
    $\begingroup$ I wrote an answer that expands out the proof of Löb. $\endgroup$
    – Akiva Weinberger
    Commented Aug 4, 2022 at 1:45
  • 4
    $\begingroup$ And thanks to @JoelDavidHamkins for writing this explanation! Exhilarating ideas. :) $\endgroup$
    – paul garrett
    Commented Aug 4, 2022 at 2:20
  • 2
    $\begingroup$ I think Joel's was the first so I will accept that, but I wish I could accept both answers! $\endgroup$
    – Henry Yuen
    Commented Aug 4, 2022 at 11:03
  • 3
    $\begingroup$ Another example: Suppose we write a machine $L$ that, if it finds proof that $L$ halts then it halts (and stops searching), and if it finds a proof that $L$ doesn't halt then it enters an infinite loop (and stops searching). Naïvely, we might think (since Con(ZFC) poisons our brains) that $L$ has the same behavior as $M$, so it halts. But since $L$ is searching for two things, our proof does not work. (I think that the fate of $L$ depends on implementation (unlike $M$ which halts no matter how you write it).) $\endgroup$
    – Akiva Weinberger
    Commented Aug 7, 2022 at 3:53
83
$\begingroup$

Build a second machine $N$. $N$ searches for a proof in ZFC of, "if $N$ halts then $M$ halts". If it finds one, it halts.

ZFC can argue as follows. "Suppose $N$ halts. Then it found a proof that if $N$ halts then $M$ halts. This, combined with the trace of $N$ halting, would be a ZFC proof that $M$ halts. Thus $M$ finds this and halts."

That paragraph is a ZFC proof that if $N$ halts then $M$ halts… which $N$ finds, so $N$ halts. Thus, by the same logic as above, there is a proof that $M$ halts, which it will find and then halt on.

Isn't this hilarious? We prove this fact about our self-referential machine by constructing a second self-referential machine. This is basically how the proof of Löb's theorem works (see Joel David Hamkins's answer).

Improve this answer
$\endgroup$
11
  • 10
    $\begingroup$ Yes, hilarious, indeed! Thanks for writing this out! $\endgroup$
    – paul garrett
    Commented Aug 4, 2022 at 2:20
  • 6
    $\begingroup$ Beautiful -- this is a lot more understandable to me than "modal logic" (what shows up on Lob's theorem's Wiki page). $\endgroup$
    – Henry Yuen
    Commented Aug 4, 2022 at 11:04
  • 3
    $\begingroup$ @HenryYuen Wikipedia does it by constructing a sentence $\Psi$ that satisfies $\vdash\Psi\leftrightarrow(\Box\Psi\rightarrow P)$ (where $P$ is "$M$ halts"). In words, that means it's a sentence $\Psi$ that's true iff, if $\Psi$ has a proof then $P$ holds. In other words, $\Psi$ is the sentence "If this sentence is provable then $P$ holds" (that is, $\Psi$ is the sentence "If this sentence is provable then $M$ halts"). Compare this to what I use, which is that $N$ halts iff, if there's a proof that $N$ halts then $M$ halts. $\endgroup$
    – Akiva Weinberger
    Commented Aug 4, 2022 at 11:28
  • 6
    $\begingroup$ @HenryYuen Wikipedia's proof is more general because it applies not just to the provability operator (what Hamkins calls $\text{Pr}_{ZFC}(\ulcorner\cdot\urcorner)$, which takes a ZFC formula as input and produces a ZFC formula as output), but to anything that behaves like the provability operator. It's also easier to verify, as it's all syntactic rules. The downside is it's harder to see what's going on. (I suppose this is a metaphor for formalization in general.) $\endgroup$
    – Akiva Weinberger
    Commented Aug 4, 2022 at 12:03
  • 3
    $\begingroup$ @mathlander This is a consequence of Kleene's recursion theorem (pronounced /ˈkleɪni/ KLAY-nee), believe it or not), which essentially states that we may assume programs can access their own source code. For a specific construction, see this comment I wrote above. $\endgroup$
    – Akiva Weinberger
    Commented Dec 26, 2022 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .