# deterministic Turing machine

The formal definition of a deterministic Turing machine is a tuple:

$$T=(Q,\mathrm{\Sigma},\mathrm{\Gamma},\delta ,{q}_{0},B,F)$$ |

Where $Q$ is a finite set^{} of states, $\mathrm{\Gamma}$ is the finite set of tape symbols, $B\in \mathrm{\Gamma}$ is the blank symbol, $\mathrm{\Sigma}\subseteq \mathrm{\Gamma}$ is the set of input symbols, $\delta :Q\times \mathrm{\Gamma}\to Q\times \mathrm{\Gamma}\times \{L,R\}$ is the move function, ${q}_{0}\in Q$ is the start state and $F\subseteq Q$ is the set of final states. (Note that, despite the name, $\delta $ is a partial function^{} which will be undefined for some pairs $(q,A)$.)

A Turing machine^{} is conceived to be a box with a tape and a tape head. The tape consists of an infinite^{} number of cells stretching in both directions, with the tape head always located over exactly one of these cells. Each cell has symbol from $\mathrm{\Gamma}$ written on it.

At the beginning of its computation, $T$ is in state ${q}_{0}$ and a finite string $S$ (the input string) over the alphabet $\mathrm{\Sigma}$ is written on the tape, with the tape located over the first letter of $S$. Each cell before the beginning or after the end of $S$ is blank. For each move, if the current state is $q$ and the value of the cell under the tape head is $A$ then suppose $\delta (q,A)=({q}^{\prime},{A}^{\prime},D)$. The value of the cell under the tape head is changed to ${A}^{\prime}$, the state changes to ${q}^{\prime}$, and the tape head moves to the left if $D=L$ and to the right if $D=R$. If $\delta (q,A)$ is undefined then the machine halts.

For any $S\in {\mathrm{\Gamma}}^{+}$, we say $T$ accepts $S$ if $T$ halts in a state $q\in F$ when $S$ is the input string, that $T$ rejects $S$ if $T$ halts in a state $q\notin F$, and otherwise that $T$ does not halt on $S$.

This definition can easily be extended to multiple tapes with various rules. $\delta $ should be a function from $Q\times {\mathrm{\Gamma}}^{n}\to {\mathrm{\Gamma}}^{m}\times {\{L,R\}}^{n}$ where $n$ is the number of tapes, $m$ is the number of input tapes, and $L$ is interpreted to mean not moving (rather than moving to the left) for one-way tapes.

Title | deterministic Turing machine |
---|---|

Canonical name | DeterministicTuringMachine |

Date of creation | 2013-03-22 13:01:22 |

Last modified on | 2013-03-22 13:01:22 |

Owner | Henry (455) |

Last modified by | Henry (455) |

Numerical id | 8 |

Author | Henry (455) |

Entry type | Definition |

Classification | msc 68Q05 |

Classification | msc 68Q10 |

Related topic | TuringMachine2 |