-4
$\begingroup$

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.

Improve this question
$\endgroup$
26
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sadeq Dousti
    Commented Dec 16, 2010 at 23:12
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Dec 16, 2010 at 23:23
  • 3
    $\begingroup$ Did you take a look at this answer cstheory.stackexchange.com/questions/2853/… It references the Low Basis theorem which is a consequence of Koenig's Lemma, which I see appealed to you previously. $\endgroup$
    – mhum
    Commented Dec 16, 2010 at 23:35
  • 8
    $\begingroup$ @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. $\endgroup$
    – Mark Reitblatt
    Commented Dec 17, 2010 at 5:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Dec 17, 2010 at 6:33

1 Answer 1

Reset to default
4
$\begingroup$

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$.
Improve this answer
$\endgroup$
10
  • $\begingroup$ @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! $\endgroup$
    – johne
    Commented Dec 17, 2010 at 3:26
  • 4
    $\begingroup$ @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. $\endgroup$
    – Mark Reitblatt
    Commented Dec 17, 2010 at 4:50
  • 3
    $\begingroup$ @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. $\endgroup$
    – mhum
    Commented Dec 17, 2010 at 5:32
  • $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Dec 17, 2010 at 5:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Dec 17, 2010 at 15:49

Your Answer

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

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