In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W

I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.

She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.

Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.

So, I have a couple of questions:

  1. Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?

So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?

  1. Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.
  • 5
    $\begingroup$ You can simulate a quantum computer with a classical computer. It's just exponentially expensive. $\endgroup$ Mar 28, 2014 at 10:50
  • 3
    $\begingroup$ there is a fairly simple proof that the multitape TM is not really any more "powerful" than a single tape TM, you only get a linear speedup, which is "negligible" wrt complexity theory & big-Oh asymptotic complexity. $\endgroup$
    – vzn
    Mar 28, 2014 at 15:13
  • 3
    $\begingroup$ also its an open question subject to major active/ongoing worldwide research both theoretically & practically whether a QM computer is/can be faster than a classical computer. $\endgroup$
    – vzn
    Mar 28, 2014 at 15:28

1 Answer 1


You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ramifications of the concept of computation. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models are the same from the point of view of computability theory. Computability theory, while an interesting mathematical subject, is not a good model for real-world computation for this reason, as you mention.

Complexity theory started its life as an attempt to address this issue. Complexity theory studies how difficult it is, in terms of time and space, to compute certain predicates and functions. From the point of view of complexity theory, not all computation models are the same, and Turing machines are taken as the reference model. However, even complexity theory is not very realistic, since it treats all computational models polynomially equivalent to Turing machines in the same way (two models are polynomially equivalent if any problem solvable in time $T(n)$ and space $S(n)$ in one model can be solved in time $T(n)^c$ and space $S(n)^c$ in the other, where $n$ is the input size and $c$ is some positive constant). For example, Turing machines are not good models for real computers since they do not support random access (accessing an arbitrary point in memory in time $O(1)$). Of course, random access can be simulated by a Turing machine, but the simulation can be slow. It is often said that sorting can be done in time $O(n\log n)$, but this is not the case for Turing machines, which probably require $\Omega(n^2)$ or move even for sorting integers. Therefore in the area of algorithms, other models such as the RAM machine replace Turing machines.

Finally, quantum computers can be modelled in several different ways, such as the quantum Turing machine. Everything computable using quantum computers is also computable using classical computers, and so from the point of view of computability theory, quantum Turing machines are just another equivalent model. However, quantum Turing machines are widely conjectured not to be polynomially equivalent to classical Turing machines: for example, factoring and discrete logarithm are "easy" for quantum Turing machines (solvable in polynomial time), while it is conjectured that they are "hard" for classical Turing machines (cannot be solved in polynomial time; though some people think that integer factoring might be solvable in polynomial time). So from the point of view of complexity theory, quantum Turing machines are different from classical Turing machines.

  • $\begingroup$ Could you give me a reference regarding equivalency between classical Turing machine and quantum Turing machine from point of view of computability theory? $\endgroup$ Sep 6, 2017 at 6:55
  • $\begingroup$ @ErfanKhaniki Check the references on Wikipedia - hopefully one of them would help. $\endgroup$ Sep 6, 2017 at 7:15
  • $\begingroup$ @YuvalFilmus "So from the point of view of complexity theory, quantum Turing machines are different from classical Turing machines," should read, "So from the point of view of complexity theory, quantum Turing machines are conjecturally different from classical Turing machines," according to, "while it is conjectured that they are 'hard' for classical Turing machines," right? $\endgroup$
    – user101794
    Mar 19, 2019 at 7:19
  • 2
    $\begingroup$ There are some provable separations in black-box models, like Simon's problem. $\endgroup$ Mar 19, 2019 at 8:41

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.