Read only right moving Turing Machines

Read only right moving Turing Machines

A particular type of Turing Machine. The definition based on a single infinite tape defined to be a 7-tuple

M= langle Q, Gamma, b, Sigma, delta, q_0, F angle where
* Q is a finite set of "states"
* Gamma is a finite set of the "tape alphabet/symbols"
* b in Gamma is the "blank symbol" (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
* Sigma, a subset of Gamma not including b is the set of "input symbols"
* delta: Q imes Gamma ightarrow Q imes Gamma imes {R} is a function called the "transition function", R is a right movement (a right shift).
* q_0 in Q is the "initial state"
* F subseteq Q is the set of "final" or "accepting states"

In the case of these types of Turing Machines, the only movement is to the right.There must exist at least one element of the set F (a HALT state) for the machine to accept a regular language (Not in including the empty language).

An example Read Only right moving Turing machine

:Q = { A, B, C, HALT }:Γ = { 0, 1 }:b = 0 = "blank":Σ = varphi, empty set:δ = see state-table below:q0 = A = initial state:F = the one element set of final states {HALT}

State table for 3 state, 2 symbol read only machine:

ee also

* DFA
* NDFA
* Finite State Machine
* Read-only Turing machine
* Turing Machine
* Turing machine examples

References

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Multi-track Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine gallery — The following article is a supplement to the article Turing machine. Turing machine as a mechanical device The Turing machine shown here consists of a special paper tape that can be erased as well as written with a tally mark . Perhaps the TABLE… …   Wikipedia

  • Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер …   Википедия

  • Квантовая машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Неде …   Википедия

  • Вероятностная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Не …   Википедия

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”