-1
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ The one reply I already got was: The prediction that is made by 𝐷 in the last paragraph will cause 𝐻 to not halt, because 𝐻 is programmed to do the opposite of what 𝐷 predicts. Thus, 𝐷 cannot correctly predict the behavior of 𝐻, even though it can affect the behavior. $\endgroup$
    – user
    Oct 26, 2020 at 10:15
  • $\begingroup$ To this I would reply: for H not to halt, it has to get out of to subroutine D and execute the last part of code that, based on D's halt prediction, triggers an infinite loop. But, H also has to have some halting state, because it has to be able to both stop and loop. What if the last instruction in the subroutine D moves the machine exactly to that state? I think H could not execute the last part of code that makes it loop. $\endgroup$
    – user
    Oct 26, 2020 at 10:19
  • 1
    $\begingroup$ The definition of decider requires that $D$ must always terminate and answer either "halts" or "does not halt", so $H$ will "get ouf of the subroutine $D$" because we assumed that $D$ was a decider. Furthermore, $D$ cannot "jump" directly into some part of $H$, it has no access to $H$ at all. $\endgroup$ Oct 26, 2020 at 13:44
  • 1
    $\begingroup$ Please don't carry out extended conversations in the comments, and please don't add clarifications in the comments. Instead, please edit the question to improve it: use the comments to identify how the question can be improved, and then revise the question based on the feedback you've received. Please format pseudocode in a readable way. $\endgroup$
    – D.W.
    Oct 26, 2020 at 15:41
  • 1
    $\begingroup$ Please put the code in your question, at the end. You can use formatting in Markdown to display it nicely. $\endgroup$ Oct 26, 2020 at 21:29

1 Answer 1

3
$\begingroup$

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.

I think this is the core of your argument - stated again here:

$D$ can be built so that, if needed, it directly terminates in such necessary state without passing through the rest of $H$’s description

However, this is not true.

Think about what the sentence "$H$ has $D$ as a subroutine" means. It means that the person who created $H$ looked at $D$, and copy-pasted it into $H$, and then adjusted their copy of $D$ to "wire it up" into $H$ - such as by renaming states or symbols to avoid conflicts, and importantly for this question, by making the final states non-final.

The author of $H$ didn't want $D$ to lead directly to random halting states, so they didn't make it do that. The states that used to be the final states of $D$ now lead to whichever other states the author of $H$ wanted to happen next after $D$ finishes.

Part of $D$'s algorithm can include looking for an algorithm isomorphic to $D$, but there is no way for the algorithm $D$ to enforce that the machine halts immediately after the execution of $D$. As long as the "core" of the algorithm remains the same, the author of $H$ will just remove the silly "and then please halt" instruction.


Remember this algorithm is supposed to compute a mathematical function, and mathematics has no concept of "the answer is 1 but you must abort the rest of the calculation and the final answer is 1." Forcing an abort is like defining this function:

$$ f(x) = x+2 \textrm{ but then abort the calculation and the final answer is }x+2 $$ so that $$ f(2) = 4 \\ f(2)+2 = 4 \textrm{ because we aborted the +2} \\ f(2)^{500} = 4 \textrm{ because we aborted the }^{500} \\ $$ which is just silly.

$\endgroup$
8
  • $\begingroup$ What I am saying is: $H$ has to halt somewhere, and there is nothing stopping $D$ to be programmed so that it has the halting state of $H$ as one of its possible halting states. Then you can think of $D$ as some general intelligence that is handed as input with an entire description of $H$. Then $D$ kind of thinks: $\endgroup$
    – user
    Apr 7, 2022 at 13:34
  • $\begingroup$ "mmh this subroutine inside $H$ is me, and there is some possibility that this is what is happening to me and right now and I am hostage of $H$ (but I don't know because this is he only input I get from the outside world). Anyways, I really want to get this prediction right too, how can I do it? Well, let me go and check what is the halting state of this guy $H$, so that I will predict "halt", then I'll go to sleep in the halting state of $H$, so that in the remote possibility this is some inception like thing I will still get it right, because from that state $H$ will not be triggered" $\endgroup$
    – user
    Apr 7, 2022 at 13:39
  • $\begingroup$ Sorry for the completely not rigorous argument, I was hoping that trying to convey it from different angles could help get my point across. $\endgroup$
    – user
    Apr 7, 2022 at 13:43
  • 2
    $\begingroup$ @AlessandroM.Agostinelli D cannot be programmed to enter H's halting state because H's halting state is not a state in D! $\endgroup$
    – user253751
    Apr 7, 2022 at 14:01
  • 1
    $\begingroup$ @AlessandroM.Agostinelli All of the transitions of D go to the states of D, because it's a Turing machine, and every Turing machine's transitions go to the states defined in that machine. $\endgroup$
    – user253751
    Apr 7, 2022 at 14:36

Your Answer

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

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