Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing machines?

  • $\begingroup$ Most hypercomputing machines are more powerful than Turing machines by definition--and only by definition. $\endgroup$ – Mars Jan 7 '20 at 22:52

I see two ways of interpreting this question, but the answer is essentially trivial either way.

Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a Turing machine?

Yes, because that is the definition of a hypercomputation model.

A caveat: Technically, you could have a hypercomputation model that (as Wikipedia puts it) "can provide outputs that are not Turing-computable", yet cannot actually accept any nonrecursive language according to the definition of language acceptance for the model. This is because accepting a language is not the same thing as computing a function. This would probably require a contrived definition of language acceptance, though. For example, take any standard hypercomputation model and say that the acceptance criterion is that the machine rejects on all inputs.

Interpretation 2: Can some hypercomputation model decide every language that cannot be decided by a Turing machine?

No for any reasonable definition of a "model of computation", because the set $\mathrm{ALL} \setminus \mathrm{R}$ of all languages not decidable by a Turing machine is an uncountable set. So for almost every undecidable language, there is no way to write down a program that decides that language, no matter how powerful your model of computation is, as long as you require programs to be written using a finite number of symbols.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.