Timeline for Is there an alternative proof of the TM Halting Problem other than the "standard" one?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2016 at 19:53 | comment | added | Joshua | I managed to shatter this proof. It has an unstated assumption for which it is an open problem in physics whether or not it is true. The naive interpretation assumes monatonic time. | |
| Dec 16, 2010 at 22:26 | comment | added | user1338 | What about the one that refers to the Low Basis theorem? I don't think that one is "more of the same." | |
| Dec 16, 2010 at 4:35 | comment | added | johne | Philip, we'll just have to disagree as to whether or not it is mathematically valid. Regardless, I think you can agree that a second proof that is completely orthogonal and independent is always useful. THIS is what I'm asking for, I'm not making claims (in the strong, formally proven sense, they are a personal opinion) that I have formally shown the proof is invalid. I looked at your links, but unfortunately it's "more of the same". I'm actually surprised that no one has put forward a link to an alternate proof. | |
| Dec 16, 2010 at 2:15 | comment | added | user1338 | "The series of complicated steps" that you allude to is mathematically valid; thus, we know that the only thing that could have "gone wrong" is the assumption A. If you can reach a contradiction as a logical consequence from some premise X, this means that the negation of X is valid and X is not. I get the sense I could talk myself blue in the face and still not convince you, though. Also, take a look at the proofs in the question I linked to above; I don't have the expertise to follow the first proof there, but it might be what you're looking for. I'm not sure what else to say. | |
| Dec 16, 2010 at 2:08 | comment | added | johne | In fact, your spacecraft analogy is precisely why I want an alternative proof that is maximally orthogonal to the original. In your spacecraft analogy, there are numerous other disciplines that can be used to arrive at "That's impossible." The same should be true here. Interestingly, König's lemma would seem to suggest that the finite nature of the $\delta$ transition table means there is no infinite, acyclic path, and therefore would seem to indicate that the Halting Problem is decidable. This is why I want a vetted proof via different means. | |
| Dec 16, 2010 at 2:00 | comment | added | johne | Phillip, the problem lies in the pedantic details in the way the proof is given. On one side, say A, we have the axiomatic definition "the halting problem is decidable." Then, through a series of complicated steps, we finally arrive at a different result, B: "The halting problem is undecidable." This is a contradiction, so we need to resolve it. We could have gone wrong somewhere in A, or possibly in B. My point is this: In this particular case, it simply is not possible to "go wrong in A" because of the way it was defined. | |
| Dec 16, 2010 at 1:00 | history | answered | user1338 | CC BY-SA 2.5 |