formal definition of a Turing machine
Based on the informal description of a Turing machine^{} in the parent entry, we give it a formal mathematical definition:
Definition. A Turing machine $T$ is a 7tuple consists of the following:

1.
an alphabet $S$ called the state alphabet,

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

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

4.
an element $r\in S$ such that $r\ne t$, called the reject state,

5.
an alphabet $\mathrm{\Sigma}$ called the input alphabet,

6.
a symbol called the blank symbol $B$ not in $\mathrm{\Sigma}$,

7.
a function $\delta :S\times \mathrm{\Sigma}\to S\times \mathrm{\Sigma}\times \{L,R\}$ called the transition function, such that
$$\delta (t,a)=\delta (t,b,X)\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}\delta (r,c)=\delta (r,d,Y),$$ where $a,b,c,d\in \mathrm{\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 \mathrm{\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 $\mathrm{\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 twoway 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 $\to $ is a binary relation^{} on the set of all configurations of $T$, defined as follows: if
$$(p,\tau ,m)\to (q,{\tau}^{\prime},n),$$ 
then
$$(q,{\tau}^{\prime},n)=\{\begin{array}{cc}(q,{\tau}^{\prime},m+1)\hfill & \text{provided that}\delta (p,\tau (m))=(q,b,R),\hfill \\ (q,{\tau}^{\prime},m1)\hfill & \text{provided that}\delta (p,\tau (m))=(q,b,L),\hfill \end{array}$$ 
where
$${\tau}^{\prime}(i)=\{\begin{array}{cc}b\hfill & \text{if}i=m,\hfill \\ \tau (i)\hfill & \text{otherwise.}\hfill \end{array}$$ 
We can of course take the reflexive transitive closure of $\to $ to obtain ${\to}^{*}$.
Definition. An input to a Turing machine is a (finite) word $w$ over $\mathrm{\Sigma}$. If the length of $w$ is $n$, we define the tape description ${\tau}_{w}$ of $w$ as follows:
$${\tau}_{w}(i)=\{\begin{array}{cc}{w}_{i}\hfill & \text{the}i\text{th letter of}w,\text{where}0\le i\le n,\text{and}\hfill \\ B\hfill & \text{otherwise.}\hfill \end{array}$$ 
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}),\mathrm{\dots},({p}_{k},{\tau}_{k},{m}_{k}),$$ 
where $({p}_{i},{\tau}_{i},{m}_{i})\to ({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){\to}^{*}(t,\tau ,m)$ for some $\tau $ and $m$. Similarly, $w$ is rejected by $T$ iff $(s,{\tau}_{w},1){\to}^{*}(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 nonreject 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 $\mathrm{\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.

•
It can be shown that $A\subseteq {\mathrm{\Sigma}}^{*}$ is Turing acceptable iff it is recursively enumerable^{}. Furthermore, $A$ is recursive iff there it is Turing acceptable by a total Turing machine.

•
The Turing machines described above are known as language^{} acceptors. However, any Turing machine can be modified so it is capable of producing outputs. Using this modification, one can think of a Turing machine as a partial function^{} where an input is in its domain iff the computation leads to a halting state. More can be found here (http://planetmath.org/TuringComputable).
Title  formal definition of a Turing machine 

Canonical name  FormalDefinitionOfATuringMachine 
Date of creation  20130322 19:09:47 
Last modified on  20130322 19:09:47 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  14 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q10 
Classification  msc 68Q05 
Classification  msc 03D10 
Related topic  TuringComputable 