Halting problem. Decider “recognising itself” in the input? Part 2

Question

This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in the input fed to it, could leverage the fact it can look at the source code of $H$ to help its clone in the input make the right prediction if the simulation was run. By treating the "clone in the input" effectively as the same as itself and therefore helping it out, $D$ would manage to make the right prediction even in the case what is going on in the simulation from the input is happening to the original $D$ too, and there actually is a real $H$ trying to trick it. The question I linked to explains the idea more thoroughly and (maybe) more clearly, but at its core the idea was about $D$ realising that its "clone" described in the input would do the exact same things that the original $D$ does, so $D$ starts acting as it was its clone with the intent of saving it from being tricked.

The error I made in the first question was to think that when programming $H$ you have a set of finitely many possible halting states to choose from, and that therefore $D$ could be programmed to possibly halt in any of the states in this set, so that after reading $H$'s source code it could simply choose to end in that state to ensure halting.

What I am wondering now is: couldn't $D$ still ensure halting of $H$ by using a more sophisticated technique? I'll try and explain more or less what I mean. Sorry for the lack of rigour and the very cloudy outline, please let me know what points need to be clarified the most.

Even if $D$ cannot directly terminate in $H$'s halting state, maybe it could trigger $H$ to decide to halt itself by tricking it into believing the "not halting" prediction was made by $D$. Imagine in the physical implementation of the Turing machine the halting prediction is made by printing 0 or 1 in some special square. The special square is easily recognisable from the external world maybe because the tape has some mark on the other side at that position, or (as in Turing 1936) the special square is the one immediately to the left of where the machine description given as input begins. $H$ cannot see the external world and it has to orient itself only based on the landscape of zeros and ones that $D$ left behind after halting. Now, $D$ can be as intelligent as we like, and had both complete access to $H$'s source code and all the time it needed to learn about it, and crucially it can deduce that everything that it does is what its alter ego described in its input would do if the simulation was left running (even if it obviously it can't run the whole simulation because of infinite recursion). Couldn't $D$ be able to arrange some portion of the tape in such a way that after it halts and $H$ is triggered, $H$ is tricked into thinking it is experiencing a reality where the special square says "not halting"? But actually the landscape that $H$ is using to orient itself is some sort of "virtual machine"/"virtual reality" built by $D$ and the true special square is in another part of the tape. By the way, I think this argument can be adapted even to the slightly different framework found in the original Turing paper (circular and circle free machines).

If we take away the ability to keep track of some special square from the outer world, and you ask whether $D$'s prediction can be accessed by any other subroutine/agent existing inside the universe run by the Turing machine, then I think the answer is no. But I also think that subroutines/agents can be built in such a way that they can access the actual prediction ($D$ won't lie to them) and use such information to do anything consistent with the assumption of $D$ being a universal decider.

One objection I see is "what if we make $H$ very intelligent too, so much so that it is always able to fight back and be one step ahead of $D$, hack trough the virtual machine built to trick it etc...? Here I think there is still a crucial problem: $H$ to win has to behave in a way that contradicts what has predicted the simulation of itself will do if left running, while $D$'s goal is compatible with staying coherent with the simulation of itself. What I mean is that at the very beginning $H$ will try to analyse the source code of the subroutine $D$ to understand its behaviour and avoid being tricked by it. But $D$'s behaviour is contingent on what course of action $H$ in its input will take to try and retrieve $D$'s true answer. This course of action has to be exactly predicted by $D$ if it is really a universal decider, then $H$ has to exactly predict $D$ and all of its predictions and yet somehow manage to do something that $D$ predicted it would not do in those circumstances, which is a contradiction. But note that this is not a proof by contradiction that $D$ must not exist: we made two assumptions, the first one is the existence of $D$ and the second one is the existence of this super powerful $H$ always capable of being one step ahead of $D$. Therefore, this is only a proof by contradiction that at least one of these two assumptions must be false.

So my question would be: can $D$ trick $H$ in the way I described? Can you spot any reason why my argument falls apart?

Edit: I got why the previous argument doesn't work. But, in my understanding $H$ has to copy-paste its input (or print it as quines do) to duplicate it and give the two copies to $D$, so I was wondering what would happen if $D$ realises that it has the power to decide if $H$ halts or not and stops trying to predict the behaviour of machines described by its input and treats those descriptions as simply some strings (disregarding they encode a machine description). Maybe the copy-paste procedure leaves in those strings some information about something like how many $H$ calls is some $H$ call nested in, so that $D$ can create some behaviour coherent with the predictions. Suppose you have a set of strings, all are meant to be equivalent descriptions of $H$, but each one pops up as description of $H$ only when $H$ is called inside itself some specific number n of times, then if $D$ alternates predictions back and forth (string1:halt, string2:loop, string3:halt etc...) depending on the number of nested calls, its predictions would be true. I started to wonder about this because it looks like to have a description of itself printed/copied in the exact same way the machine is actually implemented and then simulating it with a universal Turing machine, you need more complexity than you have, am I wrong?

Answer 1

The answer is pretty much the same as before: The person who designs the Turing machine $H$ won't let it happen. They won't allow $D$ to behave any differently when it's inside $H$ than when it's outside of $H$. Sure, you can try to make $D$ fiendishly complicated, but at the end of the day, it's not difficult to embed a Turing machine inside another so that it behaves exactly the same as when it's not embedded.

For example, $D$ might play weird tricks with the tape - like moving a million squares to the right just to check it's not in a small blank space of a tape that has other stuff on it - the designer of $H$ would just groan, curse the designer of $D$, edit the copy of $D$ so that it always moves twice as many spaces as the original $D$ did, make sure it starts on an odd-numbered space, and make sure the rest of $H$ only uses even-numbered spaces.

Or as in your original question, $D$ might go to a halting state after computing the answer. In fact that's not even trickery - that's what $D$ is supposed to do. The designer of $H$ will make those states non-halting and then add transitions back to the rest of $H$.

Or $D$ might try to use the same alphabet symbols used by $H$, like drawing "special squares" in the wrong places. Then the designer of $H$ will just change them to other symbols that don't conflict. Or they change the symbols they are using for their part of $H$, so they don't use the same ones $D$ is sneakily writing.

There is absolutely nothing you can possibly do to $D$ to make it "smartly" recognize that someone has copied and pasted and edited it, that can't be easily bypassed by the person doing the copying and pasting and editing. Even if you can think of something really really really fiendish, the designer of $H$ could embed a universal Turing machine (a Turing machine simulator), and run $D$ inside that.

---

You seem to think there is some reason that $H$ must contain an exact copy of $D$. That is not true. $H$ can contain whatever the designer of $H$ wants it to contain. It's possible that someone can find a program that $D$ doesn't decide correctly, which doesn't contain anything at all based on $D$! However, including a (possibly slightly modified) copy of $D$ is a surefire way to design $H$. 100% of the time it works every time.

The point is that $H$ checks what $D$ would say if it was run with $H$ as a parameter, and then does the opposite. Therefore, obviously, $H$ does the opposite of whatever $D$ says it does. You are trying to get around it by proposing that when $H$ checks what $D$ would say, it gets a different result than what $D$ actually says, or it "crashes". But that is impossible to achieve. It is impossible to write a $D$ which can't be checked. Think of it like a sandboxed program which can't tell that it's running inside a sandbox.

---

In a comment, you wrote:

D would see from H's description that H is running D as a simulation in a universal Turing machine and would take that into account to trick H as in the other cases

It's possible that with certain combinations of $D$ and $H$, $D$ run with input $H$ can detect that $H$ tries to simulate $D$ with input $H$. Fiendishly difficult, and not always possible (the designer of $H$ is able to hide it), but sometimes possible (let's say they don't hide it). Let's imagine that it can detect this. Then, when a human simulates $H$, $H$'s simulation of $D$ will return, for example, non-halting. Then $H$ will halt. "Haha!" you say, "I really wanted $H$ to halt all along! My crafty little $D$ has tricked $H$ into halting, which was the real prediction and it's correct!"

Except, when the same human runs $D$ with input of $H$, it will make the exact same detection, and it will again return non-halting to trick $H$, except it's not embedded into $H$ and so it just predicts non-halting. Which is a wrong prediction, because as I said in the last paragraph, $H$ halts. You still lose, good day sir.