Turing Machine transitions

The transition ( $\delta$ ) function of a Turing Machine (TM) is mapped as follows

$\begin{equation*}Q \setminus \{q_{accept}, q_{reject}\} \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\end{equation*}$

Given a state and the current tape symbol (pointed by the tape-head) the transition writes a new symbol, changes state and moves the tape-head one cell either to the left or to the right.

Here are some example transitions and the notations used

$\delta(q_i, a) = (q_j, b, R)$

In state $q_1$ with the tape-head reading $a$ , the machine goes to $q_j$ , writes $b$ , and moves the tape-head to the right.

Rendered by QuickLaTeX.com

$\delta(q_i, a) = (q_j, b, L)$

In state $q_1$ with the tape-head reading $a$ , the machine goes to $q_j$ , writes $b$ , and moves the tape-head to the left.

Rendered by QuickLaTeX.com

$\delta(q_i, a) = (q_j, a, R)$

The notation $a \rightarrow a, R$ is reduced to $a \rightarrow R$

In state $q_1$ with the tape-head reading $a$ , the machine goes to $q_j$ , and moves the tape-head to the right.

Rendered by QuickLaTeX.com

$\delta(q_i, a) = (q_j, a, L)$

The notation $a \rightarrow a, L$ is reduced to $a \rightarrow L$

In state $q_1$ with the tape-head reading $a$ , the machine goes to $q_j$ , and moves the tape-head to the left.

Rendered by QuickLaTeX.com

References

https://www.ics.uci.edu/~goodrich/teach/cs162/notes/turing2.pdf

The Beard Sage

Turing Machine transitions

$\delta(q_i, a) = (q_j, b, R)$

$\delta(q_i, a) = (q_j, b, L)$

$\delta(q_i, a) = (q_j, a, R)$

$\delta(q_i, a) = (q_j, a, L)$

References

Leave a Reply Cancel reply