7

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.

Note

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.

Roc Martí
  • 783
  • 1
  • 5
  • 17
Ubermensch
  • 1,349
  • 9
  • 15

3 Answers3

8

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.

DeadMG
  • 36,794
  • 8
  • 70
  • 139
3

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.

scarfridge
  • 1,796
  • 13
  • 20
  • 1) While input to a TM can only come from its tape, this tape has input from all sources, including from user input. At the face of it, this doesn't seem to allow for interaction because the contents of the tape can't depend on the states of the TM or the partial output, but user interaction can still be modeled by running the TM multiple times: each time it produces output (halts), a new tape is fed in, allowing for input to depend on previous output. It's unwieldy, but theoretically sound (much as QM could theoretically be used for classical problems). – outis Nov 10 '14 at 07:43
  • 2) A DTM running an NTM's computions sequentially isn't equivalent when a branch of the latter doesn't halt. In this case, the NTM will halt, but the DTM won't if it runs the non-halting branch before the accepting branch. An [NTM-equivalent DTM](https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine#Equivalence_with_DTMs) basically runs all the NTM computations in parallel, either actually, by having a DTM configuration represent multiple NTM configurations, or virtually, with serial multitasking. – outis Nov 10 '14 at 07:58
1

Although quantum computers may be faster than classical computers, they can't solve any problems that classical computers can't solve. A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false. The existence of "standard" quantum computers does not disprove the Church–Turing thesis. The D-Wave machine is solving problems using quantum technology but it is not a "general purpose" or standard computer in any sense of the term. That it does what it is doing is great and it will be fascinating to see what the future brings. See the references cited in the Wikipedia entry.

Richard Rankin
  • 19
  • 1
  • 1
    this post is rather hard to read (wall of text). Would you mind [edit]ing it into a better shape? It is also unclear what references and what Wikipedia entry you are talking about – gnat Nov 10 '14 at 07:06