title: Unambiguous Turing machine
text: # 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 every input $w=a_{1},a_{2},...,a_{n}$, there exists at most one sequence of configurations $c_{0},c_{1},...,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.
  
  In other words, if $w$ is accepted by $M$, there is exactly one accepting computation.
  
  ## Expressivity
  
  Every deterministic Turing machine is an unambiguous Turing machine, as for each input, there is exactly one computation possible. Unambiguous Turing machines have the same expressivity as a Turing machines. 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 (potentially ambiguous) non-deterministic polynomial time.
  
  