Unambiguous 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)$, as explained in the page ''non-deterministic Turing machine''.
An ''unambiguous Turing machine'' is a non-deterministic Turing machine such that, for every input $w=a_1,a_2,...,a_n$, there exists at most one sequence of configurations $c_0,c_1,...,c_m$ with the following conditions:
# $c_0$ 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 $M$, there is exactly one accepting computation.

Expressivity

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

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

Turing machine