# Is there a "halting machine" which halts on itself?

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.

• See also this related question: mathoverflow.net/q/427842/1946, and also this one: mathoverflow.net/q/131407/1946. Dec 14, 2023 at 13:50
• 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
– Stef
Dec 14, 2023 at 19:49
• Related on codegolf.SE: Interpret your lang, but not yourself? Dec 14, 2023 at 21:45
• 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).
– Ben
Dec 15, 2023 at 3:35

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