3. Turing Machines

Turing Machine

Turing Machine

A Turing Machine is a model of an automaton which can read and write from an infinite length tape which contains cells of information.

Link to original

$$\begin{array}{c}\text{Turing Machine}\\ M=⟨\Sigma ,Q,q_{init},q_{accept},q_{reject},\sigma ⟩\\ \\ \begin{array}{rl}\text{alphabet}& :\Sigma =\{a_1,\dots ,a_k\}\\ \text{finite set of control states}& :Q=\{q_1,\dots ,q_n\}\\ \text{initial state}& :q_{init}\in Q\\ \text{accept / reject states}& :q_{accept},q_{reject}\in Q\\ & \\ \text{transition function}& :\delta :(Q\times \Sigma )\to (Q\times \Sigma \times \{\leftarrow ,\to \})\\ & :\delta :(\text{current state},\text{read})\to (\text{new state},\text{write},\text{move})\end{array}\end{array}$$

Decision Procedure

We use the following notation to describe the behaviour of $M$ on input $w$:

$$M(w):=\{\begin{array}{ll}1& \text{if }M\text{ accepts }w\\ 0& \text{if }M\text{ rejects }w\\ \uparrow & \text{if }M\text{ does not halt on }w\end{array}$$

Any machine $M$ is said to decide a language $L$ if it is:

• Sound: if $M(w)=1$ then $w\in L$
• Complete: if $w\in L$ then $M(w)=1$
• Terminating: $T_M(w)<\infty$ is finite for all $w\in {\Sigma }^{\ast }$

Non-deterministic Turing Machines (NDTMs)

Non-deterministic Turing Machine

We can expand our definition of the transition function to provide a set of possible instructions which we can choose from, thus defining a non-deterministic Turing Machine:

$$\begin{array}{rl}& \delta :(Q\times \Sigma \times \{\bigsqcup \})\to \mathcal{P}(Q\times \Sigma \cup \{\bigsqcup \}\times \{\leftarrow ,\to \})\\ & \delta :(\text{current state},\text{read})\to \left\{\begin{array}{c}\text{possible instructions}\\ \text{state},\text{write},\text{move}\end{array}\right\}\end{array}$$Link to original

Church-Turing Thesis

The Church-Turing Thesis states that any language that can be effectively computed by some finite process ($\lambda$-computable) can be recognised by a Turing machine.

Link to original