|
|
|
Revision difference : deterministic Turing machine |
| Version current |
Version 4 |
| The formal definition of a deterministic Turing machine is a tuple: |
The formal definition of a deterministic Turing machine is a tuple: |
|
|
| $$T=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$$ |
$$T=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$$ |
|
|
|
Where $Q$ is a finite set of states, $\Gamma$ is the finite set of tape symbols, $B\in\Gamma$ is the blank symbol, $\Sigma\subseteq\Gamma$ is the set of input symbols, $\delta:Q\times\Gamma\rightarrow Q\times\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)$.)
|
Where $Q$ is a finite set of states, $\Gamma$ is the finite set of tape symbols, $B\in\Gamma$ is the blank symbol, $\Sigma\subseteq\Gamma$ is the set of input symbols, $\delta:Q\times\Gamma\rightarrow Q\times\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. |
|
|
| 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 $\Gamma$ written on it. |
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 $\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 $\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.
|
At the beginning of its computation, $T$ is in state $q_0$ and a finite string $S$ (the input string) over the alphabet $\Gamma$ 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\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\not\in F$, and otherwise that $T$ does not halt on $S$. |
For any $S\in\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\not\in 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\Gamma^n\rightarrow\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. |
This definition can easily be extended to multiple tapes with various rules. $\delta$ should be a function from $Q\times\Gamma^n\rightarrow\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. |
|
|
|
|
