Theoretical machines which are more powerful than Turing machines

Answered By : Yuval Filmus

The Church–Turing thesis (in one formulation) states that everything that can be physically computable can also be computed on a Turing machine. Assuming you believe this theses, and given that you're interested in functions which such machines could compute (and not in, say, interactive computation), then no hypercomputation is possible.

The Church–Turing thesis only concerns itself with what is computable, but not with the efficiency of computation. It is known that Turing machines are not so efficient, though they polynomially simulate classical computers. Quantum computers are believed to be exponentially more efficient than Turing machines. In this sense, you can beat Turing machines (if you could only build a scalable quantum computer).

Scott Aaronson probably has more to say about this — I'll let you look this up on your own.

Problem Detail: 

Are there any theoretical machines which exceed Turing machines capability in at least some areas?

Asked By : user1561358

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55489