Unambiguous Turing machine

In theoretical computer science, an unambiguous Turing machine is a theoretical model of computation whose power is between that of ordinary Turing machines and nondeterministic Turing machines. An unambiguous Turing machine is defined as a nondeterministic Turing machine with the property that for every input, there is at most one accepting computation path.^[1]

A non-deterministic Turing machine is represented formally by a 6-tuple, ${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}, as explained in the aforementioned page.^{[2] : 178}

An unambiguous Turing machine is a non-deterministic Turing machine ${\displaystyle M}${\displaystyle M} such that for any input ${\displaystyle w}${\displaystyle w}, ${\displaystyle M}${\displaystyle M} has at most one accepting computation on ${\displaystyle w}${\displaystyle w}.^[1] That is, for every input ${\displaystyle w}${\displaystyle w}, there exists at most one sequence of configurations ${\displaystyle c_{0},c_{1},\ldots ,c_{m}}${\displaystyle c_{0},c_{1},\ldots ,c_{m}} with the following conditions:

1. ${\displaystyle c_{0}}${\displaystyle c_{0}} is the initial configuration with input ${\displaystyle w}${\displaystyle w}

1. ${\displaystyle c_{i+1}}${\displaystyle c_{i+1}} is a successor of ${\displaystyle c_{i}}${\displaystyle c_{i}} and

1. ${\displaystyle c_{m}}${\displaystyle c_{m}} is an accepting configuration.^{[2] : 168–169}

The language of an unambiguous Turing machine is defined to be the same language that is accepted by the nondeterministic Turing machine. A language of strings L can be defined to be unambiguously recognizable if it is recognizable by an unambiguous Turing machine. The class of unambiguously recognizable languages is exactly the same as the class of recursively enumerable languages (RE).^{[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.

The complexity class UP is defined as the class of languages which can be decided in polynomial time by an unambiguous Turing machine.

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

• Turing machine

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from June 2024