Deterministic Turing Machine

From GM-RKB
Jump to navigation Jump to search

A Deterministic Turing Machine is a Turing Machine where..

References

2016

  • (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Retrieved:2016-1-21.
    • 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.

      In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', change it to 'B' and move left."

      In a deterministic Turing machine, the set of rules prescribes one action to be performed for any given situation. By contrast, a non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set.

      A deterministic Turing machine (DTM) has a transition function that, for a given state and symbol under the tape head, specifies three things:

      • the symbol to be written to the tape,
      • the direction (left, right or neither) in which the head should move, and
      • the subsequent state of the finite control.
    • For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. …
Retrieved from "http://www.gabormelli.com/RKB/index.php?title=Deterministic_Turing_Machine&oldid=706244"