<p>Although your reasoning is flawed, I believe it is educational to see why. First of all, I have a rule of thumb when I am trying to prove something that seems extraordinary or difficult: "Assume that your approach is wrong and try to find out why". Arguing against yourself is not an easy task, but it is very important.</p>

<p>One technique I use very often is trying to apply the same argument to different situations. In other words, I'm trying to find a counterexample. Assume that your reasoning is perfect.
Then, apart from computability, you are disproving a good part of mathematic knowledge, which is based on contradiction proofs. For example, the statement that there is no natural number such that no other natural number is greater than it, uses contradiction. This result is much more intuitive than the undecidability of halting.</p>

<p>Perhaps the notion of contradiction could be better understood if you think of every person trying to prove a statement as a little God: Assume that you have a theory, i.e. a number of axioms and theorems. Assume also that you have a universe that instead of physical laws, obeys only this theory. Now , if you wanted to prove that statement S is false,you could work in the following way (an analogy to the physical world and a statement such as the conservation of energy is highly educational):</p>

<ol>
<li><p>Split the original universe U into two parts, A and B, that are equal to U and obey its theory.Then make an addition that is unique to every part: Assume that in part A S holds, while in part B of the universe S is false. This is not the same as saying that S or its denial is an axiom in the respective part. It might be possible that a proof exists, however you are not aware of it (yet).</p></li>
<li><p>If S is false in both parts, then it must be also false in the whole universe. In the part B of universe that it is false (proven so by an unknown proof) you don't have to worry about it. If this argument does not sound very convincing, you can consider part B as small as you like: for example, if B consisted of only 2 atoms, you could easily verify the law of energy conservation.</p></li>
<li><p>Now, consider the part A. If you could show that A does not obey its own theory,that is the original theory and the theorem that S is true, it could not exist. However, you know that the original theory is true, therefore it must be that last theorem that does not allow part A to exist. Therefore, since part A does exist, S must be false. </p></li>
<li><p>Now you have that S is false in both parts of your universe, so it is false for the whole universe as well.</p></li>
</ol>

<p>I would also highly recommend reading the following posts from Terence Tao's blog. I found them very instructive. He talks about contradiction and how to create objects that are so powerful, that contradict their own existence:</p>

<p><a href="http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/" rel="nofollow">The “no self-defeating object” argument</a></p>

<p><a href="http://terrytao.wordpress.com/2010/10/18/the-no-self-defeating-object-argument-revisited/" rel="nofollow">The “no self-defeating object” argument, revisited</a></p>

<p><a href="http://terrytao.wordpress.com/2010/11/02/the-no-self-defeating-object-argument-and-the-vagueness-paradox/" rel="nofollow">The “no self-defeating object” argument, and the vagueness paradox</a></p>

CC BY-SA 2.5
2010-12-16T03:18:09.340Z
Look, there is nothing wrong with the "proof by contradiction" technique, nor am I claiming that.  I **am** claiming that there is a serious problem with the way that the technique has been employed in Turings proof.  The proof forms a series of "if / then" conditionals and then uses "Denying the antecedent" to form the contradiction.  But due to the conditional chaining, it is not possible to get to `halt()` is "undecidable" without first explicitly passing through `halt()` is "decidable" for the very case being reasoned about.
johne
CC BY-SA 2.5
2010-12-16T03:35:43.937Z
@johne I can't understand how your criticism doesn't hold for proofs by contradiction in general. The halting proof is trying to show $\neg\exists M$ s.t $L(M)=H$, so it proceeds by assuming $\exists M$ s.t. $L(M)=H$. It then shows that in fact $L(M)\neq H$. From this we conclude that our assumption of $\exists M$ s.t. $L(M)=H$ is flawed. Thus, classically, we can conclude that $\neg\exists M$ s.t. $L(M)=H$. Where in there do you have a problem?
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T03:37:43.200Z
In the proof given by Turing, it's not a question of "If this is true, then it would imply.."  The way the proof is constructed is that `halt()` MUST have been decidable at some point in the past and at the point of contradiction it has become undecidable for a case that we could have reached if, and only if, `halt()` was decidable in the past for this specific case.  The fact that "for some reason" it is undecidable now can not change the fact that it was decidable in this results causal past.
johne
CC BY-SA 2.5
2010-12-16T03:44:39.247Z
@johne Mathematical proofs do not deal with "time" in that way. Proof and truth are time invariant. It's not showing that halt() "becomes" undecidable. It's showing that if we think we have a TM that solves the halting problem, then we can always break it. So, it must be the case that we don't have a TM that solves the halting problem.
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T03:51:10.890Z
@mark: Because the proof given by Turing "shows that in fact $L(M) \ne H$" by explicitly, conditionally, and causally requiring $L(M)=H$ to be true in order to show "$L(M) \ne H$". But it's not $L(M) \ne H$ that is proven, it must be $\lnot(L(M)=H)$, because thats what was true in the past.  These are two radically different things: $\lnot(L(M)=H)$ means it is still possible to decide the Halting Problem, the fact that you ignored or negated the result does not, and can not, change that fact.
johne
CC BY-SA 2.5
2010-12-16T03:54:28.267Z
@johne You are missing quantifiers. $L(M) \neq H$ is the same as $\neg(L(M) = H)$. This might be the root of the problem. Turing's proof assumes $\exists M.~L(M)=H$, derives a contradiction, and concludes $\neg\exists M. ~L(M)=H$. IOW, there is NO TM that decides the halting problem. Therefore, it is undecidable.
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T04:03:45.003Z
I believe the following excerpt from Tao's blog could be used for a contraposition proof: "suppose that all statements in a suitably strong and consistent logical system were either provable or disprovable. Then one could build a program that determined whether an input string {S}, when run as a program, halts in finite time, simply by searching for all proofs or disproofs of the statement “{S} halts in finite time”; this program is guaranteed to terminate with a correct answer by hypothesis."
chazisop
CC BY-SA 2.5
2010-12-16T04:24:22.613Z
@mark Ok.  The $\delta$ transition function for a TM is a fixed number of finite states with a fixed finite number of symbols.  This can be mapped to the Boolean domain, and we can use Boolean algebra to decide `halt()`.  In this case, it is impossible for the Boolean algebra to be undecidable.  Additionally, König's lemma says that $\delta$, which is completely finite, can not have an infinite acyclic path- therefore, König's lemma says that the halting problem must be decidable.  So which "Proof by contradiction" is going to take precedence here?
johne
CC BY-SA 2.5
2010-12-16T04:46:17.483Z
@johne That "proof" doesn't make sense. How do you get from a finite state controller to using Boolean algebra to "decide" the halting problem? TM have an infinite tape, so the full state of the TM is much more than just the finite controller. It's almost trivial that a TM either halts or its finite state controller loops. How do you get from there to an algorithm that decides the halting problem? What is the actual algorithm?
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T05:16:34.577Z
@mark Simple: [CMOS boolean logic](http://www.ece.virginia.edu/~mrs8n/cadence/SynthesisTutorials/tsmc18.pdf). In fact, I can probably crank off a simple TM in Verilog in about an hour and synthesize an FPGA / ASIC with a "tape" port that has {symbol, r/w, l/r, etc}. Boolean algebra? No problem.  As for a TM and state, the tape is irrelevant- the $\delta$ transition table contains everything you need to enumerate all of the finitely possible acyclic path permutations that the tape could ever cause $\delta$ to transition through.
johne
CC BY-SA 2.5
2010-12-16T05:24:03.567Z
@johne The tape is precisely the difference between a TM and an FSM. You can have a TM whose controller loops, yet it halts. You seem to think that the halting problem boils down to determining whether the controller loops. It doesn't. That is necessary, but far from sufficient for a TM not to halt.
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T01:51:18.193Z
2010-12-16T01:51:18.193Z
chazisop
<p>I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof.  Since there are so many formulations of this proof, rather than pick a specific one, I will sketch out the general outline that every proof I've seen follows (at least, I honestly don't remember one that doesn't follow this pattern):</p>

<ol>
<li>Assume that there is a function <code>halt()</code> that can decide whether or not a given Turing Machine halts or not.</li>
<li>Construct a Turing Machine that embeds <code>halt()</code>, but "does the exact opposite".</li>
<li>...</li>
<li>Proof by contradiction that because we have constructed a program that embeds <code>halt()</code>, but does the exact opposite, this proves that <code>halt()</code> can not exist.</li>
</ol>

<p>I believe the above is "sufficiently accurate" for the purposes of this question.  Please feel free to speak up if you feel it misses some nuance of the problem and / or proof.</p>

<p>My objection with this entire class of proofs is:</p>

<ul>
<li>Every formulation of the problem / proof begins by assuming that <code>halt()</code> exists and is capable of <em>deciding</em> whether or not a given Turning Machine halts or not.</li>
</ul>

<p>At this point in the proof, there are really only two possibilities:</p>

<ol>
<li><code>halt()</code> does not, or can not, <em>decide</em> whether a Turing Machine halts or not.</li>
<li><code>halt()</code> can, and does, <em>decide</em> whether or not a Turing Machine halts.</li>
</ol>

<p>The problem is this: If we choose the first possibility, that is to say that for some unspecified reason <code>halt()</code> does not "work as advertised", the proof comes to an end.  There is literally no point in proving <code>halt()</code> can not <em>decide</em> whether a Turing Machine halts or not if we handicap it from the start- we already know the answer.</p>

<p>I'm not aware of any proof that places qualifications on <code>halt()</code> at this point in the proof, therefore the only reasonable choice is the second possibility.  This means that we axiomatically define <code>halt()</code> in order to "bring it in to existence".  The problem with this is- <code>halt()</code> is axiomatically defined, and therefore is guaranteed to <em>decide</em> whether or a Turing Machine halts or not.</p>

<p>Since <code>halt()</code> is axiomatically defined as being able to <em>decide</em> whether a Turing Machine halts, any analysis that arrives at a result that contradicts this behavior <strong><em>can not</em></strong>, by definition, prove that <code>halt()</code> is <em>undecidable</em>.  The axiomatic definition of <code>halt()</code> is so strong that any result that causes, or results in, a contradiction of <code>halt()</code> is proof that the hypothesis is invalid.  Basically, just like the first possibility, there's no point in continuing on with the proof with this choice either because we have our answer- it is impossible to prove that the Halting Problem is <em>undecidable</em> using this technique because it is axiomatically guaranteed to be <em>decidable</em>.</p>

<p>Therefore, I personally consider this family of Halting Problem proofs to be invalid.</p>

<p>So, I'm wondering if anyone is aware of a proof of the Halting Problem that is "independent" of this style and family of proof.  I have a strong preference for a proof that does not rely on "diagonalization" or "recursion" in any way.  My preference is for something rooted in graph theory.</p>

<p>Which raises a different problem:  So far, I have been unable to arrive at a zero-order approximation of a Halting Problem proof using other means.  In fact, every back of the envelope attempt has completely failed to arrive at the same conclusion.</p>

<p>The strongest one I've managed to come up with is roughly: The $\delta$ transition table is finite, with a finite number of symbols.  An appeal to König's lemma seems to be enough to justify that there is no infinite path, and therefore it must be possible to find a path from the start state to a halting state, if one exists.  Not intended as proof, but a result from graph theory, whatever it is, would be much stronger than the current "Say something is true, then do the exact opposite, and then claim that by doing the exact opposite of what you first claimed, you've proved that it was never true to begin with" <em>proof</em>.</p>

<p>Does anyone:</p>

<ol>
<li>Have a Halting Problem proof that is <em>significantly different</em> than the current "standard" proof?  My preference is for a proof that gives the same result using completely different techniques and / or approach.  So far, I have only been able to find derivatives of the "standard" proof.</li>
<li>See a problem with the analysis above?</li>
</ol>

<p><strong>edit</strong></p>

<p>@Kaveh stated <code>Note that undecidability of H is usually stated negatively</code>.  To be clear, from Turings <em>On computable numbers, with an application to the Entscheidungsproblem</em> paper that established the proof:</p>

<p>It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable.  It might, for instance, be thought that the limit of a sequence of computable numbers must be computable.  This is clearly only true if the sequence of computable numbers is defined by some rule.</p>

<p>Or we might apply the diagonal process.  "If the computable sequences are enumerable, let $a_n$ be the $n$-th computable sequence, and let $\phi_n\left(m\right)$ be the $m$-th figure in $a_n$.  Let $\beta$ be the sequence with $1 - \phi_n\left(n\right)$ as its $n$-th figure.  Since $\beta$ is computable, there exists a number $K$ such that $1 - \phi_n\left(n\right) = \phi_K\left(n\right)$ all $n$.  Putting $n = K$, we have $1 = 2\phi_K\left(K\right)$, <em>i.e.</em> $1$ is even.  This is impossible.  The computable sequences are therefore not enumerable".</p>

<p>The fallacy in this argument lies in the assumption that $\beta$ is computable.  It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps.  In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.</p>

<p>The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes $\beta$.  This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that "there must be something wrong".  The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea "circle-free".  It depends not on constructing $\beta$, but on constructing $\beta&#39;$, whose $n$-th figure is $\phi_n\left(n\right)$.</p>

<p>Let us suppose that there is such a process; that is to say, that we can invent a machine $\mathcal{D}$ which, when supplied with the S.D of any computing machine $\mathcal{M}$ will test this S.D and if $\mathcal{M}$ is circular will mark the S.D with the symbol "$u$" and if it is circle-free will mark it with "$s$".  By combining the machines $\mathcal{D}$ and $\mathcal{U}$ we could construct a machine $\mathcal{M}$ to compute the sequence $\beta&#39;$. The machine $\mathcal{D}$ may require a tape.  We may suppose that it uses the $E$-squares beyond all symbols on $F$-squares, and that when it has reached its verdict all the rough work done by $\mathcal{D}$ is erased.</p>

<p>...</p>

<p>It is clear the original proof "assumes that there is a function <code>halt()</code> that can decide whether or not a given Turing Machine halts or not."</p>

<p>...</p>

<p>The machine $\mathcal{H}$ has its motion divided into sections.  In the first $N - 1$ sections, among other things, the integers $1, 2, \ldots, N - 1$ have been written down and tested by the machine $\mathcal{D}$.  A certain number, say $R\left(N - 1\right)$, of them have been found to be the D.N's of circle-free machines.  In the $N$-th section the machine $\mathcal{D}$ tests the number $N$.  If $N$ is satisfactory, <em>i.e.</em>, if it is the D.N of a circle-free machine, then $R\left(N\right) = 1 + R\left(N - 1\right)$ and the first.  $R\left(N\right)$ figures of the sequence of which a D.N is $N$ are calculated.  The $R\left(N\right)$-th figure of this sequence is written down as one of the figures of the sequence $\beta&#39;$ computed by $\mathcal{H}$.  If $N$ is not satisfactory, then $R\left(N\right) = R\left(N - 1\right)$ and the machine goes on to the $\left(N + 1\right)$-th section of its motion.</p>

<p>From the construction of $\mathcal{H}$ we can see that $\mathcal{H}$ is circle-free.  Each section of the motion of $\mathcal{H}$ comes to an end after a finite number of steps.  For, by our assumption about $\mathcal{D}$, the decision as to whether $N$ is satisfactory is reached in a finite number of steps.  If $N$ is not satisfactory, then the $N$-th section is finished.  If $N$ is satisfactory, this means that the machine $\mathcal{M}\left(N\right)$ whose D.N is $N$ is circle-free, and therefore its $R\left(N\right)$-th figure can be calculated in a finite number of steps.  When this figure has been calculated and written down as the $R\left(N\right)$-th figure of $\beta&#39;$, the $N$-th section is finished.  Hence $\mathcal{H}$ is circle-free.</p>

<p>...</p>

<p>At this point, Turing has explicitly stated that $\mathcal{H}$ is "circle-free" and can be, and in fact is, constructed using a finite number of steps.</p>

<p>...</p>

<p>Now let $K$ be the D.N of $\mathcal{H}$.  What does $\mathcal{H}$ do in the $K$-th section of its motion?  It must test whether $K$ is satisfactory, giving a verdict "$s$" or "$u$".  Since $K$ is the D.N of $\mathcal{H}$ and since $\mathcal{H}$ is circle-free, the verdict cannot be "$u$".  On the other hand the verdict cannot be "$s$".  For if it were, then in the $K$-th section of its motion $\mathcal{H}$ would be bound to compute the first $R\left(K - 1\right) + 1 = R\left(K\right)$ figures of the sequence computed by the machine with $K$ as its D.N and to write down the $R\left(K\right)$-th as a figure of the sequence computed by $\mathcal{H}$.  The computation of the first $R\left(K\right) - 1$ figures would be carried out all right, but the instructions for calculating the $R\left(K\right)$-th would amount to "calculate the first $R\left(K\right)$ figures computed by $\mathcal{H}$ and write down the $R\left(K\right)$-th".  This $R\left(K\right)$-th figure would never be found.  <em>I.e.</em>, $\mathcal{H}$ is circular, contrary both to what we have found in the last paragraph and to the verdict "$s$".  Thus both verdicts are impossible and we conclude that there can be no machine $\mathcal{D}$.</p>

<p>...</p>

<p>And here is part of the problem- after Turing has just finished showing that $\mathcal{H}$ must be circle-free, and we are only constructing a machine made up of circle-free machines, the proof then immediately states that $\mathcal{H}$ can not be circle-free, even though we've shown that the machine we have constructed must be circle-free by definition.</p>

<p>The fact of the matter is this- the alleged issue that is being used to assert that the halting problem is undecidable has already been resolved by this point.  If it were truly a problem that would cause the Turing Machine to be "circular" it never would have been written out as a circle-free machine.  At this point we are executing the circle-free machines, so the alleged problem being discussed has already been filtered out along with all the other "circular" machines by <code>halt()</code>.  The fallacy here is "denying the antecedent".</p>

CC BY-SA 2.5
2010-12-15T21:59:22.763Z
Tim Gowers had a [post](http://gowers.wordpress.com/2010/03/28/when-is-proof-by-contradiction-necessary/) on a related question on his blog a while ago. Also see [this post](http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/) of Anrej Bauer. Note that undecidability of $H$ is usually stated negatively, i.e. $\lnot \exists A\in Algorithms \forall x. A(x) = H(x)$, but it can be stated positively as $\forall A\in Algorithms \exists x. A(x) \neq H(x)$, and the diagonalization proof gives you a (computable) function that finds an $x$ for each given algorithm $A$.
Kaveh
CC BY-SA 2.5
2010-12-15T22:03:15.287Z
The post linked by Philip seems to ask the same question so I am voting to close as exact duplicate.
Kaveh
CC BY-SA 2.5
2010-12-16T00:37:34.850Z
I don't have a problem with proof by contradiction.  I have a problem with a mathematical fallacy that masquerades as a proof by contradiction (as most mathematical fallacies tend to do).  And no, Kaveh, I am not asking the same question.  I am explicitly asking for an alternate Halting Problem proof that uses completely orthogonal means to achieve the same result.  There should be a number of different ways to show exactly the same thing if the proof is valid.
johne
CC BY-SA 2.5
2010-12-16T01:39:00.660Z
I have to agree to Philip.  Moreover, when someone claims a well-established mathematical fact to be a mathematical fallacy, it is usually because he/she just does not understand the fact or its proof.  Your case does not seem to be an exception.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T05:37:32.867Z
johne, I think that question *is* exactly asking the same thing, i.e. an alternative proof of undecidability of halting. I also agree with Tsuyoshi and in the past have seen a number of students having trouble in understanding the argument, but they are usually humbler and ask us to help them clarify their misunderstanding and don't claim that the theorem is a fallacy. This also happens a lot with Godel's incompleteness theorem. When someone claims that a well known mathematical theorem is a fallacy it is usually that person who is misunderstanding something.
Kaveh
CC BY-SA 2.5
2010-12-16T08:48:48.360Z
I'm really not seeing how there's a useful Q&A to be had here. A discussion on perceived "holes" in the Halting problem is best left to a discussion forum, not a site for clearly defined questions and answers. Closing now...
Suresh Venkat
CC BY-SA 2.5
2010-12-16T08:49:38.517Z
johne: if you're unhappy with this, the appropriate course of action is to take this up on meta.cstheory.stackexchange.com, where we *can* indulge in more discussion.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T22:41:56.930Z
johne, this site is for **research-level questions** in **theoretical computer science**, that are likely to have short well-defined answers. "Research-level" means, roughly, questions that might be discussed between two professors, or between graduate students working on Ph.D.'s, but not usually between a professor and the typical undergraduate student. It does not include questions at the level of difficulty of undergraduate homework. [Math.SE](http://math.stackexchange.com) is generally more suitable for non-research-level questions.
Kaveh
<computability><turing-machines><proofs>
Is there an alternative proof of the TM Halting Problem other than the "standard" one?
johne
# Is there an alternative proof of the TM Halting Problem other than the "standard" one?

(Asked by: username_0 on 2010-12-15)

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a specific one, I will sketch out the general outline that every proof I've seen follows (at least, I honestly don't remember one that doesn't follow this pattern):

1. Assume that there is a function `halt()` that can decide whether or not a given Turing Machine halts or not.
2. Construct a Turing Machine that embeds `halt()`, but "does the exact opposite".
3. ...
4. Proof by contradiction that because we have constructed a program that embeds `halt()`, but does the exact opposite, this proves that `halt()` can not exist.

I believe the above is "sufficiently accurate" for the purposes of this question. Please feel free to speak up if you feel it misses some nuance of the problem and / or proof.

My objection with this entire class of proofs is:

* Every formulation of the problem / proof begins by assuming that `halt()` exists and is capable of *deciding* whether or not a given Turning Machine halts or not.

At this point in the proof, there are really only two possibilities:

1. `halt()` does not, or can not, *decide* whether a Turing Machine halts or not.
2. `halt()` can, and does, *decide* whether or not a Turing Machine halts.

The problem is this: If we choose the first possibility, that is to say that for some unspecified reason `halt()` does not "work as advertised", the proof comes to an end. There is literally no point in proving `halt()` can not *decide* whether a Turing Machine halts or not if we handicap it from the start- we already know the answer.

I'm not aware of any proof that places qualifications on `halt()` at this point in the proof, therefore the only reasonable choice is the second possibility. This means that we axiomatically define `halt()` in order to "bring it in to existence". The problem with this is- `halt()` is axiomatically defined, and therefore is guaranteed to *decide* whether or a Turing Machine halts or not.

Since `halt()` is axiomatically defined as being able to *decide* whether a Turing Machine halts, any analysis that arrives at a result that contradicts this behavior ***can not***, by definition, prove that `halt()` is *undecidable*. The axiomatic definition of `halt()` is so strong that any result that causes, or results in, a contradiction of `halt()` is proof that the hypothesis is invalid. Basically, just like the first possibility, there's no point in continuing on with the proof with this choice either because we have our answer- it is impossible to prove that the Halting Problem is *undecidable* using this technique because it is axiomatically guaranteed to be *decidable*.

Therefore, I personally consider this family of Halting Problem proofs to be invalid.

So, I'm wondering if anyone is aware of a proof of the Halting Problem that is "independent" of this style and family of proof. I have a strong preference for a proof that does not rely on "diagonalization" or "recursion" in any way. My preference is for something rooted in graph theory.

Which raises a different problem: So far, I have been unable to arrive at a zero-order approximation of a Halting Problem proof using other means. In fact, every back of the envelope attempt has completely failed to arrive at the same conclusion.

The strongest one I've managed to come up with is roughly: The $\delta$ transition table is finite, with a finite number of symbols. An appeal to König's lemma seems to be enough to justify that there is no infinite path, and therefore it must be possible to find a path from the start state to a halting state, if one exists. Not intended as proof, but a result from graph theory, whatever it is, would be much stronger than the current "Say something is true, then do the exact opposite, and then claim that by doing the exact opposite of what you first claimed, you've proved that it was never true to begin with" *proof*.

Does anyone:

1. Have a Halting Problem proof that is *significantly different* than the current "standard" proof? My preference is for a proof that gives the same result using completely different techniques and / or approach. So far, I have only been able to find derivatives of the "standard" proof.
2. See a problem with the analysis above?

**edit**

@Kaveh stated `Note that undecidability of H is usually stated negatively`. To be clear, from Turings *On computable numbers, with an application to the Entscheidungsproblem* paper that established the proof:

It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable. It might, for instance, be thought that the limit of a sequence of computable numbers must be computable. This is clearly only true if the sequence of computable numbers is defined by some rule.

Or we might apply the diagonal process. "If the computable sequences are enumerable, let $a\_n$ be the $n$-th computable sequence, and let $\phi\_n\left(m\right)$ be the $m$-th figure in $a\_n$. Let $\beta$ be the sequence with $1 - \phi\_n\left(n\right)$ as its $n$-th figure. Since $\beta$ is computable, there exists a number $K$ such that $1 - \phi\_n\left(n\right) = \phi\_K\left(n\right)$ all $n$. Putting $n = K$, we have $1 = 2\phi\_K\left(K\right)$, *i.e.* $1$ is even. This is impossible. The computable sequences are therefore not enumerable".

The fallacy in this argument lies in the assumption that $\beta$ is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes $\beta$. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that "there must be something wrong". The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea "circle-free". It depends not on constructing $\beta$, but on constructing $\beta'$, whose $n$-th figure is $\phi\_n\left(n\right)$.

Let us suppose that there is such a process; that is to say, that we can invent a machine $\mathcal{D}$ which, when supplied with the S.D of any computing machine $\mathcal{M}$ will test this S.D and if $\mathcal{M}$ is circular will mark the S.D with the symbol "$u$" and if it is circle-free will mark it with "$s$". By combining the machines $\mathcal{D}$ and $\mathcal{U}$ we could construct a machine $\mathcal{M}$ to compute the sequence $\beta'$. The machine $\mathcal{D}$ may require a tape. We may suppose that it uses the $E$-squares beyond all symbols on $F$-squares, and that when it has reached its verdict all the rough work done by $\mathcal{D}$ is erased.

...

It is clear the original proof "assumes that there is a function `halt()` that can decide whether or not a given Turing Machine halts or not."

...

The machine $\mathcal{H}$ has its motion divided into sections. In the first $N - 1$ sections, among other things, the integers $1, 2, \ldots, N - 1$ have been written down and tested by the machine $\mathcal{D}$. A certain number, say $R\left(N - 1\right)$, of them have been found to be the D.N's of circle-free machines. In the $N$-th section the machine $\mathcal{D}$ tests the number $N$. If $N$ is satisfactory, *i.e.*, if it is the D.N of a circle-free machine, then $R\left(N\right) = 1 + R\left(N - 1\right)$ and the first. $R\left(N\right)$ figures of the sequence of which a D.N is $N$ are calculated. The $R\left(N\right)$-th figure of this sequence is written down as one of the figures of the sequence $\beta'$ computed by $\mathcal{H}$. If $N$ is not satisfactory, then $R\left(N\right) = R\left(N - 1\right)$ and the machine goes on to the $\left(N + 1\right)$-th section of its motion.

From the construction of $\mathcal{H}$ we can see that $\mathcal{H}$ is circle-free. Each section of the motion of $\mathcal{H}$ comes to an end after a finite number of steps. For, by our assumption about $\mathcal{D}$, the decision as to whether $N$ is satisfactory is reached in a finite number of steps. If $N$ is not satisfactory, then the $N$-th section is finished. If $N$ is satisfactory, this means that the machine $\mathcal{M}\left(N\right)$ whose D.N is $N$ is circle-free, and therefore its $R\left(N\right)$-th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the $R\left(N\right)$-th figure of $\beta'$, the $N$-th section is finished. Hence $\mathcal{H}$ is circle-free.

...

At this point, Turing has explicitly stated that $\mathcal{H}$ is "circle-free" and can be, and in fact is, constructed using a finite number of steps.

...

Now let $K$ be the D.N of $\mathcal{H}$. What does $\mathcal{H}$ do in the $K$-th section of its motion? It must test whether $K$ is satisfactory, giving a verdict "$s$" or "$u$". Since $K$ is the D.N of $\mathcal{H}$ and since $\mathcal{H}$ is circle-free, the verdict cannot be "$u$". On the other hand the verdict cannot be "$s$". For if it were, then in the $K$-th section of its motion $\mathcal{H}$ would be bound to compute the first $R\left(K - 1\right) + 1 = R\left(K\right)$ figures of the sequence computed by the machine with $K$ as its D.N and to write down the $R\left(K\right)$-th as a figure of the sequence computed by $\mathcal{H}$. The computation of the first $R\left(K\right) - 1$ figures would be carried out all right, but the instructions for calculating the $R\left(K\right)$-th would amount to "calculate the first $R\left(K\right)$ figures computed by $\mathcal{H}$ and write down the $R\left(K\right)$-th". This $R\left(K\right)$-th figure would never be found. *I.e.*, $\mathcal{H}$ is circular, contrary both to what we have found in the last paragraph and to the verdict "$s$". Thus both verdicts are impossible and we conclude that there can be no machine $\mathcal{D}$.

...

And here is part of the problem- after Turing has just finished showing that $\mathcal{H}$ must be circle-free, and we are only constructing a machine made up of circle-free machines, the proof then immediately states that $\mathcal{H}$ can not be circle-free, even though we've shown that the machine we have constructed must be circle-free by definition.

The fact of the matter is this- the alleged issue that is being used to assert that the halting problem is undecidable has already been resolved by this point. If it were truly a problem that would cause the Turing Machine to be "circular" it never would have been written out as a circle-free machine. At this point we are executing the circle-free machines, so the alleged problem being discussed has already been filtered out along with all the other "circular" machines by `halt()`. The fallacy here is "denying the antecedent".

**Tags:** computability, turing-machines, proofs
> **Comments:**
> **username_1**: Tim Gowers had a [post](http://gowers.wordpress.com/2010/03/28/when-is-proof-by-contradiction-necessary/) on a related question on his blog a while ago. Also see [this post](http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/) of Anrej Bauer. Note that undecidability of $H$ is usually stated negatively, i.e. $\lnot \exists A\in Algorithms \forall x. A(x) = H(x)$, but it can be stated positively as $\forall A\in Algorithms \exists x. A(x) \neq H(x)$, and the diagonalization proof gives you a (computable) function that finds an $x$ for each given algorithm $A$.  
> **username_1**: The post linked by Philip seems to ask the same question so I am voting to close as exact duplicate.  
> **username_0**: I don't have a problem with proof by contradiction.  I have a problem with a mathematical fallacy that masquerades as a proof by contradiction (as most mathematical fallacies tend to do).  And no, Kaveh, I am not asking the same question.  I am explicitly asking for an alternate Halting Problem proof that uses completely orthogonal means to achieve the same result.  There should be a number of different ways to show exactly the same thing if the proof is valid.  
> **username_2**: I have to agree to Philip.  Moreover, when someone claims a well-established mathematical fact to be a mathematical fallacy, it is usually because he/she just does not understand the fact or its proof.  Your case does not seem to be an exception.  
> **username_1**: johne, I think that question *is* exactly asking the same thing, i.e. an alternative proof of undecidability of halting. I also agree with Tsuyoshi and in the past have seen a number of students having trouble in understanding the argument, but they are usually humbler and ask us to help them clarify their misunderstanding and don't claim that the theorem is a fallacy. This also happens a lot with Godel's incompleteness theorem. When someone claims that a well known mathematical theorem is a fallacy it is usually that person who is misunderstanding something.  
> **username_3**: I'm really not seeing how there's a useful Q&A to be had here. A discussion on perceived "holes" in the Halting problem is best left to a discussion forum, not a site for clearly defined questions and answers. Closing now...  
> **username_3**: johne: if you're unhappy with this, the appropriate course of action is to take this up on meta.cstheory.stackexchange.com, where we *can* indulge in more discussion.  
> **username_1**: johne, this site is for **research-level questions** in **theoretical computer science**, that are likely to have short well-defined answers. "Research-level" means, roughly, questions that might be discussed between two professors, or between graduate students working on Ph.D.'s, but not usually between a professor and the typical undergraduate student. It does not include questions at the level of difficulty of undergraduate homework. [Math.SE](http://math.stackexchange.com) is generally more suitable for non-research-level questions.  

---

## 1 answers

### Answer by username_4 on 2010-12-16. Score: 4

Although your reasoning is flawed, I believe it is educational to see why. First of all, I have a rule of thumb when I am trying to prove something that seems extraordinary or difficult: "Assume that your approach is wrong and try to find out why". Arguing against yourself is not an easy task, but it is very important.

One technique I use very often is trying to apply the same argument to different situations. In other words, I'm trying to find a counterexample. Assume that your reasoning is perfect.
Then, apart from computability, you are disproving a good part of mathematic knowledge, which is based on contradiction proofs. For example, the statement that there is no natural number such that no other natural number is greater than it, uses contradiction. This result is much more intuitive than the undecidability of halting.

Perhaps the notion of contradiction could be better understood if you think of every person trying to prove a statement as a little God: Assume that you have a theory, i.e. a number of axioms and theorems. Assume also that you have a universe that instead of physical laws, obeys only this theory. Now , if you wanted to prove that statement S is false,you could work in the following way (an analogy to the physical world and a statement such as the conservation of energy is highly educational):

1. Split the original universe U into two parts, A and B, that are equal to U and obey its theory.Then make an addition that is unique to every part: Assume that in part A S holds, while in part B of the universe S is false. This is not the same as saying that S or its denial is an axiom in the respective part. It might be possible that a proof exists, however you are not aware of it (yet).
2. If S is false in both parts, then it must be also false in the whole universe. In the part B of universe that it is false (proven so by an unknown proof) you don't have to worry about it. If this argument does not sound very convincing, you can consider part B as small as you like: for example, if B consisted of only 2 atoms, you could easily verify the law of energy conservation.
3. Now, consider the part A. If you could show that A does not obey its own theory,that is the original theory and the theorem that S is true, it could not exist. However, you know that the original theory is true, therefore it must be that last theorem that does not allow part A to exist. Therefore, since part A does exist, S must be false.
4. Now you have that S is false in both parts of your universe, so it is false for the whole universe as well.

I would also highly recommend reading the following posts from Terence Tao's blog. I found them very instructive. He talks about contradiction and how to create objects that are so powerful, that contradict their own existence:

[The “no self-defeating object” argument](http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/)

[The “no self-defeating object” argument, revisited](http://terrytao.wordpress.com/2010/10/18/the-no-self-defeating-object-argument-revisited/)

[The “no self-defeating object” argument, and the vagueness paradox](http://terrytao.wordpress.com/2010/11/02/the-no-self-defeating-object-argument-and-the-vagueness-paradox/)

> **Comments:**
> **username_0**: Look, there is nothing wrong with the "proof by contradiction" technique, nor am I claiming that.  I **am** claiming that there is a serious problem with the way that the technique has been employed in Turings proof.  The proof forms a series of "if / then" conditionals and then uses "Denying the antecedent" to form the contradiction.  But due to the conditional chaining, it is not possible to get to `halt()` is "undecidable" without first explicitly passing through `halt()` is "decidable" for the very case being reasoned about.  
> **username_5**: @johne I can't understand how your criticism doesn't hold for proofs by contradiction in general. The halting proof is trying to show $\neg\exists M$ s.t $L(M)=H$, so it proceeds by assuming $\exists M$ s.t. $L(M)=H$. It then shows that in fact $L(M)\neq H$. From this we conclude that our assumption of $\exists M$ s.t. $L(M)=H$ is flawed. Thus, classically, we can conclude that $\neg\exists M$ s.t. $L(M)=H$. Where in there do you have a problem?  
> **username_0**: In the proof given by Turing, it's not a question of "If this is true, then it would imply.."  The way the proof is constructed is that `halt()` MUST have been decidable at some point in the past and at the point of contradiction it has become undecidable for a case that we could have reached if, and only if, `halt()` was decidable in the past for this specific case.  The fact that "for some reason" it is undecidable now can not change the fact that it was decidable in this results causal past.  
> **username_5**: @johne Mathematical proofs do not deal with "time" in that way. Proof and truth are time invariant. It's not showing that halt() "becomes" undecidable. It's showing that if we think we have a TM that solves the halting problem, then we can always break it. So, it must be the case that we don't have a TM that solves the halting problem.  
> **username_0**: @mark: Because the proof given by Turing "shows that in fact $L(M) \ne H$" by explicitly, conditionally, and causally requiring $L(M)=H$ to be true in order to show "$L(M) \ne H$". But it's not $L(M) \ne H$ that is proven, it must be $\lnot(L(M)=H)$, because thats what was true in the past.  These are two radically different things: $\lnot(L(M)=H)$ means it is still possible to decide the Halting Problem, the fact that you ignored or negated the result does not, and can not, change that fact.  
> **username_5**: @johne You are missing quantifiers. $L(M) \neq H$ is the same as $\neg(L(M) = H)$. This might be the root of the problem. Turing's proof assumes $\exists M.~L(M)=H$, derives a contradiction, and concludes $\neg\exists M. ~L(M)=H$. IOW, there is NO TM that decides the halting problem. Therefore, it is undecidable.  
> **username_4**: I believe the following excerpt from Tao's blog could be used for a contraposition proof: "suppose that all statements in a suitably strong and consistent logical system were either provable or disprovable. Then one could build a program that determined whether an input string {S}, when run as a program, halts in finite time, simply by searching for all proofs or disproofs of the statement “{S} halts in finite time”; this program is guaranteed to terminate with a correct answer by hypothesis."  
> **username_0**: @mark Ok.  The $\delta$ transition function for a TM is a fixed number of finite states with a fixed finite number of symbols.  This can be mapped to the Boolean domain, and we can use Boolean algebra to decide `halt()`.  In this case, it is impossible for the Boolean algebra to be undecidable.  Additionally, König's lemma says that $\delta$, which is completely finite, can not have an infinite acyclic path- therefore, König's lemma says that the halting problem must be decidable.  So which "Proof by contradiction" is going to take precedence here?  
> **username_5**: @johne That "proof" doesn't make sense. How do you get from a finite state controller to using Boolean algebra to "decide" the halting problem? TM have an infinite tape, so the full state of the TM is much more than just the finite controller. It's almost trivial that a TM either halts or its finite state controller loops. How do you get from there to an algorithm that decides the halting problem? What is the actual algorithm?  
> **username_0**: @mark Simple: [CMOS boolean logic](http://www.ece.virginia.edu/~mrs8n/cadence/SynthesisTutorials/tsmc18.pdf). In fact, I can probably crank off a simple TM in Verilog in about an hour and synthesize an FPGA / ASIC with a "tape" port that has {symbol, r/w, l/r, etc}. Boolean algebra? No problem.  As for a TM and state, the tape is irrelevant- the $\delta$ transition table contains everything you need to enumerate all of the finitely possible acyclic path permutations that the tape could ever cause $\delta$ to transition through.  
> **username_5**: @johne The tape is precisely the difference between a TM and an FSM. You can have a TM whose controller loops, yet it halts. You seem to think that the halting problem boils down to determining whether the controller loops. It doesn't. That is necessary, but far from sufficient for a TM not to halt.  

---

