Unambiguous Turing machine

In theoretical computer science, an unambiguous Turing machine is a theoretical model of computation whose power (under resource restrictions) is between that of ordinary Turing machines and nondeterministic Turing machines.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In theoretical computer science, an unambiguous Turing machine is a theoretical model of computation whose power (under resource restrictions) 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.

A nondeterministic Turing machine is represented formally by a 6-tuple, M=(Q, \Sigma, \iota, \sqcup, A, \delta) , as explained in the aforementioned linked article. An unambiguous Turing machine is a nondeterministic Turing machine M such that for any input w , M has at most one accepting computation on w . That is, for every input w , there exists at most one sequence of configurations c_0,c_1,\ldots,c_m with the following conditions: c_0 is the initial configuration with input w c_{i+1} is a successor of c_i and c_m is an accepting configuration.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1326580587 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001326580587 · captured 1765303952.0 · version history

Cite this page as: encyclopegia.org, “Unambiguous Turing machine”, snapshot enwiki-001326580587. https://encyclopegia.org/a/unambiguous-turing-machine

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.