Timeline for Alternative Turing Machine Proofs
Current License: CC BY-SA 2.5
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 17, 2010 at 6:59 | comment | added | Suresh Venkat | metadiscussion here: meta.cstheory.stackexchange.com/questions/826/… | |
| Dec 17, 2010 at 6:33 | comment | added | Suresh Venkat | 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. | |
| Dec 17, 2010 at 6:29 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 6:24 | comment | added | johne | @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. | |
| Dec 17, 2010 at 6:07 | comment | added | johne |
@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.
|
|
| Dec 17, 2010 at 5:44 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 5:41 | comment | added | johne | @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. | |
| Dec 17, 2010 at 5:34 | comment | added | Mark Reitblatt | @johne How are you going to "cull" that finite set other than running the machine? | |
| Dec 17, 2010 at 5:32 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 5:31 | comment | added | johne | @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. | |
| Dec 17, 2010 at 5:29 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 5:21 | comment | added | johne |
@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.
|
|
| Dec 17, 2010 at 5:19 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 5:08 | comment | added | johne | @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$)") | |
| Dec 17, 2010 at 5:06 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 4:58 | comment | added | johne | @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. | |
| Dec 17, 2010 at 4:46 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 4:41 | comment | added | johne | @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? | |
| Dec 17, 2010 at 4:40 | comment | added | Mark Reitblatt | @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. | |
| Dec 17, 2010 at 4:37 | comment | added | johne | @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. | |
| Dec 17, 2010 at 4:25 | comment | added | Peter Shor | 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? | |
| Dec 17, 2010 at 1:15 | answer | added | mhum | timeline score: 4 | |
| Dec 16, 2010 at 23:35 | comment | added | mhum | 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. | |
| Dec 16, 2010 at 23:29 | comment | added | Mark Reitblatt | "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. | |
| Dec 16, 2010 at 23:23 | comment | added | Kaveh | 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. | |
| Dec 16, 2010 at 23:19 | history | edited | Kaveh |
edited tags
|
|
| Dec 16, 2010 at 23:19 | comment | added | Kaveh | possible duplicate of Is there an alternative proof of the TM Halting Problem other than the "standard" one? | |
| Dec 16, 2010 at 23:12 | comment | added | Sadeq Dousti | 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. | |
| Dec 16, 2010 at 23:08 | history | asked | johne | CC BY-SA 2.5 |