0
$\begingroup$

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be recognized by a Turing machine, but can be recognized by something more computationally powerful than a Turing machine). Turing machines are universal, in the sense that all Turing-equivalent machines have the same fundamental computational capability (ignoring time and space limits), and as far as we know, it is not possible to build something that is fundamentally more computationally powerful than a Turing machine.

What is the name for this theory? How is it proved that there cannot exist a computer more computationally powerful than a Turing machine?

$\endgroup$
2
  • 1
    $\begingroup$ I'm not 100% clear about what you are asking, but it seems like you may be referring to the Church-Turing thesis. $\endgroup$
    – mhum
    Mar 15 at 20:54
  • $\begingroup$ @mhum You should post it as an answer. $\endgroup$
    – Nathaniel
    Mar 15 at 21:33

3 Answers 3

4
$\begingroup$

I believe that the questioner is inquiring about the Church-Turing thesis.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, that's not what I'm looking for (I am interested in any name for a proof that no computer more powerful than a Turing computer can be built), but the article you linked did link to the answer: en.wikipedia.org/wiki/Hypercomputation $\endgroup$ Mar 16 at 7:17
1
$\begingroup$

The term I was looking for, that collects research on my original question as to whether there was a proof that Turing completeness is the most powerful model of computing, is hypercomputation:

https://en.wikipedia.org/wiki/Hypercomputation

It seems that it is controversial as to whether hypercomputation models can practically be built (there is no proof yet as to whether hypercomputation is possible or not).

(Thanks to mhum for pointing me in the right direction so that I could find this answer...)

$\endgroup$
1
  • 1
    $\begingroup$ When you have found the right answer yourself, you can still accept it. $\endgroup$
    – Highheath
    Mar 19 at 19:27
1
$\begingroup$

In my recent question, I asked why do we consider Turing Machines as a limit of computation, you can check it here, good answer was provided for it: Is the Turing machine the only framework to analyse limits of computation?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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