Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

As far as I know, a Turing Machine is the widely used model in computational theory to know whether something could be computed and if computed can they can be computed in finite time (P, NP, NPSpace). But I have the following doubts:

  1. Is a Turing Machine essentially a black-box model where a set of inputs give a set of outputs such that there could be no interaction during computation? By no interaction, I mean that during computation the variables wouldn't be altered by an external factor.
  2. As an extension to the above question, are non-deterministic functions Turing complete?
  3. Is Turing Machine an efficient model for Quantum Computing?

Going by what I have learned so far, my answers are:

  1. Turing Machines cannot handle interaction and random behavior and it's not guaranteed even by Turing in his original paper.
  2. Non-deterministic functions may bring Turing machines to a halt.
  3. No since Turing machines cannot efficiently support the superposition of bits.


I am not well-versed in either Computational Theory or Quantum Computing. So a lot of links and some beginner's stuff would be a lot helpful and reading this article inspired this question.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

1) As you pointed out a lot of the theory about "what can be computed" is based on it. For that to work out it is essential to know how it operates internally. A Turing machine is not a black box. A favorable property of Turing machines is their locality of change. Every step changes just very little, that is, the internal state (think of it as number), the letter on the tape and the position on the tape. The latter can only be changed by 1 step to the left or to the right. In this model all input is in form of what is written on the tape. The tape content is only changed by the machine. So - no interaction.

2) A machine or programming language is called Turing complete, if it can simulate all Turing machines. Thus, non-deterministic Turing machines are Turing complete, because they can simulate a Turing machine by simply not using non-determinism. Interestingly enough, a deterministic Turing can simulate a non-deterministic one, simply by trying all possible outcomes of non-deterministic results sequentially. This is a brute force approach and not very efficient. It is unclear if there is an efficient way to do it. BTW, most computer scientist do not think that it can be done.

As for your own answer to this - Turing machines are supposed to halt. In this context it means that the computation is finished and has a result. You might think it means that the machine gets frozen. But it is the other way round. A frozen machine (e.g. your desktop computer) did not halt, when it was supposed to and know you are waiting forever and cannot do anything (but reboot). Non-determinism has no effect on a machine halting or not.

3) The only known way to simulate a quantum computing device uses non-determinism. As said under 2), we can simulate non-determinism, but not efficiently. And we probably never will.

share|improve this answer

Quantum computers are still within the limits of Turing-complete. You can exactly simulate one with a regular machine, it would simply take exponential time. Of course, the complexity classes are not necessarily the same- for example, discrete factorization is an NP-hard problem on a classical computer but a quantum algorithm can do it in linear time.

Quantum computers do not fundamentally break the rules of computation. No quantum computer can solve the Halting Problem, or anything like that. They can simply perform some kinds of computation much, much faster than a classical computer. It's exactly the same as having an exponentially faster classical machine.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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