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.
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 all input w = a1a2 ... an, there exists at most one sequence of configurations c0,c1, ..., cm with the following conditions:
- c0 is the initial configuration with input w
- ci+1 is a successor of ci and
- cm is an accepting configuration.
In other words, if w is accepted by M, there is exactly one accepting computation.
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.
Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653