Turing Machine

Most powerful abstract model of computation. Can simulate any real computer (ignoring efficiency). Modelled by Alan Turing.

A 5-tuple $T = (Q, \Sigma, \Gamma, q_0, \delta)$.

Where:

• $Q$ = finite set of states
• $\Sigma \supset \set{ h_a, h_r }$ = input alphabet
• $\Gamma \supset \set{ \Lambda }$ = tape alphabet
• $q_0$ = start state
• $δ: Q \times \Sigma \rightarrow Q \times \Gamma \times \set{L,R,S}$ = transition function

Components

Tape

Consists of infinite cells. One dimensional. Works as memory.

Cell

A component inside the tape. Can be read from or written to.

Symbol

Element that can be written on a cell. $\Lambda$ means empty.

Tape Head

Points to a cell. Reads from or writes to a cell. Can move left or right or stay at the current cell.

CPU

Has internal state (from an finite set of states). Decides whether to move the tape head, in which direction to move, whether to write on the cell, what to write on the cell. Decisions based on current symbol and current state.

State

State of the machine (or the CPU). Includes 2 halting states:

• $h_a$: Accept
• $h_r$ → Reject

Transition Function

It means, from state $q$, reading $X$:

• Write $Y$
• Move to state $r$
• Move head $D \in {L, R, S}$

Configuration

Represents the current status. $(q, x\underline{a}y) \in Q \times \Gamma^*$. Current symbol under tape head is underlined.

For input string $x$, the machine starts at $(q_0, \Delta x)$.

Configuration Changes

Turing machine changes from 1 configuration to another in each step. Can either move in:

• Single step
  $(q, x\underline{a}y) \vdash_T (r, z\underline{b}w)$
• Multiple steps
  $(q, x\underline{a}y) \vdash_T^* (r, z\underline{b}w)$

Halting

Turing machine halts when it reaches either of the halting states. May run forever without halting.

Acceptance

A string $x$ is accepted iff the machine reaches accepting state i.e. $(q_0, \Delta x) \vdash_T^* (h_a, y\underline{a}z)$.

Examples

Regular Language

TM behaves like FA. Moves right only. Does not modify the tape.

Ends with “aba”

Must read entire input before accepting.

Palindromes

Match first and last symbols. Replace them and repeat. Deterministic.

Functions

A function $f: \Sigma^* \rightarrow \Gamma^*$ is Turing-computable iff a Turing machine $T$ exists that computes $f$.

$T$ computes $f(x)$ iff $(q_0, \Delta x) \vdash_T^* (h_a, \Delta f(x))$.

Partial Functions

When the function is undefined for certain inputs.

TM will produce output only for valid inputs. Loop indefinitely otherwise.

Characteristic Function

For any language $L$ in $\Sigma^*$, its characteristic function $\chi_L: \Sigma^* \rightarrow \set{0,1}$ is defined as:

Computing $\chi_L$ is the same as accepting a language.

A Turing machine may distinguish between strings that are in $L$ and not in $L$ by either:

• accepting or rejecting the string OR
• accepting and ending up in either $(h_a,\Delta 0)$ or $(h_a, \Delta 1)$ configuration

Combination

Suppose $T_1$ and $T_2$ are 2 Turing machines with disjoint non-halting states and transition functions.

$T_1T_2$ denotes a new Turing machine that is a combination of the 2. It starts with the initial state of $T_1$ and executes $T_1$ first. For any move that halts in an accepting state of $T_1$, the machine moves to the initial state of $T_2$ and execute $T_2$. Can also be denoted as $T_1 \rightarrow T_2$.

If either $T_1$ or $T_2$ rejects, $T_1T_2$ also rejects.

Variations

Many minor variations can be defined such as:

• A Turing machine that must move unidirectionally.
• A Turing machine that can either write a symbol or move but not both.
• A Turing machine with multiple tapes and multiple tape heads.
  However the ultimate computing power is unchanged.

n-tape Turing Machine

A Turing machine with multiple tapes. Each tape has its own tape head.

An $n$-tape Turing machine is a 6-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ where:

• $Q$: finite set of states
• $\Sigma$: input alphabet
• $\Gamma$: tape alphabet ($\Sigma \subseteq \Gamma$)
• $q_0$: initial state
• $F$: set of accepting states
• $\delta: Q \times \Gamma^n \rightarrow Q \times \Gamma^n \times \{L, R, S\}^n$: transition function

The machine reads $n$ symbols (one from each tape). Based on the current state and these symbols:

• It moves to a new state
• Writes $n$ symbols (one on each tape)
• Moves each tape head independently (Left, Right, or Stay)

Non-deterministic TM

Aka. NTM. Same as the deterministic TM except the transition function’s output is a set of configurations.

For any non-deterministic TM, there exists a deterministic TM that accept the same language.

Encoding

A TM can be represented as a finite string over a finite alphabet. This encoding, written $\langle T \rangle$ or $e(T)$, describes the TM’s states, alphabets, and transition function.

Encoding is what allows a TM to take another TM as input. Without it, a TM cannot reason about other TMs.

Example

TM $T$ accepts $\{a\}$: states $q_0, q_1, h_a, h_r$; transitions $\delta(q_0, a) = (q_1, a, R)$ and $\delta(q_1, \Lambda) = (h_a, \Lambda, S)$.

Each transition is encoded as a 5-tuple $(q,\, X,\, r,\, Y,\, D)$. Tuples are separated by #:

$\langle T \rangle = \texttt{q0,a,q1,a,R\#q1,B,ha,B,S}$

States, symbols, and directions are replaced with agreed-upon tokens. The exact scheme is arbitrary as long as it is consistent and decodable.

Universal TM

Denoted by $T_u$ A Turing machine that can run any arbitrary program with an arbitrary data set (input to the program).

• The program is expressed as a string that specifies another special purpose TM, $T_1$
• Data set is a string $w$ (input to $T_1$)

$T_u$ simulates the processing of $w$ by $T_1$.

Accept vs Decide

A language $L$ is Turing-acceptable iff a Turing machine $T$ exists that accepts $L$.

$T$ accepts $L$ iff $T$ halts in $h_a$ for every $x \in L$. For $x \notin L$, $T$ may:

• Halt at $h_r$ OR
• Loop forever

A language $L$ is Turing-decidable iff a Turing machine $T$ exists that decides $L$.

$T$ decides $L$ iff for every $x \in \Sigma^*$, $T$ halts and computes $\chi_L(x)$.

Limits

Not all problems are solvable. Some problems are undecidable — no Turing machine can solve them.