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.
≈ 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.