1
$\begingroup$

You are all familiar with the halting problem so I won't repeat it.

Suppose $H$ is a Turing machine which takes as input an encoding of another Turing machine $M$, then searches all possible proof strings until it finds a proof that $M$ halts or a proof that $M$ does not halt. Of course, if there is no such proof then it will search forever, so I do not claim that $H$ decides the halting problem.

Suppose $Q$ is the usual counterexample that first invokes $H$ on $Q$ as a subroutine (this is possible using quine techniques). Then if $H$ reports that $Q$ doesn't halt, it halts. If $H$ reports that $Q$ does halt, it enters a trivial infinite loop.

Now consider what the subroutine $H$ returns. If $H$ would report that $Q$ would halt, that would mean it had found a specific proof that $Q$ would halt, despite the fact that $Q$ obviously would not halt and we could see it enter a trivial infinite loop after a finite number of steps. Assuming that the proof system is consistent, we can be certain that there is no proof that $Q$ halts. Likewise, we can be certain that there is no proof that $Q$ does not halt.

Since there is no proof that $Q$ halts and no proof that $Q$ does not halt, we can be certain that $H$ will never find either one, therefore the $H$ subroutine of $Q$ will continue searching proofs forever, QED. We have proved that $Q$ does not halt.

Wait, what? The fact there is no proof gives a proof. Of course, if there is a proof, that proof is wrong. What's going on here? Where is the error in my reasoning?

(Credits to raoof for the "proof" sketch)

$\endgroup$
11
  • $\begingroup$ "Suppose $Q$ is the usual counterexample that first invokes $H$ on itself as a subroutine." How does $Q$ invoke $H$ on $H$? The input to $H$ must be the encoding of a Turing machine that can run without input. However, $H$ itself is not such a Turing machine. $H$ cannot run without input. This is the first error in your reasoning. $\endgroup$
    – John L.
    Apr 10, 2023 at 2:12
  • $\begingroup$ @JohnL. It is trivial to bundle an input-ful machine together with its input to make an input-less machine, so I decided to use the simpler input-less halting problem. $\endgroup$
    – user253751
    Apr 10, 2023 at 15:53
  • 1
    $\begingroup$ Yes, I knew it is trivial to bundle with an input. However, you should have specified what is the input you have bundled with. $\endgroup$
    – John L.
    Apr 10, 2023 at 18:19
  • $\begingroup$ I see that you updated with "quine techniques". Can you specify your usage of the quine techniques in detail? It would be great if you also include a proof/reference for that. $\endgroup$
    – John L.
    Apr 10, 2023 at 18:22
  • 1
    $\begingroup$ @JohnL. There's not much to say there, it's just a standard application of the Recursion Theorem. $\endgroup$ Apr 10, 2023 at 20:09

3 Answers 3

1
$\begingroup$

This is a very natural question, and it hinges on a logical subtlety: when you describe the machine $H$'s behavior as

search[ing] all possible proof[s] until it finds a proof that $M$ halts or a proof that $M$ does not halt,

what exactly do you mean by "proof"? The only way you derive a contradiction is if there is some system $T$ such that (i) by "proof" you mean "proof in $T$" and (ii) the argument of your post goes through in $T$. However, one crucial assumption you've made about proofs in your post is that they are correct: we never prove false halting or non-halting facts. This means that the argument of your post can't go through in the same theory that it implicitly talks about, by (a consequence of) Godel's second incompleteness theorem. So you don't get a contradiction at all.

At the end of the day, what you're essentially doing is proving that the halting problem is creative.


The following might help clarify the situation. Let $T$ be a "reasonable" theory (e.g. any consistent r.e. extension of Robinson arithmetic), and let $A_T,B_T$ be the "$T$-solvable parts" of the halting problem: $A_T$ is the set of machines $T$ proves halt, and $B_T$ is the set of machines $T$ proves don't halt. Then we have:

  • $A_T$ and $B_T$ are disjoint r.e. sets, and the halting problem is a proper subset of $A_T$.

  • If $T$ is $\Sigma_1$-sound, then $A_T$ is exactly the usual halting problem.

  • Meanwhile, since Robinson arithmetic is $\Sigma_1$-complete, we have by mere consistency of $T$ that $B_T$ is disjoint from the true halting problem.

  • But (almost) none of the above is provable in $T$ itself, since $T$ doesn't even know that $T$ is consistent.

$\endgroup$
9
  • $\begingroup$ "everything humans know in mathematics" is one theory (if poorly specified), yes? Either this theory includes the assumption that this theory is consistent, or it doesn't. If it does, we seem to have this paradox. If it doesn't, then humans can't know that proving things means they are correct (unless it doesn't, in which case they can know it does because they can know all true and false things) $\endgroup$
    – user253751
    Apr 10, 2023 at 22:16
  • 1
    $\begingroup$ @user253751 Look at Godel's second incompleteness theorem. No "reasonable" theory can include its own consistency principle without, ironically, becoming inconsistent. I don't agree with your interpretation of the situation, though (the "If not,..." bit), but interpreting Godel's theorems gets us into territory that a comment thread isn't great for. $\endgroup$ Apr 10, 2023 at 22:19
  • $\begingroup$ @user253751 This isn't too weird, though, unless you fixate on having a single theory that exactly corresponds to "math we know." A better picture of human mathematics is to have a whole bunch of theories with varying levels of confidence - e.g. I'm quite confident that $\mathsf{ZFC}$ is consistent, but I'm extremely confident that $\mathsf{PA}$ is consistent, and I'm only somewhat confident that $\mathsf{ZFC}$ + "There is a proper class of supercompact cardinals" is consistent. Per Godel, this is an inescapable feature of the mathematical experience. $\endgroup$ Apr 10, 2023 at 22:31
  • $\begingroup$ hmm, now I will have to ask "is human mathematical reasoning provably inconsistent?" $\endgroup$
    – user253751
    Apr 10, 2023 at 23:16
  • $\begingroup$ @user253751 I don't think there's any single such thing as human mathematical reasoning. Certainly many individual humans have mathematical beliefs which it turns out are subtly inconsistent. But Godel in no way implies that all systems are inconsistent, or that we cannot sensibly navigate a wide array of systems some of which may be inconsistent. We only run into trouble if we demand too much. If you want something to lean against, consider limiting mathematics to expressions of the form "The theory $T$ proves sentence $\sigma$" (if $T$ is inconsistent this merely becomes less interesting). $\endgroup$ Apr 11, 2023 at 0:18
-2
$\begingroup$

Of course, if there is no such proof then it will search forever.

This is your mistake: since we permit $H$ to loop forever, the language accepted by $H$ is recognizable but not necessarily decidable. The conventional proof is that Halting Problem is undecidable – that no $H$ exists that can accept or reject any input TM in finite time.

The existence of the Universal Turing Machine proves the Halting Problem to be recognizable, as one can simply simulate any input TM and accept the ones that halt in finite time.

$\endgroup$
6
  • 2
    $\begingroup$ What is the mistake? The quoted statement refers to "there is no such proof" while you are talking about "recognizable" or "undecidable". $\endgroup$
    – John L.
    Apr 10, 2023 at 8:16
  • $\begingroup$ @JohnL. "then it will search forever" $\endgroup$
    – kviiri
    Apr 10, 2023 at 8:25
  • $\begingroup$ @JohnL. The querent is attempting "replicate" the Halting Problem proof using a Halting recognizer, not a decider, and is confused why there is no contradiction. $\endgroup$
    – kviiri
    Apr 10, 2023 at 8:28
  • 2
    $\begingroup$ Are you saying that there is no error in the question if the last paragraph, the paragraph that starts with "Wait, what?" Is deleted? $\endgroup$
    – John L.
    Apr 10, 2023 at 14:30
  • 2
    $\begingroup$ Note that I do not claim to have solved the halting problem. I merely arrived at a contradiction while thinking about the halting problem. Nothing in the question claims to decide whether every machine halts. $\endgroup$
    – user253751
    Apr 10, 2023 at 15:54
-2
$\begingroup$

The "halting problem" is about finding a Turing machine X that DECIDEs whether another Turing machine Y halts with input Z, for every Y and Z. You were instead talking about a Turing machine that RECOGNIZEs whether another Turing machine halts. That is a very different problem. And building a halting recognizer is trivial and doesn't lead to conflicts (well, it's an awful lot of work to build it, but not difficult).

For a DECIDER to exist, it must be true that for every Turing machine Y and input Z either there is a proof that Y halts on input Z, or there is a proof that Y doesn't halt on input Z. And that isn't true.

$\endgroup$
2
  • 2
    $\begingroup$ Note that I do not claim to have solved the halting problem. I merely arrived at a contradiction while thinking about the halting problem. Nothing in the question claims to decide whether every machine halts. $\endgroup$
    – user253751
    Apr 10, 2023 at 15:54
  • $\begingroup$ This is indeed not the problem with the OP's argument - I think you've read too quickly. $\endgroup$ Apr 10, 2023 at 20:09

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.