-4

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.

Kaveh
  • 21,577
  • 8
  • 82
  • 183
johne
  • 227
  • 2
  • 7
  • 2
    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 Dec 16 '10 at 23:12
  • possible duplicate of Is there an alternative proof of the TM Halting Problem other than the "standard" one? – Kaveh Dec 16 '10 at 23:19
  • 3
    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 Dec 16 '10 at 23:23
  • 2
    "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 Dec 16 '10 at 23:29
  • 3
    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 Dec 16 '10 at 23:35
  • 1
    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 Dec 17 '10 at 04:25
  • @mhum: Yes, but... it's very complicated. This does not directly answer your question, but a Toffoli gate 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 Dec 17 '10 at 04:37
  • @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 Dec 17 '10 at 04:40
  • @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 Dec 17 '10 at 04:41
  • 1
    @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 Dec 17 '10 at 04:46
  • @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 Dec 17 '10 at 04:58
  • @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 Dec 17 '10 at 05:06
  • @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 Dec 17 '10 at 05:08
  • @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 Dec 17 '10 at 05:19
  • @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 Dec 17 '10 at 05:21
  • @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 Dec 17 '10 at 05:29
  • @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 Dec 17 '10 at 05:31
  • 8
    @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 Dec 17 '10 at 05:32
  • @johne How are you going to "cull" that finite set other than running the machine? – Mark Reitblatt Dec 17 '10 at 05:34
  • @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. – johne Dec 17 '10 at 05:41
  • 2
    @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 Dec 17 '10 at 05:44
  • @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. 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 Dec 17 '10 at 06:07
  • @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 Dec 17 '10 at 06:24
  • @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 Dec 17 '10 at 06:29
  • 3
    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 Dec 17 '10 at 06:33
  • 1
    metadiscussion here: http://meta.cstheory.stackexchange.com/questions/826/dealing-with-user-issue – Suresh Venkat Dec 17 '10 at 06:59

1 Answers1

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 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$.
mhum
  • 3,382
  • 1
  • 21
  • 22
  • @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 ~$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 Dec 17 '10 at 03:26
  • 4
    @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 Dec 17 '10 at 04:50
  • 3
    @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 Dec 17 '10 at 05:32
  • 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 Dec 17 '10 at 05:36
  • @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 Dec 17 '10 at 06:44
  • @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 Dec 17 '10 at 06:50
  • @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 Dec 17 '10 at 06:53
  • @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 Dec 17 '10 at 07:20
  • @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 Dec 17 '10 at 07:24
  • 1
    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 Dec 17 '10 at 15:49