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?
1
-
$\begingroup$ Most hypercomputing machines are more powerful than Turing machines by definition--and only by definition. $\endgroup$– MarsJan 7, 2020 at 22:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
