patternMinor
Converse of halting problem
Viewed 0 times
problemhaltingconverse
Problem
It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is undecidable for some computing apparatus, then it is Turing-complete?
Solution
Here's an artificial counterexample:
Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).
This is clearly not Turing complete since it can't recognize the language $\{b\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem for TMs.
Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).
This is clearly not Turing complete since it can't recognize the language $\{b\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem for TMs.
Context
StackExchange Computer Science Q#99908, answer score: 2
Revisions (0)
No revisions yet.