12
$\begingroup$

The crux of the halting problem is that there can be no Turing machine $M$ such that $\text{Halt}(M(N))=\neg \text{Halt}(N(N))$ for all Turing machines $N$, since $\text{Halt}(M(M))=\neg \text{Halt}(M(M))$ is impossible.

Suppose that we removed the negation, and asked simply for a Turing machine $M$ such that such that $\text{Halt}(M(N))=\text{Halt}(N(N))$ for all $N$. This removes the contradiction. In fact, there is an easy example of such a machine. Namely, we can define $M^{\text{triv}}$ to be the machine which runs $N$ on itself whenever given $N$ as input.

We can now ask: what is $\text{Halt}(M(M))$? A-priori from the relation $\text{Halt}(M(N))=\text{Halt}(N(N))$ we get no clues, since plugging in $N=M$ we get the tautology $\text{Halt}(M(M))=\text{Halt}(M(M))$.

For the trivial machine $M^{\text{triv}}$, we see that $\text{Halt}(M^{\text{triv}}(M^{\text{triv}}))=\text{False}$. This is because when you run $M^{\text{triv}}$ on itself it will recursively run on itself forever, never stopping. In fact, for any naive machine $M$ with $\text{Halt}(M(N))=\text{Halt}(N(N))$ it feels natural that $\text{Halt}(M(M))=\text{False}$. When writing out the definition of $M$ you will have to do some amount of recursion that picks up information about how $N$ runs on itself, so when you run it on itself it will keep on doing this recursion forever. So, this brings us to the question:

Can there be a Turing machine $M$ such that $\text{Halt}(M(N))=\text{Halt}(N(N))$ for all Turing machines $N$, and $\text{Halt}(M(M))=\text{True}$?

One trivial example might be a machine which first detects if its input is equal to itself, halts if that is the case, and runs the input on itself otherwise. However, I am a bit skeptical of this. Can a machine really "know" what its original state was? In trying to determine its original state the Turing machine's state will change. I am by no means an expert in this area, so I can't tell. I have very little intuition about whether or not the central question of my post is non-trivial, or what the answer should be if so, but I am very curious to know the answer.

$\endgroup$
4
  • 2
    $\begingroup$ See also this related question: mathoverflow.net/q/427842/1946, and also this one: mathoverflow.net/q/131407/1946. $\endgroup$ Dec 14, 2023 at 13:50
  • 11
    $\begingroup$ Upvoted!! "One trivial example might be a machine which first detects if its input is equal to itself, halts if that is the case, and runs the input on itself otherwise. However, I am a bit skeptical of this. Can a machine really "know" what its original state was?" <<< Oh, I take it you are not familiar with a person named Willard Van Orman Quine and another person named Douglas Hofstadter. Wonderful discoveries are waiting for you :D $\endgroup$
    – Stef
    Dec 14, 2023 at 19:49
  • 1
    $\begingroup$ Related on codegolf.SE: Interpret your lang, but not yourself? $\endgroup$ Dec 14, 2023 at 21:45
  • 3
    $\begingroup$ The TM doesn't actually have to "know what its original state was". The TM's execution has state, but the description of the TM itself is just a string, which is timeless. There's no "original" or "was" about it. We just have to construct a TM that has a branch it goes down when its input is matches a single hard-coded string, where that string happens to be the description of the TM itself, but the TM doesn't "know" that. (In solving for such a TM, it obviously can't simply contain its own description verbatim, so it'll have to be encoded in a quine-like way, but that can be done). $\endgroup$
    – Ben
    Dec 15, 2023 at 3:35

1 Answer 1

30
$\begingroup$

Kleene's recursion theorem states that for any TM $P(x,y)$ there is a TM $G(x)=P(x, G)$, so in particular for $$P(x,y) = \begin{cases}\text{Halt} & x=y \\ x(x) & \text{otherwise}\end{cases}$$ we get the program you suggested

$\endgroup$
2
  • $\begingroup$ This is fantastic. Thank you! $\endgroup$
    – Milo Moses
    Dec 14, 2023 at 20:36
  • $\begingroup$ Though this is less useful than it may seem. There are many, many ways to encode essentially the same computation as a Turing machine (for a trivial example: for any machine M and natural number n, there is machine M′(n) that performs k steps of useless busywork, and then proceeds with the same computation as M). If you try to recognize them all, you run into the halting problem again. $\endgroup$ Dec 16, 2023 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.