Is there any turing machine that it is proovably known to be undecideable, it has to fullfit the following characteristics:

  • Not rely on Open Problems/ Conjectures
  • Should not use the same machine used in diagonalization proof

In other words, is there an alternative proof that Halting problem is undecideable (other than diagonalization)?

  • $\begingroup$ "known to be undecidable" in a particular formal theory, or in the sense that [the set on inputs on which the machine halts] is non-computable? ​ ​ $\endgroup$ – user12859 Sep 14 '16 at 14:03
  • $\begingroup$ Is it relevant to say here that $L(M)= \sum^*$ is undecidable, because we do not have a general algorithm that can be applied to this machine to decide whether it is decidable (halts)? If yes, does this support the argument of the halting problem being undecidable? $\endgroup$ – px06 Sep 14 '16 at 15:20
  • $\begingroup$ But does the proof of that rely on the diagonalization? $\endgroup$ – CoffeDeveloper Sep 14 '16 at 16:12
  • 1
    $\begingroup$ Let M be TM that decides $A_{tm}$. Take M as subroutine to decide language $S_{tm}$ but since that language is not recursive this leads to contradiction (without diagonalization). $\endgroup$ – Evil Sep 14 '16 at 20:37
  • $\begingroup$ Would accept it if added with some explaination so that also who don't know what Atm is can understand it $\endgroup$ – CoffeDeveloper Sep 15 '16 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.