Unambiguous Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. An unambiguous Turing machine is a special kind of non-deterministic Turing machine, which, in some sense, is similar to a deterministic Turing machine.

Formal definition

A non-deterministic Turing machine is represented formally by a 6-tuple, $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , as explained in the page non-deterministic Turing machine. An unambiguous Turing machine is a non-deterministic Turing machine such that, for all input w = a₁a₂ ... a_n, there exists at most one sequence of configurations c₀,c₁, ..., c_m with the following conditions:

c₀ is the initial configuration with input w
c_i+1 is a successor of c_i and
c_m is an accepting configuration.

In other words, if w is accepted by M, there is exactly one accepting computation.

Expressivity

A (deterministic) Turing machine is an unambiguous Turing machine. Indeed, for each input, there is exactly one computation possible.

On the one hand, unambiguous Turing machine have the same expressivity as a Turing machine. Indeed, they are a subset of non-deterministic Turing machines, which have the same expressivity as Turing machines.

On the other hand, unambiguous non-deterministic polynomial time is suspected to be strictly less expressive than non-deterministic polynomial time.

gollark: It does describe it quite well, I think.

gollark: That's the help text for it.

gollark: ```Eggs and hatchlings can become sick when they receive too many views, unique views, and clicks in a short period of time. Although sickness can occur at any time, eggs are most vulnerable when first laid. If an egg or hatchling continues to receive too many views, unique views, and clicks while sick, it may die.To “cure” an egg or hatchling of sickness, simply reduce the rate at which it is receiving views, unique views, and clicks. This may be as simple as removing the egg or hatchling from any sites you have posted it on. Since the hide action prevents eggs and hatchlings from receiving views, unique views, and clicks, it can be a useful tool at combating sickness.```

gollark: Oh? I thought it was good.

gollark: Well, you partly were, but whatever.

References

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.