11.1 Machine Definitions

A Turing machine is a formal model of an algorithm. It describes computation using a finite set of rules and an unbounded tape.

The machine has three main parts:

Part	Role
Tape	stores symbols
Head	reads and writes one cell at a time
Finite control	stores the current state

The tape is divided into cells:

\cdots,\ c_{-2},\ c_{-1},\ c_0,\ c_1,\ c_2,\ \cdots

Each cell contains one symbol. Most cells are blank. The blank symbol is usually written as:

\sqcup

The tape is idealized as unbounded. This means the machine always has more space available if computation needs it.

At every step, the machine does exactly four things:

reads the current tape symbol
writes a tape symbol
moves left or right
changes state

A move direction is written as:

L

R

Some versions also allow a stay-put move $S$ , but $L$ and $R$ are enough for the standard theory.

A deterministic Turing machine is usually defined as a tuple:

M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}})

Here each component has a precise meaning.

Symbol	Meaning
$Q$	finite set of states
$\Sigma$	input alphabet
$\Gamma$	tape alphabet
$\delta$	transition function
$q_0$	start state
$q_{\mathrm{accept}}$	accepting halt state
$q_{\mathrm{reject}}$	rejecting halt state

The set $Q$ is finite. A state records the machine’s internal condition.

The input alphabet $\Sigma$ contains the symbols allowed in the input word. For binary strings, we often use:

\Sigma={0,1}

The tape alphabet $\Gamma$ contains every symbol the machine may read or write. It includes the input alphabet and the blank symbol:

\Sigma \subseteq \Gamma

\sqcup \in \Gamma

Usually the blank symbol is not part of the input alphabet:

\sqcup \notin \Sigma

The transition function gives the rule for one computation step:

\delta : Q \times \Gamma \to Q \times \Gamma \times {L,R}

If:

\delta(q,a)=(q',b,D)

then the instruction means:

Component	Meaning
$q$	current state
$a$	symbol currently being read
$q'$	next state
$b$	symbol to write
$D$	direction to move

For example:

\delta(q_0,1)=(q_1,0,R)

means: if the machine is in state $q_0$ and reads $1$ , it writes $0$ , moves right, and enters state $q_1$ .

The states $q_{\mathrm{accept}}$ and $q_{\mathrm{reject}}$ are halting states. Once the machine enters one of them, the computation stops.

For a decision problem, accepting means the answer is yes. Rejecting means the answer is no.

For machines that compute functions, we often use one halting state instead:

q_{\mathrm{halt}}

Then the output is read from the tape after the machine stops.

Initial Configuration

An input word has the form:

w=a_1a_2\cdots a_n

where each symbol belongs to the input alphabet:

a_i \in \Sigma

At the start, the tape contains the input symbols on consecutive cells:

a_1,\ a_2,\ \ldots,\ a_n

All other cells contain blanks:

\sqcup

The head begins on the first input symbol, and the machine begins in the start state:

q_0

If the input word is empty, the head begins on a blank cell.

Deterministic Behavior

The machine described above is deterministic. This means that every state-symbol pair determines at most one next move.

So for a fixed pair:

(q,a)

there is only one possible instruction:

(q,a) \mapsto (q',b,D)

There is no guessing, randomness, or choice. If the same machine starts with the same input twice, it follows exactly the same sequence of steps.

Partial Transition Functions

Some definitions make the transition function partial:

\delta : Q \times \Gamma \rightharpoonup Q \times \Gamma \times {L,R}

The symbol $\rightharpoonup$ means a partial function.

If $\delta(q,a)$ is undefined, the machine halts. This convention avoids needing explicit accepting and rejecting states in some settings.

Both styles define the same class of computable functions and decidable languages.

Example: Scanning to the End of a Word

Let the input alphabet be:

\Sigma={0,1}

Let the tape alphabet be:

\Gamma={0,1,\sqcup}

Consider a machine that scans right until it finds the first blank cell.

Use states:

Q={q_0,q_{\mathrm{halt}}}

Define the transition rules:

\delta(q_0,0)=(q_0,0,R)

\delta(q_0,1)=(q_0,1,R)

\delta(q_0,\sqcup)=(q_{\mathrm{halt}},\sqcup,R)

On input:

1011

the machine reads the symbols one by one:

1,\ 0,\ 1,\ 1

Then it reaches the first blank:

\sqcup

and halts.

The machine does not change the input. Its purpose is only to show how a transition function controls movement.

A Turing machine is finite as a description, even though its tape is unbounded. This matters because machines can be encoded as strings. Once machines can be encoded, one machine can receive another machine as input. This idea leads to universal machines and the halting problem.