# formal definition of a Turing machine

Definition. A Turing machine $T$ is a 7-tuple consists of the following:

1. 1.

an alphabet $S$ called the state alphabet,

2. 2.

an element $s\in S$ called the start state,

3. 3.

an element $t\in S$ called the accept state, and

4. 4.

an element $r\in S$ such that $r\neq t$, called the reject state,

5. 5.

an alphabet $\Sigma$ called the input alphabet,

6. 6.

a symbol called the blank symbol $B$ not in $\Sigma$,

7. 7.

a function $\delta:S\times\Sigma\to S\times\Sigma\times\{L,R\}$ called the transition function, such that

 $\delta(t,a)=\delta(t,b,X)\qquad\mbox{and}\qquad\delta(r,c)=\delta(r,d,Y),$

where $a,b,c,d\in\Sigma\cup\{B\}$ and $X,Y\in\{L,R\}$.

$t,r$ are collectively called the halt states of $T$.

Actually, the definition above is only part of the story. What is described in the definition is the “finite control” (the brain) portion of a Turing machine. All by itself, the finite control is useless. In order for a Turing machine to do computations, two other ingredients are needed to complete     the description: a tape, and a reading head. The two can be formalized as follows:

Definition. A tape, or formally a tape description, is a function $\tau:\mathbb{Z}\to\Sigma\cup\{B\}$. A position of the reading head is an integer $n\in\mathbb{Z}$.

In other words, the tape of a Turing machine $T$ is infinitely long in both direction, and is divided up into squares. The content of each square is either a symbol in $\Sigma$ or blank ($B$). The purpose of the tape is to store input, output, as well as any other strings that are used during computations.

The finite control and the tape of a Turing machine are connected by a reading head, which points over the tape, has the ability to move left or right along the tape, and reads the tape one square at a time. The position of the reading head is the square it is currently reading.

The Turing machine defined this way is also known as a two-way deterministic Turing machine.

To formally describe the computational process of a Turing machine, we need to know three things: what is the current state of the finite control, what is on the tape, and what is the current position of the reading head:

Definition. A configuration  of a Turing machine is a triple $(p,\tau,m)$, where $p\in S$, called the state of the configuration, $\tau$ is a tape description called the tape description of the configuration, and $m$ is a position of the reading head called the position of the reading head of the configuration.

We are now ready to describe what it means for a Turing machine to compute something:

Definition. Given a Turing machine $T$ (with the associated tape and reading head), a computation step $\rightarrow$ is a binary relation  on the set of all configurations of $T$, defined as follows: if

 $(p,\tau,m)\rightarrow(q,\tau^{\prime},n),$

then

 $(q,\tau^{\prime},n)=\left\{\begin{array}[]{ll}(q,\tau^{\prime},m+1)&\textrm{% provided that }\delta(p,\tau(m))=(q,b,R),\\ (q,\tau^{\prime},m-1)&\textrm{provided that }\delta(p,\tau(m))=(q,b,L),\end{% array}\right.$

where

 $\tau^{\prime}(i)=\left\{\begin{array}[]{ll}b&\textrm{if }i=m,\\ \tau(i)&\textrm{otherwise.}\end{array}\right.$

We can of course take the reflexive transitive closure of $\rightarrow$ to obtain $\rightarrow^{*}$.

Definition. An input to a Turing machine is a (finite) word $w$ over $\Sigma$. If the length of $w$ is $n$, we define the tape description $\tau_{w}$ of $w$ as follows:

 $\tau_{w}(i)=\left\{\begin{array}[]{ll}w_{i}&\textrm{the i-th letter of }w,% \mbox{ where }0\leq i\leq n,\mbox{ and}\\ B&\textrm{otherwise.}\end{array}\right.$

Note that $\tau_{\lambda}$ is the constant function whose value is $B$, where $\lambda$ is the empty word   .

Definition. Given an input $w$ and a Turing machine $T$, a computation of $w$ by $T$ is a finite sequence  $(s,\tau_{w},1)=(p_{1},\tau_{1},m_{1}),(p_{2},\tau_{2},m_{2}),\ldots,(p_{k},% \tau_{k},m_{k}),$

where $(p_{i},\tau_{i},m_{i})\rightarrow(p_{i+1},\tau_{i+1},m_{i+1})$. From the computation of $w$ above, we also say that the computation of $w$ leads to state $p_{k}$. $T$ is said to accept an input $w$ iff it there is a computation of $w$ leading to the accepting state $t$. In other words, $w$ is accepted by $T$ iff $(s,\tau_{w},1)\rightarrow^{*}(t,\tau,m)$ for some $\tau$ and $m$. Similarly, $w$ is rejected by $T$ iff $(s,\tau_{w},1)\rightarrow^{*}(r,\tau,m)$ for some $\tau$ and $m$. $T$ is said to halt on input $w$ iff it either accepts or rejects $w$. Otherwise, $T$ is said to loop on $w$.

By the definition of the transition function $\delta$, once the computation of $w$ leads to the accepting state $t$, it never leaves that state. Likewise, once the computation of $w$ leads to the reject state $r$, no further computation will lead to a non-reject state.

Definition. Let $T$ be a Turing machine. The set of words accepted by $T$ is denoted by $L(T)$. A set $A$ of words over $\Sigma$ is said to be Turing acceptable if there is a Turing machine $T$ such that $A=L(T)$. If $T$ halts on every input word, then $T$ is said to be total.

Remarks.

Title formal definition of a Turing machine FormalDefinitionOfATuringMachine 2013-03-22 19:09:47 2013-03-22 19:09:47 CWoo (3771) CWoo (3771) 14 CWoo (3771) Definition msc 68Q10 msc 68Q05 msc 03D10 TuringComputable