Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the machine which could solve the problems that T.M cannot?Are quantum computers also the T.M or are they more powerful than T.M?
1
-
1$\begingroup$ Have you checked this site for answers? What about TM with Oracles? With infinite inputs and real numbers? $\endgroup$– EvilCommented Jul 13, 2018 at 14:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Your question is closely related to the Church–Turing thesis, which says that Turing machines can compute anything that can reasonably be described as an algorithm (i.e., a sequence of discrete steps). Variants, such as the physical Church–Turing thesis state that Turing machines can compute anything that can be computed by any physical mechanism. Note that these are described as "theses", rather than theorems. They're not formal claims about mathematics so they're not possible to prove.
We don't know how to build any physical device that could compute a non-Turing-computable function. This includes quantum computers, which can be simulated (though inefficiently) to arbitrary accuracy by non-quantum devices such as Turing machines.
We can certainly consider more powerful devices, though, even though we don't know of any way to build them. A typical construction is to take something that Turing machines can't do, and then imagine that we have a subroutine that instantly solves that problem. These are known as oracle machines, and they are provably more powerful than Turing machines. Indeed, one can define a whole infinite hierarchy of successively more powerful machines using this idea, with the caveat that we have no clue how to physically build such a thing.
answered Jul 13, 2018 at 14:59