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, ${\displaystyle 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 ${\displaystyle w=a_{1},a_{2},...,a_{n}}$, there exists at most one sequence of configurations ${\displaystyle c_{0},c_{1},...,c_{m}}$ with the following conditions:

1. ${\displaystyle c_{0}}$ is the initial configuration with input ${\displaystyle w}$
2. ${\displaystyle c_{i+1}}$ is a successor of ${\displaystyle c_{i}}$ and
3. ${\displaystyle c_{m}}$ is an accepting configuration.

In other words, if ${\displaystyle w}$ is accepted by ${\displaystyle 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