<p>I think I might understand what the asker is asking about. I don't think that he objects to proofs by contradiction in general. Rather, I've interpreted his various recent statements as an objection to proofs by contradiction of the following form:</p>

<ol>
<li>Assume the existence of an object $A$ with property $P$.</li>
<li>Through a sequence of deductions, we determine that $A$ does not possess property $P$.</li>
<li>Thus, we conclude that no object exists with property $P$.</li>
</ol>

<p>I would point out that such proofs by contradiction are completely standard throughout all of mathematics, not just in theoretical computer science. But, never mind that for now. </p>

<p>I think the exposition in Chapter 8 of <a href="http://rads.stackoverflow.com/amzn/click/0321462254" rel="nofollow">Hopcroft &amp; Ullman</a> just might avoid the asker's objections. It proceeds as follows:</p>

<ol>
<li>Construct a language $L_d$ that is not accepted by any Turing machine. Of course, such languages must exist by the pigeon-hole principle. In this proof, $L_d$ is constructed explicitly. </li>
<li>Show that if $L_d$ is not accepted by any Turing machine, neither is its complement $\overline{L_d}$. This a fairly obvious observation given the mechanics of a Turing machine.</li>
<li>In the book, they define the language $L_u$ consisting of all strings which encode a pair $(M, w)$ where $M$ is a Turing machine and $x$ is an input string such that $M$ accepts $x$. For our purposes, we can define $L_h$ in a similar way except we require merely that $M$ halts on $x$ (not necessarily in an accepting state). </li>
<li>Show that if there exists an algorithm to decide membership in $L_h$, we can construct a Turing machine that accepts $\overline{L_d}$ (as defined above). Note that $L_d$ was constructed completely independently of $L_h$ and has nothing to do with $L_h$. </li>
<li>Since $\overline{L_d}$ was constructed so that no Turing machine could accept it, we conclude that there does not exist an algorithm to decide $L_h$. </li>
</ol>

CC BY-SA 2.5
2010-12-17T03:26:14.133Z
@mhum Thank you for a genuine attempt at answering my question.  My objection to your proposal lies with step 1.  For my purposes, Shannons [*The Synthesis of Two-Terminal Switching Circuits*](http://bstj.bell-labs.com/BSTJ/images/Vol28/bstj28-1-59.pdf) ~$2^n/n$ result says that every $L_d$ language is accepted and is decidable.  This is also one of the reasons why an appeal to diagonalization is unlikely to work. It puts me in a pickle (relative to Turings proof). But I do appreciate the attempt!
johne
CC BY-SA 2.5
2010-12-17T04:50:39.677Z
@johne There is a difference between circuits and TMs. In particular, a TM corresponds to a circuit family, not just a single circuit. The family has a circuit for each size of input. The existence of a circuit family doesn't imply decidability of the language. In this realm, you need an additional uniformity requirement. That is, given just the input size, I can computably construct the circuit for that input. Shannon's result is talking about arbitrary, non-uniform circuits. Not uniform circuit families.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:32:11.683Z
@johne: As Mark says, the Shannon paper deals in a non-uniform computation model. Informally, this means that for each input length you can create a different computing device (i.e.: a circuit with one input wire, a different circuit for two input wires, etc...). This model is most naturally found in circuit-style models. Decidability is defined vis-a-vis a uniform computation model, specifically Turing machines. Again informally, you only get to pick one computing device (i.e.: TM) that must process inputs of all lengths. Non-uniform is usually (always?) more powerful than uniform.
mhum
CC BY-SA 2.5
2010-12-17T05:36:35.203Z
Furthermore, the pigeon-hole principle proves that there must exist non-decidable languages -- diagonalization is not required. There are a countable number of Turing machines but an uncountable number of languages. Hence, there must be some languages that do not correspond to any TM. On the other hand, there are an uncountable number of families of circuits. Thus, there is no contradiction in the fact that every language can be recognized by some family of circuit.
mhum
CC BY-SA 2.5
2010-12-17T06:44:00.670Z
@mhum (this may take more than one attempt) I understand the point you're making.  However, the concept of "Turing Completeness" implies that a modern CPU is "equivalent" (for some definition of equivalent) to a Turing Machine.  Is a 4-bit RISCy CPU Turing Complete.  I think most would say yes.  At what point does a circuit transition from non-uniform to uniform?  Is a "sea of gates" that is on-the-fly reconfigurable (i.e., FPGA) uniform or non-uniform?  What if the calculation mutates the gate interconnection during the calculation?
johne
CC BY-SA 2.5
2010-12-17T06:50:45.247Z
@johne A CPU is "Turing Complete" if you attach it to an infinite tape (or HD), yes. But that's not what we mean by a circuit, formally. A boolean circuit is a graph of gates with $n$ designated input wires, and a single output wire. So, to emulate a TM, which computes over arbitrary input, you need arbitrarily many circuits, one for each input size. The Sipser book I alluded to earlier covers this.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T06:53:20.813Z
@johne A circuit isn't "non-uniform", an infinite circuit family is. An FPGA can only have finite gates, so it can only represent at most finitely many circuits. A CPU/FPGA maps to the finite state controller in a TM. A CPU by itself without an (infinite) tape isn't equivalent to a TM.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T07:20:46.100Z
@johne One must differentiate between formal models of computation and physical manifestations of computation. Any physical computer is finite and thus must have a bounded number of possible states. Due to its unbounded tape, a Turing machine system has infinite possible states. However, just because a physical computer isn't actually a TM does not mean that the TM formalism is useless. Remember that this is a *model* of computation. And, as they say, all models are wrong, but some models are useful.
mhum
CC BY-SA 2.5
2010-12-17T07:24:31.243Z
@johne Similarly, even though a physical computer is composed of physical circuits, and though it can process inputs of variable length, it alone does not comprise a complete circuit *family* under the circuit model of computation. A circuit family would define the behaviour of the system for *all* input lengths. Any physical computer has some upper bound on the size of the input length it can process, again due to finiteness of the physical world.
mhum
CC BY-SA 2.5
2010-12-17T15:49:10.390Z
Also, I should be more precise: When I said that a TM has "infinite possible states", I should have said that it has infinite possible *configurations* where a configuration is a combination of the internal state of the TM and the sequence of symbols on the tape. By definition, there are only a finite number of possibilities for the former but infinitely many possibilities for the latter.
mhum
CC BY-SA 2.5
2010-12-17T01:15:31.743Z
2010-12-17T01:28:38.320Z
2010-12-17T01:28:38.320Z
mhum
<p>I am asking this question again.  I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me.</p>

<p>I am looking for a TM Halting Problem proof that does not have the following properties:</p>

<ul>
<li>Uses diagonalization.</li>
<li>Uses recursion.</li>
<li>Uses "self reference".</li>
<li>Relies on "running" the Turing Machine.  Specifically, there is a distinction between "analyzing a Turing Machine" to determine if it has a certain property and "running / simulating" a Turing Machine to see if it exhibits a certain property.  It should go without saying that a HALTing function that determines whether or not a given Turing Machine halts by simulating it and "waiting until it halts / returns" is not the only way to determine whether or not a Turing Machine halts.</li>
<li>Uses "proof by contradiction", although this is extremely context dependent.  My main concern is with a "proof by contradiction" that is "self referential" such that it forms a key part of the proof that can not be separated from the proof without causing the result to collapse.  I understand you may not understand or agree with my reasoning, but for my purposes a proof that did not use this technique would greatly simplify things.</li>
</ul>

<p>Ideally, the proof would have the following properties:</p>

<ul>
<li>Use technique such as exhaustively enumerative, pigeon hole, double count, etc.</li>
<li>Uses a different branch of mathematics to achieve the same result, i.e. graph theory, combinatorics, etc.</li>
<li>Still applies when reduced to the "Boolean domain" (i.e., a turing machine built using just 2 input, 1 output NAND gates (i.e., a computer) exhibits the same problem).  Specifically, the result can not contradict the fact that Boolean algebras have been proven to be decidable, and every $n$-bit Boolean $L$ can be shown to be decided by a bounded by a number of {AND, OR, NOT} gates (via Shannons <em>The synthesis of two-terminal switching circuits</em>).</li>
</ul>

<p>I have spent quite a bit of time looking for alternate formulations of the Halting Problem that are not just simple permutations of the original proof given by Turing.</p>

<p><strong>Question:</strong> Can you point me to a vetted proof of the Halting Problem that shares as absolutely as little in common with the one given by Turing?</p>

<p><em><strong>Please</em></strong>, instead of arguing with me as to whether or not my reasons are valid, or that I "don't get it and should just accept the proof given by Turing", it would be a great help to me and possibly someone else if you could simply help me <em>locate an alternate proof</em>.  Yes, I am looking for proofs with certain properties, properties that inconveniently cull a number of candidates.  Despite this, they are properties that I unfortunately need.</p>

CC BY-SA 2.5
2010-12-16T23:12:06.683Z
I see you are serious at asking this question! To lower the chance of getting it closed as exact duplicate, you can refer to other posts which have asked the same thing, but without these limitations.
Sadeq Dousti
CC BY-SA 2.5
2010-12-16T23:19:01.513Z
possible duplicate of [Is there an alternative proof of the TM Halting Problem other than the "standard" one?](http://cstheory.stackexchange.com/questions/3810/is-there-an-alternative-proof-of-the-tm-halting-problem-other-than-the-standard)
Kaveh
CC BY-SA 2.5
2010-12-16T23:23:34.460Z
You should not repost a closed question. Edit the previous one and flag it for moderator attention after the edit and it will be reopen when it becomes suitable for the site (as stated by one of the moderators under your previous post, and you can use meta to argue about the decision). That is the procedure that you should follow, not reposting your question once more, so I am voting to close as exact duplicate.
Kaveh
CC BY-SA 2.5
2010-12-16T23:29:19.657Z
"a turing machine built using just 2 input, 1 output NAND gates" This doesn't make sense to me. A TM has an infinite read-write tape. You can build the controller using finite logic of course, but the entire TM can't be built using a finite number of gates.
Mark Reitblatt
CC BY-SA 2.5
2010-12-16T23:35:27.000Z
Did you take a look at this answer http://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-depe/2854#2854  It references the Low Basis theorem which is a consequence of Koenig's Lemma, which I see appealed to you previously.
mhum
CC BY-SA 2.5
2010-12-17T04:25:20.067Z
You say *It should go without saying that a HALTing function that determines whether or not a given Turing Machine halts by simulating it and "waiting until it halts / returns" is not the only way to determine whether or not a Turing Machine halts.* A lot of computer scientists would disagree with you about this. How else can we tell whether a general Turing Machine halts?
Peter Shor 
CC BY-SA 2.5
2010-12-17T04:37:01.533Z
@mhum: Yes, but... it's very complicated.  This does not directly answer your question, but a [Toffoli gate](http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf) is "universal" (a complete boolean basis) that is invertible.  Which raises secondary questions such as "Are one way functions possible if there exists the possibility that the function can be implemented with Toffoli gates?"  It just gets more complicated from there (i.e., thermodynamics). The link contains some info on "reversible Turing Machines" as well.
johne
CC BY-SA 2.5
2010-12-17T04:40:56.053Z
@Peter There are analyses that can decide termination for certain classes of programs. It's not clear prima facie that you can't do this for all programs. He's just pointing out that assumptions on how the hypothetical decider operates are unsound. It's a bit of a strawman, since the standard proof makes no such assumption.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T04:41:40.267Z
@peter:  A $\delta$ transition table is a directed graph, is it not?  Is it not reasonable to assume that one can use graph theory to analyze the $\delta$ transition table to determine if a path exists from $q_0$ to a $q_{halt}$ state?
johne
CC BY-SA 2.5
2010-12-17T04:46:41.163Z
@johne That's not sound. For any non-halting TM M, I can give you a TM M' that loops on the same inputs, yet has a path from the initial state to the halting state. Just add a new symbol Z to the alphabet, add a transition from every state to q_halt if you read Z. Now, just don't ever write Z. Every input that made M loop now makes M' loop. You seem very hung up on the TM controller. The power of a TM comes from the tape, not the controller.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T04:58:10.917Z
@Mark When you say "standard proof makes no such assumption", could you clarify?  I just re-read Turings proof to check, but I think it does, but it is somewhat ambiguous (the nomenclature has very clearly changed).  I think my first impression is correct, but I would be willing to concede this point.  However, the proof given by Hopcroft (ch.8, 2nd ed) very clearly does.
johne
CC BY-SA 2.5
2010-12-17T05:06:43.027Z
@johne I don't have a copy of Hopcroft handy, but the proof on wikipedia seems to be the "standard proof". Note that they make no assumption about $f$ other than being a total, computable function.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:08:27.300Z
@mark: Yes, but the input for the Turing Machine on the tape is fixed and finite at the start of $q_0$.  Therefore it is possible to scan the finite number of input symbols, check if it contains $Z$.  Then, check if $\delta$ ever writes $Z$ to the tape.  Therefore, it is possible to decide "It is possible for $M'$ to halt, but given this input, it will not.  In order for $M'$ to halt, the following conditions must be met..." (from Cook "Initially, a finite input string over $\Sigma$ is written on adjacent squares of the tape, all other squares are blank (contain $b$)")
johne
CC BY-SA 2.5
2010-12-17T05:19:59.500Z
@johne The point was that reachability in the control graph is not the same thing as termination. So, given an arbitrary TM, how are you going to decide if it halts? Looking at the control graph alone is not enough, as I just pointed out. There's an infinite number of such tricks.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:21:14.880Z
@mark: The proof given at Wikipedia uses `undefined`. I completely understand what the author *wants* to mean.  My "devils advocate" question is "Does it really mean this?  Is it fundamentally impossible, not just axiomatically by assumption, to show that the authors intended meaning of `undefined` is valid under all conditions?"  The entire proof rests entirely on what `undefined` pedantically means and no definition for `undefined` is given.  Break this assumption and this proof folds.
johne
CC BY-SA 2.5
2010-12-17T05:29:19.113Z
@johne Your code is broken. At any rate, that seems a very pedantic and ultimately irrelevant criticism. No, the wikipedia proof is not 100% formal. There are 100% formal proofs. In fact, there are many of them.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:31:35.367Z
@mark Why do you say "reachability in the control graph is not the same thing as termination."  If it halts, there is clearly a path from $q_0$ to $q_{halt}$, which is the very definition of reachability.  If you can show that there is no path from $q_0$ to $q_{halt}$, then you've shown that $M$ will not halt.  The finite number of states in $\delta$ guarantees that there are only a finite number of acyclic path permutations.  Once you have the set of $q_{halt}$ paths, you can use the finite input to cull this set.  Graph theory provides a number of powerful techniques for just this problem.
johne
CC BY-SA 2.5
2010-12-17T05:32:48.533Z
@johne Quite frankly, I don't think this is going anywhere. You seem to be laboring under some severe misunderstandings, and are showing a complete unwillingness to admit them. If you really want to understand the undecidability of the halting problem, I suggest reading Sipser until it makes sense. Because the theorem is correct. If you think the result is wrong, then you need to go back and think until you see why you are in fact wrong.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:34:40.357Z
@johne How are you going to "cull" that finite set other than running the machine?
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T05:41:38.273Z
@mark: The criticism is relative.  For example, in the VLSI / ASIC industry, it costs \$50 million for a set of masks on a modern lithography node.  A typo and / or "bug" represents.... another \$50 million dollars for a corrected set of masks.  \$50 million tends to make "very pedantic" in to "extremely important".  And airplanes.  And nuclear power plants.  And software [when it can kill you](http://en.wikipedia.org/wiki/Therac-25).
johne
CC BY-SA 2.5
2010-12-17T05:44:54.353Z
@johne That's nice, but it has nothing to do with anything. And since you seem to have a thing for EE, I should point out that before starting a PhD in CS, I worked for Intel on a HW FV team. I'm very well aware of what formal means. And it has nothing to do with this.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T06:07:37.963Z
@mark Just how much programming have you actually done?  I mean, I've built CPU's.  I've written C compilers for said CPUs. I've written stuff like [lockless, concurrent multi-reader, multi-writer hash tables](http://transactionkit.sourceforge.net/).  I believe my decades of experience are sufficient to judge whether or not applying trivial graph analysis operations to the problem is possible or not.  `You seem to be laboring under some severe misunderstandings, and are showing a complete unwillingness to admit them.`  I'm not agreeing with you, therefore I'm wrong?  Lovely.
johne
CC BY-SA 2.5
2010-12-17T06:24:19.867Z
@phillip I agree, but my request is still reasonable and valid.  With all due respect, your observation goes both ways (and not necessarily to you).  The behavior of some of the people in this group has been nothing short of amazing.  Instead of helping me find a vetted proof with certain qualities, people seem compelled to explain how wrong I am.  Fine, then it should be trivial to find a vetted proof that is "different" than the one Turing gave.  Problem solved.  Multiple, independent proofs are healthy.  A single, unchallengeable proof is religion.
johne
CC BY-SA 2.5
2010-12-17T06:29:46.070Z
@johne We have given you multiple proofs. mhum has one below. The question linked earlier has at least 2 more different proofs. One of which doesn't use diagonalization. There are multiple proofs. If you don't understand them, fine. But don't pretend we haven't bent over backwards to meet your requests.
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T06:33:10.407Z
johne: I closed the previous question, and am not sure that this question deserves to survive. Having said that, mhum has tried to interpret what your question might be looking for. rather than doing battle in the comments here, it might be better to focus on the specific issues mhum has raised and address them there. If this comment thread continues to veer towards the personal, I'll have to shut it down again.
Suresh Venkat
CC BY-SA 2.5
2010-12-17T06:59:51.517Z
metadiscussion here: http://meta.cstheory.stackexchange.com/questions/826/dealing-with-user-issue
Suresh Venkat
<computability><turing-machines><proofs><halting-problem>
Alternative Turing Machine Proofs
johne
# Alternative Turing Machine Proofs

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

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me.

I am looking for a TM Halting Problem proof that does not have the following properties:

* Uses diagonalization.
* Uses recursion.
* Uses "self reference".
* Relies on "running" the Turing Machine. Specifically, there is a distinction between "analyzing a Turing Machine" to determine if it has a certain property and "running / simulating" a Turing Machine to see if it exhibits a certain property. It should go without saying that a HALTing function that determines whether or not a given Turing Machine halts by simulating it and "waiting until it halts / returns" is not the only way to determine whether or not a Turing Machine halts.
* Uses "proof by contradiction", although this is extremely context dependent. My main concern is with a "proof by contradiction" that is "self referential" such that it forms a key part of the proof that can not be separated from the proof without causing the result to collapse. I understand you may not understand or agree with my reasoning, but for my purposes a proof that did not use this technique would greatly simplify things.

Ideally, the proof would have the following properties:

* Use technique such as exhaustively enumerative, pigeon hole, double count, etc.
* Uses a different branch of mathematics to achieve the same result, i.e. graph theory, combinatorics, etc.
* Still applies when reduced to the "Boolean domain" (i.e., a turing machine built using just 2 input, 1 output NAND gates (i.e., a computer) exhibits the same problem). Specifically, the result can not contradict the fact that Boolean algebras have been proven to be decidable, and every $n$-bit Boolean $L$ can be shown to be decided by a bounded by a number of {AND, OR, NOT} gates (via Shannons *The synthesis of two-terminal switching circuits*).

I have spent quite a bit of time looking for alternate formulations of the Halting Problem that are not just simple permutations of the original proof given by Turing.

**Question:** Can you point me to a vetted proof of the Halting Problem that shares as absolutely as little in common with the one given by Turing?

***Please***, instead of arguing with me as to whether or not my reasons are valid, or that I "don't get it and should just accept the proof given by Turing", it would be a great help to me and possibly someone else if you could simply help me *locate an alternate proof*. Yes, I am looking for proofs with certain properties, properties that inconveniently cull a number of candidates. Despite this, they are properties that I unfortunately need.

**Tags:** computability, turing-machines, proofs, halting-problem

> **Comments:**
> **username_1**: I see you are serious at asking this question! To lower the chance of getting it closed as exact duplicate, you can refer to other posts which have asked the same thing, but without these limitations.  
> **username_2**: possible duplicate of [Is there an alternative proof of the TM Halting Problem other than the "standard" one?](http://cstheory.stackexchange.com/questions/3810/is-there-an-alternative-proof-of-the-tm-halting-problem-other-than-the-standard)  
> **username_2**: You should not repost a closed question. Edit the previous one and flag it for moderator attention after the edit and it will be reopen when it becomes suitable for the site (as stated by one of the moderators under your previous post, and you can use meta to argue about the decision). That is the procedure that you should follow, not reposting your question once more, so I am voting to close as exact duplicate.  
> **username_3**: "a turing machine built using just 2 input, 1 output NAND gates" This doesn't make sense to me. A TM has an infinite read-write tape. You can build the controller using finite logic of course, but the entire TM can't be built using a finite number of gates.  
> **username_4**: Did you take a look at this answer http://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-depe/2854#2854  It references the Low Basis theorem which is a consequence of Koenig's Lemma, which I see appealed to you previously.  
> **username_5**: You say *It should go without saying that a HALTing function that determines whether or not a given Turing Machine halts by simulating it and "waiting until it halts / returns" is not the only way to determine whether or not a Turing Machine halts.* A lot of computer scientists would disagree with you about this. How else can we tell whether a general Turing Machine halts?  
> **username_0**: @username_4: Yes, but... it's very complicated.  This does not directly answer your question, but a [Toffoli gate](http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf) is "universal" (a complete boolean basis) that is invertible.  Which raises secondary questions such as "Are one way functions possible if there exists the possibility that the function can be implemented with Toffoli gates?"  It just gets more complicated from there (i.e., thermodynamics). The link contains some info on "reversible Turing Machines" as well.  
> **username_3**: @Peter There are analyses that can decide termination for certain classes of programs. It's not clear prima facie that you can't do this for all programs. He's just pointing out that assumptions on how the hypothetical decider operates are unsound. It's a bit of a strawman, since the standard proof makes no such assumption.  
> **username_0**: @peter:  A $\delta$ transition table is a directed graph, is it not?  Is it not reasonable to assume that one can use graph theory to analyze the $\delta$ transition table to determine if a path exists from $q_0$ to a $q_{halt}$ state?  
> **username_3**: @username_0 That's not sound. For any non-halting TM M, I can give you a TM M' that loops on the same inputs, yet has a path from the initial state to the halting state. Just add a new symbol Z to the alphabet, add a transition from every state to q_halt if you read Z. Now, just don't ever write Z. Every input that made M loop now makes M' loop. You seem very hung up on the TM controller. The power of a TM comes from the tape, not the controller.  
> **username_0**: @Mark When you say "standard proof makes no such assumption", could you clarify?  I just re-read Turings proof to check, but I think it does, but it is somewhat ambiguous (the nomenclature has very clearly changed).  I think my first impression is correct, but I would be willing to concede this point.  However, the proof given by Hopcroft (ch.8, 2nd ed) very clearly does.  
> **username_3**: @username_0 I don't have a copy of Hopcroft handy, but the proof on wikipedia seems to be the "standard proof". Note that they make no assumption about $f$ other than being a total, computable function.  
> **username_0**: @mark: Yes, but the input for the Turing Machine on the tape is fixed and finite at the start of $q_0$.  Therefore it is possible to scan the finite number of input symbols, check if it contains $Z$.  Then, check if $\delta$ ever writes $Z$ to the tape.  Therefore, it is possible to decide "It is possible for $M'$ to halt, but given this input, it will not.  In order for $M'$ to halt, the following conditions must be met..." (from Cook "Initially, a finite input string over $\Sigma$ is written on adjacent squares of the tape, all other squares are blank (contain $b$)")  
> **username_3**: @username_0 The point was that reachability in the control graph is not the same thing as termination. So, given an arbitrary TM, how are you going to decide if it halts? Looking at the control graph alone is not enough, as I just pointed out. There's an infinite number of such tricks.  
> **username_0**: @mark: The proof given at Wikipedia uses `undefined`. I completely understand what the author *wants* to mean.  My "devils advocate" question is "Does it really mean this?  Is it fundamentally impossible, not just axiomatically by assumption, to show that the authors intended meaning of `undefined` is valid under all conditions?"  The entire proof rests entirely on what `undefined` pedantically means and no definition for `undefined` is given.  Break this assumption and this proof folds.  
> **username_3**: @username_0 Your code is broken. At any rate, that seems a very pedantic and ultimately irrelevant criticism. No, the wikipedia proof is not 100% formal. There are 100% formal proofs. In fact, there are many of them.  
> **username_0**: @mark Why do you say "reachability in the control graph is not the same thing as termination."  If it halts, there is clearly a path from $q_0$ to $q_{halt}$, which is the very definition of reachability.  If you can show that there is no path from $q_0$ to $q_{halt}$, then you've shown that $M$ will not halt.  The finite number of states in $\delta$ guarantees that there are only a finite number of acyclic path permutations.  Once you have the set of $q_{halt}$ paths, you can use the finite input to cull this set.  Graph theory provides a number of powerful techniques for just this problem.  
> **username_3**: @username_0 Quite frankly, I don't think this is going anywhere. You seem to be laboring under some severe misunderstandings, and are showing a complete unwillingness to admit them. If you really want to understand the undecidability of the halting problem, I suggest reading Sipser until it makes sense. Because the theorem is correct. If you think the result is wrong, then you need to go back and think until you see why you are in fact wrong.  
> **username_3**: @username_0 How are you going to "cull" that finite set other than running the machine?  
> **username_0**: @mark: The criticism is relative.  For example, in the VLSI / ASIC industry, it costs \$50 million for a set of masks on a modern lithography node.  A typo and / or "bug" represents.... another \$50 million dollars for a corrected set of masks.  \$50 million tends to make "very pedantic" in to "extremely important".  And airplanes.  And nuclear power plants.  And software [when it can kill you](http://en.wikipedia.org/wiki/Therac-25).  
> **username_3**: @username_0 That's nice, but it has nothing to do with anything. And since you seem to have a thing for EE, I should point out that before starting a PhD in CS, I worked for Intel on a HW FV team. I'm very well aware of what formal means. And it has nothing to do with this.  
> **username_0**: @mark Just how much programming have you actually done?  I mean, I've built CPU's.  I've written C compilers for said CPUs. I've written stuff like [lockless, concurrent multi-reader, multi-writer hash tables](http://transactionkit.sourceforge.net/).  I believe my decades of experience are sufficient to judge whether or not applying trivial graph analysis operations to the problem is possible or not.  `You seem to be laboring under some severe misunderstandings, and are showing a complete unwillingness to admit them.`  I'm not agreeing with you, therefore I'm wrong?  Lovely.  
> **username_0**: @phillip I agree, but my request is still reasonable and valid.  With all due respect, your observation goes both ways (and not necessarily to you).  The behavior of some of the people in this group has been nothing short of amazing.  Instead of helping me find a vetted proof with certain qualities, people seem compelled to explain how wrong I am.  Fine, then it should be trivial to find a vetted proof that is "different" than the one Turing gave.  Problem solved.  Multiple, independent proofs are healthy.  A single, unchallengeable proof is religion.  
> **username_3**: @username_0 We have given you multiple proofs. username_4 has one below. The question linked earlier has at least 2 more different proofs. One of which doesn't use diagonalization. There are multiple proofs. If you don't understand them, fine. But don't pretend we haven't bent over backwards to meet your requests.  
> **username_6**: username_0: I closed the previous question, and am not sure that this question deserves to survive. Having said that, username_4 has tried to interpret what your question might be looking for. rather than doing battle in the comments here, it might be better to focus on the specific issues username_4 has raised and address them there. If this comment thread continues to veer towards the personal, I'll have to shut it down again.  
> **username_6**: metadiscussion here: http://meta.cstheory.stackexchange.com/questions/826/dealing-with-user-issue  

---

## 1 answers

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

I think I might understand what the asker is asking about. I don't think that he objects to proofs by contradiction in general. Rather, I've interpreted his various recent statements as an objection to proofs by contradiction of the following form:

1. Assume the existence of an object $A$ with property $P$.
2. Through a sequence of deductions, we determine that $A$ does not possess property $P$.
3. Thus, we conclude that no object exists with property $P$.

I would point out that such proofs by contradiction are completely standard throughout all of mathematics, not just in theoretical computer science. But, never mind that for now.

I think the exposition in Chapter 8 of [Hopcroft & Ullman](http://rads.stackoverflow.com/amzn/click/0321462254) just might avoid the asker's objections. It proceeds as follows:

1. Construct a language $L\_d$ that is not accepted by any Turing machine. Of course, such languages must exist by the pigeon-hole principle. In this proof, $L\_d$ is constructed explicitly.
2. Show that if $L\_d$ is not accepted by any Turing machine, neither is its complement $\overline{L\_d}$. This a fairly obvious observation given the mechanics of a Turing machine.
3. In the book, they define the language $L\_u$ consisting of all strings which encode a pair $(M, w)$ where $M$ is a Turing machine and $x$ is an input string such that $M$ accepts $x$. For our purposes, we can define $L\_h$ in a similar way except we require merely that $M$ halts on $x$ (not necessarily in an accepting state).
4. Show that if there exists an algorithm to decide membership in $L\_h$, we can construct a Turing machine that accepts $\overline{L\_d}$ (as defined above). Note that $L\_d$ was constructed completely independently of $L\_h$ and has nothing to do with $L\_h$.
5. Since $\overline{L\_d}$ was constructed so that no Turing machine could accept it, we conclude that there does not exist an algorithm to decide $L\_h$.

> **Comments:**
> **username_0**: @username_4 Thank you for a genuine attempt at answering my question.  My objection to your proposal lies with step 1.  For my purposes, Shannons [*The Synthesis of Two-Terminal Switching Circuits*](http://bstj.bell-labs.com/BSTJ/images/Vol28/bstj28-1-59.pdf) ~$2^n/n$ result says that every $L_d$ language is accepted and is decidable.  This is also one of the reasons why an appeal to diagonalization is unlikely to work. It puts me in a pickle (relative to Turings proof). But I do appreciate the attempt!  
> **username_3**: @username_0 There is a difference between circuits and TMs. In particular, a TM corresponds to a circuit family, not just a single circuit. The family has a circuit for each size of input. The existence of a circuit family doesn't imply decidability of the language. In this realm, you need an additional uniformity requirement. That is, given just the input size, I can computably construct the circuit for that input. Shannon's result is talking about arbitrary, non-uniform circuits. Not uniform circuit families.  
> **username_4**: @username_0: As Mark says, the Shannon paper deals in a non-uniform computation model. Informally, this means that for each input length you can create a different computing device (i.e.: a circuit with one input wire, a different circuit for two input wires, etc...). This model is most naturally found in circuit-style models. Decidability is defined vis-a-vis a uniform computation model, specifically Turing machines. Again informally, you only get to pick one computing device (i.e.: TM) that must process inputs of all lengths. Non-uniform is usually (always?) more powerful than uniform.  
> **username_4**: Furthermore, the pigeon-hole principle proves that there must exist non-decidable languages -- diagonalization is not required. There are a countable number of Turing machines but an uncountable number of languages. Hence, there must be some languages that do not correspond to any TM. On the other hand, there are an uncountable number of families of circuits. Thus, there is no contradiction in the fact that every language can be recognized by some family of circuit.  
> **username_0**: @username_4 (this may take more than one attempt) I understand the point you're making.  However, the concept of "Turing Completeness" implies that a modern CPU is "equivalent" (for some definition of equivalent) to a Turing Machine.  Is a 4-bit RISCy CPU Turing Complete.  I think most would say yes.  At what point does a circuit transition from non-uniform to uniform?  Is a "sea of gates" that is on-the-fly reconfigurable (i.e., FPGA) uniform or non-uniform?  What if the calculation mutates the gate interconnection during the calculation?  
> **username_3**: @username_0 A CPU is "Turing Complete" if you attach it to an infinite tape (or HD), yes. But that's not what we mean by a circuit, formally. A boolean circuit is a graph of gates with $n$ designated input wires, and a single output wire. So, to emulate a TM, which computes over arbitrary input, you need arbitrarily many circuits, one for each input size. The Sipser book I alluded to earlier covers this.  
> **username_3**: @username_0 A circuit isn't "non-uniform", an infinite circuit family is. An FPGA can only have finite gates, so it can only represent at most finitely many circuits. A CPU/FPGA maps to the finite state controller in a TM. A CPU by itself without an (infinite) tape isn't equivalent to a TM.  
> **username_4**: @username_0 One must differentiate between formal models of computation and physical manifestations of computation. Any physical computer is finite and thus must have a bounded number of possible states. Due to its unbounded tape, a Turing machine system has infinite possible states. However, just because a physical computer isn't actually a TM does not mean that the TM formalism is useless. Remember that this is a *model* of computation. And, as they say, all models are wrong, but some models are useful.  
> **username_4**: @username_0 Similarly, even though a physical computer is composed of physical circuits, and though it can process inputs of variable length, it alone does not comprise a complete circuit *family* under the circuit model of computation. A circuit family would define the behaviour of the system for *all* input lengths. Any physical computer has some upper bound on the size of the input length it can process, again due to finiteness of the physical world.  
> **username_4**: Also, I should be more precise: When I said that a TM has "infinite possible states", I should have said that it has infinite possible *configurations* where a configuration is a combination of the internal state of the TM and the sequence of symbols on the tape. By definition, there are only a finite number of possibilities for the former but infinitely many possibilities for the latter.  

---

