Loading AI tools
From Wikipedia, the free encyclopedia
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. An unambiguous Turing machine is a non-deterministic Turing machine such that, for every input , there exists at most one sequence of configurations with the following conditions:
In other words, if is accepted by , there is exactly one accepting computation.
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.
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. Comput., 26(3), 634–653
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.