Unambiguous Turing machine

Turing machines
Machine
Universal Turing machine Alternating Turing machine Quantum Turing machine Non-deterministic Turing machine Unambiguous Turing machine Read-only Turing machine Read-only right moving Turing machines Probabilistic Turing machine Multitape Turing machine Multi-track Turing machine Turing machine equivalents Turing machine examples
Science
Alan Turing Category:Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. An unambiguous Turing machine is a special kind of non-deterministic Turing machine, which, in some sense, is similar to a deterministic Turing machine.

Formal definition

A non-deterministic Turing machine is represented formally by a 6-tuple, $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ . An Unambiguous Turing machine is a non-deterministic Turing machine such that, for all input w = a₁a₂ ... a_n, there exists at most one sequence of configurations c₀,c₁, ..., c_m with the following conditions:

c₀ is the initial configuration with input w
c_i+1 is a successor of c_i and
c_m is an accepting configuration.

In other words, if w is accepted by A, there is exactly one accepting computation.

Expressivity

A (deterministic) Turing machine is an unambiguous Turing machine. Indeed, for each input, there is exactly one computation possible.

On the one hand, unambiguous Turing machine have the same expressivity as a Turing machine. Indeed, they are a subset of non-deterministic Turing machines, which have the same expressivity as Turing machines.

On the other hand, unambiguous non-deterministic polynomial time is supposed to be strictly less expressive than non-deterministic polynomial time.

References

Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653

This article is issued from Wikipedia - version of the 8/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.