Unambiguous Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments[by whom?] to examine the abilities and limitations of computers.[citation needed] An unambiguous Turing machine is a special kind of non-deterministic Turing machine, which, in some sense,[clarification needed] is similar to a deterministic Turing machine.
Formal definition[edit]
A non-deterministic Turing machine is represented formally by a 6-tuple, , as explained in the page non-deterministic Turing machine. An unambiguous Turing machine is a non-deterministic Turing machine such that, for every input , there exists at most one sequence of configurations with the following conditions:
- is the initial configuration with input
- is a successor of and
- is an accepting configuration.
In other words, if is accepted by , there is exactly one accepting computation.
Expressivity[edit]
Every deterministic Turing machine is an unambiguous Turing machine, as for each input, there is exactly one computation possible. Unambiguous Turing machines have the same expressivity as a Turing machines. 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 suspected to be strictly less expressive than (potentially ambiguous) non-deterministic polynomial time.
References[edit]
Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653