This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the halting problem? I want to state clearly I am aware the following argument surely contains errors and is not valid, I wouldn’t like this question to be perceived as pretentious or arrogant.
I’ll call $D$ the decider for the halting problem, and $H$ the pathological program containing $D$ as a subroutine. $D$ is an algorithm we assume can always determine whether the Turing machine described in its input will halt.
I have been thinking about the possibility for a program to recognise instances of itself inside its input. I think that if $H$ has $D$ as a subroutine, when $D$ is running, $D$ could terminate in a halting state, making the whole of $H$ terminate without exiting the subroutine. The decider (the subroutine $D$) has to read the description of some machine $M$ on the tape, then it has to print a symbol, let’s say adjacently to the left extreme of the description (as in Turing 1936): a $1$ if $M$ halts and a $0$ if not. After that, $D$ has to reach some halting state $q(h)$. We can imagine that if $D$ is a subroutine, $H$ has in its description some instructions of the kind “when in state $q(h)$ do such and such and move to state $q(x)$”. The pathological machine $H$ has to have some halting state, say we call it $q(s)$, that stops the entire program: it has to be able to either stop or loop by assumption.
One could argue that for any of the state-symbol pair the machine ends in to go into an halting state, there is a pathological program $H$ that starts from that exact same state-symbol pair and can lead the machine either to a loop or to a definitive halt. But I thought maybe this is not the case if $D$ has as input the source code (the description) of $H$: in this case the final state-symbol pair in which $D$ terminates can be chosen ad hoc as a function of the description given as input. And if $H$ has the possibility of either halting or looping, this means it has to have in its description some state that no instruction takes as starting state to make the halting scenario possible. $D$ can be built so that, if needed, it directly terminates in such necessary state without passing through the rest of $H$’s description. Whatever hardware (namely, possible states and symbols) we program $D$ and $H$ on, we can build $D$ so that, depending on the input, it can terminate in any state it doesn’t use.
Imagine $D$ composed by $A$ and $B$, where $B$ just stores the description of $A$. $A$ could use its description to recognise itself in the description of $H$ given as input in the pathological case. Then $A$ could do something like asking itself “if this was the program in which I am embedded, what actions would make my prediction true?”. If it gets $H$ as description, $A$ is going to recognise that the instance of itself in the simulation always makes the wrong prediction if it allows $H$ to keep running at the end of the subroutine $D$. So, $D$ outputs $1$ (halting), then looks at what is the necessary halting state where the final part of $H$ is not triggered and terminates there to completely stop $H$.
My point is: if $D$ recognises itself in the input, it can also recognise that the simulated $D$ is going to get as input the same input it got, and can "conclude": "in whatever state I alt, the simulated $D$ is going to do the same". Then it predicts "halt", looks at the halting state that globally stops the simulated $H$ and halts in that state.
In what ways do you think this doesn’t make sense?
As asked, some (low quality) pseudocode to try and explain more decently my idea:
D(input):
is_self_and_gets_same_input = D.recognize_self(input)
if is_self_and_gets_same_input == true:
prediction, final_state = D.help_self(input)
return prediction, final_state
else:
prediction = analyse_as_usual(input)
final_state = default_final_state
return prediction, final_state
def help_self(input):
for state in D.possible_halting_states: #looks at scenarios
for prediction in “halts”, “loops”:
outcome = D.check_loop(input, prediction, state)
if outcome == prediction:
return prediction, state
Note: I don’t think it makes too much sense for $D$ to “return” a state. With that I am thinking about the fact that you need the Turing machine to be in some particular state $x$ when the subroutine $D$ ends. $x$ has to be a state for which the rest of $H$ has some instructions to move from there, and if $x$ = $z$, with $z$ being the halting state of $H$, $H$ could not move from there, therefore it could not look at the prediction “halt” that the subroutine $D$ produced, and could not trigger the infinite loop.
Note #2: $D$ doesn’t have to simulate the instance of itself, it can just look at it as a black box and analyse how the rest of $H$ makes use of the information potentially produced by $D$ in different scenarios.
