The Special Case of Non-Deterministic Turing Machines

By

Home / The Special Case of Non-Deterministic Turing Machines

NTMs and Quantum Computing?

A non-deterministic Turing machine tests all possible paths simultaneously until it succeeds in one. In quantum mechanics, a “particle” exists in a probabilistic superposition of multiple states simultaneously, until an interaction collapses the probabilities into a unique state.

Diagram of the double-slit experiment: Image by Koantum

A photon aimed at a double-slit apparatus uses both slits as if the photon’s path were a probability wave. However, one photon can only be detected at one slit, not both simultaneously, so the detector “collapses the probability function.”

In 1982, Dr. Richard Feynman suggested that a quantum computer could simulate quantum events efficiently, by simultaneously keeping all possibilities suspended until finding one positive solution. In this manner, the quantum computer would be similar to an NTM that follows multiple paths simultaneously.

Several theoretical “quantum oracle” algorithms demonstrated that quantum computing would indeed require fewer steps than classic computing, if only a quantum computer could be constructed. As of early 2012, however, only a few quantum bits, or qubits, have been put together into one memory register.

Richard Feynman, centre, in the Manhattan Project. Image courtesy of the US Government

The Value of Non-Deterministic Turing Machines

Non-deterministic Turing machines provide a theoretic basis for quantum computing to achieve certain complex results at high speeds. For mathematicians writing TM proofs, an NTM may offer a shorter set of instructions, but the deterministic Turing machine has the same computational power as its sibling, the non-deterministic Turing machine.

References:

Barker-Plummer, D. Turing Machines. The Stanford Encyclopedia of Philosophy (Spring 2011 Edition), Edward N. Zalta (ed.). Accessed February 28, 2012.

Hagar, A. Quantum Computing. The Stanford Encyclopedia of Philosophy (Spring 2011 Edition), Edward N. Zalta (ed.). Accessed February 28, 2012.

Toida, S. Types of Turing Machines. Old Dominion University, Virginia. Accessed February 28, 2012.

Weisstein, E. W. Turing MachineNondeterministic Turing Machine. (2012). MathWorld-A Wolfram Web Resource.  Accessed February 28, 2012.

Click to Return to Page One: The Special Case of Non-deterministic Turing Machines

Leave a Comment