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.
A non-deterministic Turing machine is represented formally by a 6-tuple,
, as explained in the page non-deterministic Turing machine.
The language of an unambiguous Turing machine is defined to be the same language that is accepted by the nondeterministic Turing machine.
[citation needed] In particular, every deterministic Turing machine is an unambiguous Turing machine, as for each input, there is exactly one computation possible.
Therefore, all recursively enumerable languages are unambiguously recognizable.
On the other hand, unambiguous non-deterministic polynomial time is suspected to be strictly less expressive than (potentially ambiguous) non-deterministic polynomial time.
Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J.