Tweeted twitter.com/#!/StackCompSci/status/369022777392525312
5 edited tags
| link
4 edited tags
| link
3 added 176 characters in body; edited title
source | link

Alternative proof for the undecidability of the halting problem$A_{TM}$

The proof of the undecidability of the halting problem$A_{TM}$ in Michael Sipser's textbook*textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

 

*Sipser*Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179. On this page, Sipser uses the term halting problem for the language $A_{TM}$. The proper name for this language is acceptance problem, see the footnote on page 188.

Alternative proof for the undecidability of the halting problem

The proof of the undecidability of the halting problem in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

*Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179.

Alternative proof for the undecidability of $A_{TM}$

The proof of the undecidability of $A_{TM}$ in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

 

*Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179. On this page, Sipser uses the term halting problem for the language $A_{TM}$. The proper name for this language is acceptance problem, see the footnote on page 188.

2 added 479 characters in body
source | link
1
source | link