14. Introduction to Turing Machines#
Introduction#
This section provides a comprehensive introduction to Turing Machines, one of the most fundamental concepts in theoretical computer science. Named after the British mathematician Alan Turing, these abstract machines serve as a mathematical model of computation that, despite their simplicity, can simulate any computer algorithm. Turing Machines are central to our understanding of what problems are computationally solvable. They form the foundation of the Church-Turing thesis, which suggests that any function that can be effectively calculated can be computed by a Turing Machine. This concept has profound implications for computer science, mathematics, and philosophy.
1. Definition of Turing Machines#
1.1 Definition#
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, the Turing machine can simulate the logic of any computer algorithm.
A Turing machine can be formally defined as a 7-tuple: \(M=(Q,\Sigma,\Gamma,T, H, \delta, \triangle)\) where:
\(Q\) is a finite set of states with exactly one START state and zero or more HALT states.
\(\Sigma\) is a finite set of input symbols that can appear in the original input string provided to the machine.
\(\Gamma\) is a finite set of tape symbols the machine can write on the tape, including input symbols plus extra symbols like markers.
\(T\) is a TAPE consisting of a sequence of numbered cells, each holding either a single character or a blank symbol. The input word is written on the tape with one character per cell, starting from the leftmost cell (cell 1). All remaining cells on the tape are initially filled with blanks.
\(H\) is a TAPE HEAD that, in a single step, can read the contents of a cell on the tape, overwrite it with another character, and then move either one cell to the left or right. At the start of computation, the tape head begins by reading the input in the leftmost cell (cell 1).
\(\delta\) is a program or a set of transition functions that tells the machine what to do based on the current state and the symbol under the head.
\(\triangle\) is a blank symbol, which is not part of input symbols or tape symbols.
1.2 Code Walkthrough: The TuringMachine Simulator#
Concept#
A Turing machine is formally defined as a 7-tuple: $\(M = (Q,\; \Sigma,\; \Gamma,\; T,\; H,\; \delta,\; \triangle)\)$
The TuringMachine class below provides a direct, one-to-one mapping of this
7-tuple into Python. It is the foundational class for all concrete Turing
machines in this chapter — create_anbn_tm() and create_palindrome_tm() both
instantiate it.
⚠️ This class is defined twice in this chapter. A second, palindrome-specific version appears in Section 2.2.4 (Code Cell 4). That version overwrites this one when its cell runs. Keep the two cells in execution order to avoid unexpected behaviour — see Section 2.2.4’s pre-code Markdown for details.
Formal notation ↔ Python mapping#
Formal component |
Python parameter |
Notes |
|---|---|---|
\(Q\) (states) |
|
|
\(\Sigma\) (input symbols) |
|
|
\(\Gamma\) (tape symbols) |
|
|
\(T\) (tape) |
|
1-indexed |
\(H\) (tape head) |
|
integer ≥ 1; never decremented below 1 (left-boundary rule) |
\(\delta\) (transition function) |
|
|
\(\triangle\) (blank symbol) |
|
must not be in \(\Sigma\); fills all cells beyond the input |
Method roles#
Method |
What it does |
Returns |
|---|---|---|
|
Writes \(s\) to tape, resets head and state |
— |
|
Reads \(\Gamma\) symbol under head; returns \(\triangle\) if beyond tape |
symbol |
|
Extends tape if needed, writes symbol |
— |
|
Executes one \(\delta\) transition |
|
|
Loops |
|
|
Returns tape as string, trimming trailing blanks |
|
|
Prints state, tape, and head-position indicator |
— |
Running outside Jupyter#
Save the class to turing_machine.py. No Jupyter-specific calls are present.
The concrete machines in later sections import it as a dependency — add
from turing_machine import TuringMachine at the top of each.
# ── FORMAL GROUNDING ────────────────────────────────────────────────────────
# Implements M = (Q, Σ, Γ, T, H, δ, △) — the standard 7-tuple Turing Machine.
# Reference: Sipser §3.1 Definition 3.3; Cohen Chapter 19; Hopcroft §8.2
#
# Design note: tape is 1-indexed (tape[0] = None) to match the textbook's
# convention that computation starts at "cell 1", not "cell 0".
# ────────────────────────────────────────────────────────────────────────────
class TuringMachine:
"""
General-purpose Turing Machine simulator.
Instantiation: TuringMachine(states, input_symbols, tape_symbols,
transition_function, blank_symbol)
Execution: set_input(s) → run() → check result string.
HALT states: any state whose name starts with 'HALT' (e.g. 'HALT', 'HALT1').
START state: must be named exactly 'START'.
Note: A second version of this class is defined in Section 2.2.4 with
palindrome-specific naming conventions. That version overwrites this one
when its cell runs — keep execution order in mind.
"""
def __init__(self, states, input_symbols, tape_symbols,
transition_function, blank_symbol):
# ── Validate required structural properties ───────────────────────
# The 7-tuple requires exactly one designated start state.
if 'START' not in states:
raise ValueError("states must include a 'START' state")
# △ ∉ Σ — the blank symbol is not an input symbol (Definition 3.3).
if blank_symbol in input_symbols:
raise ValueError("blank_symbol cannot be part of input_symbols")
# ── Store the 7-tuple components ──────────────────────────────────
self.states = states # Q
self.input_symbols = input_symbols # Σ
self.tape_symbols = tape_symbols # Γ
self.transition_function = transition_function # δ: Q×Γ → Q×Γ×{L,R}
self.blank_symbol = blank_symbol # △
# Derive halt states: any state name beginning with 'HALT'.
# Convention allows multiple halt states (e.g. 'HALT_ACCEPT', 'HALT1').
self.halt_states = {q for q in states if q.startswith('HALT')}
# ── Initialise operational components (T and H) ──────────────────
# tape[0] = None so that tape[1] aligns with "cell 1" in the textbook.
self.tape = [] # T: will be populated by set_input()
self.head_position = 1 # H: starts at leftmost cell (cell 1)
self.current_state = 'START' # machine begins in the START state
def set_input(self, input_string):
"""
Write input_string to the tape and reset the machine to its initial
configuration: head at cell 1, state = START.
"""
# Validate: every character must be in Σ
for symbol in input_string:
if symbol not in self.input_symbols:
raise ValueError(f"Symbol '{symbol}' not in input_symbols {self.input_symbols}")
# Build tape: [None, w₁, w₂, …, wₙ]
# None at index 0 makes tape[i] correspond to "cell i" (1-indexed).
self.tape = [None] + list(input_string)
self.head_position = 1
self.current_state = 'START'
def get_current_symbol(self):
"""
Read the symbol under the tape head (Γ symbol at cell head_position).
Returns △ if the head has moved beyond the written portion of the tape —
the tape is infinite to the right, so unwritten cells contain blanks.
"""
if self.head_position >= len(self.tape):
return self.blank_symbol # cell is blank (tape extends infinitely)
return self.tape[self.head_position]
def write_symbol(self, symbol):
"""
Write `symbol` to the cell at head_position.
Extends the tape with blanks if the head has moved past the current end.
"""
# Grow tape to reach the current head position
while self.head_position >= len(self.tape):
self.tape.append(self.blank_symbol)
self.tape[self.head_position] = symbol
def step(self):
"""
Execute one transition: δ(current_state, current_symbol) → (q', a', d).
Implements the single-step semantics:
1. Read symbol under head.
2. Look up δ.
3. Write new symbol, update state, move head.
Left-boundary rule: head never moves left of cell 1 (tape is one-way
infinite to the right). Moving left from cell 1 keeps head at cell 1.
Returns:
True — step was taken successfully; machine may continue.
False — machine is in a HALT state or no valid transition exists.
"""
# ── Check halt condition before attempting a transition ───────────
if self.current_state in self.halt_states:
return False # already halted; no further transitions
# ── Read ─────────────────────────────────────────────────────────
current_symbol = self.get_current_symbol()
# ── Look up δ(q, a) ──────────────────────────────────────────────
key = (self.current_state, current_symbol)
if key not in self.transition_function:
return False # no valid transition → implicit rejection
next_state, new_symbol, direction = self.transition_function[key]
# ── Write, transition, move ───────────────────────────────────────
self.current_state = next_state
self.write_symbol(new_symbol)
if direction == 'L':
# Left-boundary: head cannot go below cell 1.
self.head_position = max(1, self.head_position - 1)
elif direction == 'R':
self.head_position += 1
else:
raise ValueError(f"direction must be 'L' or 'R', got '{direction}'")
return True
def run(self, max_steps=10000):
"""
Run until HALT, rejection, or max_steps exceeded.
The three outcomes correspond to the three input classes:
'accepted' → string is in L(M) [ACCEPT class]
'rejected' → machine halted without accepting [REJECT class]
'timeout' → machine still running at max_steps [proxy for LOOP class]
Reference: Section 5 (Three Classes of Input Strings).
"""
steps = 0
while steps < max_steps:
if self.current_state in self.halt_states:
return 'accepted'
if not self.step():
return 'rejected'
steps += 1
return 'timeout' # approximation of the LOOP class
def get_tape_contents(self):
"""
Return the tape as a string, trimming trailing blanks.
Skips tape[0] (the None placeholder at index 0).
"""
if len(self.tape) <= 1:
return ""
rightmost = len(self.tape) - 1
# Find the last non-blank cell
while rightmost > 0 and self.tape[rightmost] == self.blank_symbol:
rightmost -= 1
return ''.join(self.tape[1:rightmost + 1])
def print_configuration(self):
"""
Print the current tape, state, and head-position indicator.
Useful for step-by-step tracing.
"""
tape_content = self.tape[1:] if len(self.tape) > 1 else []
# Extend for display if head has moved past the written portion
while len(tape_content) < self.head_position:
tape_content.append(self.blank_symbol)
tape_str = ' '.join(str(s) for s in tape_content)
# Two characters per symbol (symbol + space), adjusted for 1-indexing
head_indicator = ' ' * (2 * (self.head_position - 1)) + '^'
print(f"State: {self.current_state}")
print(f"Tape: {tape_str}")
print(f"Head: {head_indicator}")
1.3 Turing Machine tape#
The following image depicts a Turing machine tape. It shows a horizontal tape divided into cells, with each cell numbered sequentially from 1 to 5 across the top. The contents of each cell are clearly marked:
Cell 1 contains the symbol “a”
Cell 2 contains the symbol “b”
Cell 3 contains the symbol “a”
Cells 4 and 5 contain the blank symbol \(\triangle\)
An ellipsis “…” indicates that the tape continues indefinitely to the right.
A tape head indicator (shown as an upward-pointing arrow) is positioned beneath Cell 1, pointing to the first “a” symbol. The text “TAPE HEAD” appears below the arrow to clearly label this component. This illustration represents the conceptual model of a Turing machine’s memory structure, showing the current configuration of the tape and the position of the read/write head. In Turing machine theory, the tape head can read the current symbol, write a new symbol, and move left or right according to the machine’s transition rules.
Figure 1: The Turing Machine Tape#
Note: This cell is rendering only — it loads a pre-made SVG file and displays it as Figure 1. There is no algorithm to trace here. Focus on the figure itself and use the table below to connect each visual element to the formal 7-tuple.
The tape is the central data structure of a Turing machine. Unlike the finite memory of a DFA or the stack of a PDA, the tape is infinite to the right and readable and writable — the tape head can both read the current cell and overwrite it in a single step.
Reading Figure 1:
Visual element |
Formal component |
Notes |
|---|---|---|
Numbered cells (1, 2, 3, …) |
\(T\) (the tape) |
Cells are 1-indexed; Python uses |
|
Input string \(w = \mathtt{aba}\) written left-to-right in \(\Sigma\) |
One symbol per cell |
\(\triangle\) in cells 4, 5 |
Blank symbol \(\triangle \in \Gamma \setminus \Sigma\) |
All cells beyond the input are initially blank |
|
Tape extends infinitely to the right |
No right boundary |
Upward arrow under cell 1 |
Tape head \(H\), initially at position 1 |
Head reads, writes, and moves in each step |
What the tape head does in one step (from Section 3.3): $\(\delta(q, a) = (q', a', d) \implies \text{read } a,\; \text{write } a',\; \text{move } d \in \{L, R\}\)$
Running outside Jupyter. The load_svg_from_file and display(HTML(...))
calls are Jupyter-specific. To view Figure 1 outside Jupyter, open
tape_head.svg directly in any browser.
# from IPython.display import SVG
# SVG('tape_head.svg')
from IPython.display import SVG, display, HTML, Markdown
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
# Load SVG from file
def load_svg_from_file(filename):
"""Load SVG content from a file"""
with open(filename, 'r', encoding='utf-8') as f:
svg_content = f.read()
print(f"SVG loaded from {filename}")
return svg_content
loaded_svg = load_svg_from_file('tape_head.svg')
html_with_caption = f"""
<figure style="text-align: center;">
{loaded_svg}
<figcaption style="margin-top: 10px; font-style: italic; color: #666;">
Figure 1: a Turing machine tape
</figcaption>
</figure>
"""
display(HTML(html_with_caption))
SVG loaded from tape_head.svg
2. Examples of Turing Machines#
Let’s implement some simple Turing machines to illustrate the concept.
2.1 Example 1: A Turing Machine that Accepts \(a^nb^n\)#
2.1.1 Definition:#
Using the formal definition structure \(M=(Q,\Sigma,\Gamma,T, H, \delta, \triangle)\), we define the Turing machine that accepts the language \(L = \{a^nb^n, n \geq 0 \}\) as follows:
\(Q: \{1START, 2, 3, 4, 5, 6HALT\}\), the finite set of states
\(\Sigma = \{a, b\}\), the finite set of input symbols
\(\Gamma = \{a, b, A, B\}\), the finite set of tape symbols (excluding the blank symbol)
\(T\): the tape consisting of cells, with the input starting at cell 1. Initially it contains the input string, with one character per cell. All remaining cells are filled with blank symbols.
\(H\): the tape head that starts at position 1. It can read, write, and move left or right in each step.
\(\delta\): the transition function defined as follows:
δ(START, a) = (2, A, R)
δ(START, △) = (HALT, △, R)
δ(2, a) = (2, a, R)
δ(2, B) = (2, B, R)
δ(2, b) = (3, B, L)
δ(3, B) = (3, B, L)
δ(3, a) = (4, a, L)
δ(3, A) = (5, A, R)
δ(4, a) = (4, a, L)
δ(4, A) = (START, A, R)
δ(5, B) = (5, B, R)
δ(5, △) = (HALT, △, R)
\(△\): the blank symbol, it is not part of the input or tape symbol sets.
2.1.2 Machine Diagram:#
The following diagram visualizes the state transitions of this Turing machine.
stateDiagram-v2
accTitle: State Transitions of a Turing machine
accDescr: a diagram representing state transitions of a Turing machine
direction LR
START: 1 START
q2: 2
q3: 3
q4: 4
q5: 5
HALT:6 HALT
START --> q2: (a,A,R)
START --> HALT: (△,△,R)
q2 --> q2: (a,a,R)
q2 --> q2: (B,B,R)
q2 --> q3: (b,B,L)
q3 --> q3: (B,B,L)
q3 --> q4: (a,a,L)
q3 --> q5: (A,A,R)
q4 --> q4: (a,a,L)
q4 --> START: (A,A,R)
q5 --> q5: (B,B,R)
q5 --> HALT: (△,△,R)
classDef start fill:#9f6,stroke:#333,stroke-width:2px
classDef halt fill:#f96,stroke:#333,stroke-width:2px
classDef state fill:#bbf,stroke:#333,stroke-width:1px
class START start
class HALT halt
class q2,q3,q4,q5 state
2.1.3 How this Turing Machine Works:#
This Turing machine is designed to recognize strings of the form \(a^nb^n\), which means n ‘a’s followed by exactly n ‘b’s (where n ≥ 0). Let us explain in detail how this machine processes inputs. The machine works by systematically “matching and marking” ‘a’s and ‘b’s. It converts the leftmost ‘a’ to ‘A’ (marking it as processed); scans right to find the leftmost ‘b’ and converts it to ‘B’ (marking it as processed); returns to the beginning to repeat the process with the next ‘a’. When all pairs are matched, it verifies that all input has been processed. If there are equal numbers of ‘a’s and ‘b’s, it accepts the input; otherwise, it rejects the input.
Let us examine each state and its role:
State 1 (START): Processes the leftmost unmarked ‘a’ or accepts if the input is blank
State 2: Scans right looking for the leftmost unmarked ‘b’
State 3: After marking ‘b’, scans left looking for ‘a’s or ‘A’s
State 4: After finding an unmarked ‘a’, scans left to return to the beginning
State 5: After finding a marked ‘A’, verifies all ‘b’s have been processed
For example, let us process an input: “aabb”
Start (State 1): Machine reads ‘a’, replaces it with ‘A’, moves right, enters State 2. Tape: Aabb
State 2: Reads ‘a’, keeps it, moves right, stays in State 2. Tape: Aabb
State 2 → State 3: Reads ‘b’, replaces it with ‘B’, moves left, enters State 3. Tape: AabB
State 3: Reads ‘a’, moves left, enters State 4. Tape: AabB
State 4 → State 1: Reads ‘A’, moves right, returns to State 1. Tape: AabB
State 1 → State 2: Reads ‘a’, replaces it with ‘A’, moves right, enters State 2. Tape: AAbB
State 2 → State 3: Reads ‘B’, keeps it, moves right, stays in State 2. Then reads ‘b’, replaces it with ‘B’, moves left, enters State 3. Tape: AABB
State 3 → State 5: Reads ‘B’, keeps it, moves left, stays in State 3. Then reads ‘A’, moves right, enters State 5. Tape: AABB
State 5 → HALT: Reads ‘B’, keeps it, moves right, stays in State 5. Then reads blank, moves right, enters HALT state. Input is accepted.
2.1.4 Code Walkthrough: Turing Machine for \(L = \{a^n b^n \mid n \geq 0\}\)#
Concept#
This function instantiates the TuringMachine class (defined in Code Cell 1) with
the specific transition function for recognising \(\{a^n b^n\}\).
Dependency: This function calls TuringMachine(...). Run Code Cell 1 before
this cell. If Code Cell 4 (palindrome machine) has also been run, the
TuringMachine class in the kernel will be the palindrome-specific version —
create_anbn_tm() will still run, but HALT detection will differ. Re-run Code
Cell 1 to restore the general-purpose class if needed.
Algorithm: mark-and-match#
The machine repeatedly matches one a with one b using a two-symbol marking
scheme: a → A (processed \(a\)) and b → B (processed \(b\)). Each pass through
the input matches exactly one \(a\)–\(b\) pair.
State |
Role |
Textbook description |
|---|---|---|
|
Process leftmost |
\(\delta(\text{START}, a) = (2, A, R)\); \(\delta(\text{START}, \triangle) = (\text{HALT}, \triangle, R)\) |
|
Scan right to find leftmost |
Skips |
|
Scan left to return toward beginning |
Skips |
|
Scan left past remaining |
Skips |
|
Verify all |
Skips |
|
Accept |
— |
Notation mapping: transitions in this cell#
Each line in transition_function encodes one \(\delta\) rule. Format:
('state', 'read') : ('new_state', 'write', 'direction')
corresponds to the formal notation: $\(\delta(\mathtt{state},\; \mathtt{read}) = (\mathtt{new\_state},\; \mathtt{write},\; \mathtt{direction})\)$
Running outside Jupyter#
python anbn_tm.py
Include the TuringMachine class at the top of the file (or import it from
turing_machine.py) before defining create_anbn_tm.
# ── FORMAL GROUNDING ────────────────────────────────────────────────────────
# Implements the Turing machine for L = {aⁿbⁿ | n ≥ 0}.
# Algorithm: "mark-and-match" — repeatedly convert one 'a'→'A' and one 'b'→'B'
# per pass until no unmarked 'a's remain, then verify no unmarked 'b's remain.
# Reference: Cohen Chapter 19 Example; Sipser §3.1
# ────────────────────────────────────────────────────────────────────────────
def create_anbn_tm():
"""
Build and return a TuringMachine that accepts L = {aⁿbⁿ | n ≥ 0}.
Depends on: TuringMachine class from Code Cell 1.
States: START (=1), 2, 3, 4, 5, HALT (=6).
Auxiliary tape symbols: A (marks a processed 'a'), B (marks a processed 'b').
"""
# Q — state set; 'HALT' prefix triggers halt detection in TuringMachine
states = {'START', '2', '3', '4', '5', 'HALT'}
# Σ — input alphabet
input_symbols = {'a', 'b'}
# Γ — tape alphabet: Σ ∪ {auxiliary markers, blank}
# 'A' = matched/processed 'a'; 'B' = matched/processed 'b'
tape_symbols = {'a', 'b', 'A', 'B', '△'}
blank_symbol = '△'
# δ — transition function: (state, read) → (new_state, write, direction)
# ─────────────────────────────────────────────────────────────────────────
# Each entry is one formal transition δ(q, a) = (q', a', d).
transition_function = {
# ── State START (state 1): process leftmost unmatched 'a' ────────
# δ(START, a) = (2, A, R) — mark 'a' as matched, start scanning right
('START', 'a'): ('2', 'A', 'R'),
# δ(START, △) = (HALT, △, R) — no more 'a's: accept (empty or all matched)
('START', '△'): ('HALT', '△', 'R'),
# ── State 2: scan right to find the leftmost unmatched 'b' ───────
# δ(2, a) = (2, a, R) — skip unmatched 'a' (not yet our turn)
('2', 'a'): ('2', 'a', 'R'),
# δ(2, B) = (2, B, R) — skip already-matched 'b'
('2', 'B'): ('2', 'B', 'R'),
# δ(2, b) = (3, B, L) — found a 'b': mark it, begin leftward return
('2', 'b'): ('3', 'B', 'L'),
# ── State 3: scan left, decide what we landed on ─────────────────
# δ(3, B) = (3, B, L) — skip matched 'b's while scanning left
('3', 'B'): ('3', 'B', 'L'),
# δ(3, a) = (4, a, L) — found an unmatched 'a': continue scanning left
('3', 'a'): ('4', 'a', 'L'),
# δ(3, A) = (5, A, R) — found a matched 'A': all a's are matched → verify b's
('3', 'A'): ('5', 'A', 'R'),
# ── State 4: scan left back to the left edge (past all 'a's) ─────
# δ(4, a) = (4, a, L) — keep scanning left past unmatched 'a's
('4', 'a'): ('4', 'a', 'L'),
# δ(4, A) = (START, A, R) — hit a marked 'A' → return to START for next pass
('4', 'A'): ('START', 'A', 'R'),
# ── State 5: verify all 'b's have been matched ───────────────────
# δ(5, B) = (5, B, R) — skip matched 'B's: all good so far
('5', 'B'): ('5', 'B', 'R'),
# δ(5, △) = (HALT, △, R) — reached end of tape with all B's matched: accept
('5', '△'): ('HALT', '△', 'R'),
}
return TuringMachine(states, input_symbols, tape_symbols,
transition_function, blank_symbol)
# ── TEST SUITE ────────────────────────────────────────────────────────────────
# Expected outcomes:
# In L: "" "ab" "aabb" "aaabbb" → accepted
# Not in L: "abb" "aaabb" "bbaa" → rejected
anbn_tm = create_anbn_tm()
test_strings = ["", "ab", "aabb", "abb", "aaabb", "aaabbb", "bbaa"]
for test_str in test_strings:
try:
anbn_tm.set_input(test_str)
result = anbn_tm.run(1000)
final_tape = anbn_tm.get_tape_contents()
print(f"Input: '{test_str:8s}' Result: {result:10s} "
f"Final tape: '{final_tape}' Final state: {anbn_tm.current_state}")
except ValueError as e:
print(f"Input: '{test_str}', Error: {e}")
Input: ' ' Result: accepted Final tape: '' Final state: HALT
Input: 'ab ' Result: accepted Final tape: 'AB' Final state: HALT
Input: 'aabb ' Result: accepted Final tape: 'AABB' Final state: HALT
Input: 'abb ' Result: rejected Final tape: 'ABb' Final state: 5
Input: 'aaabb ' Result: rejected Final tape: 'AAABB' Final state: 2
Input: 'aaabbb ' Result: accepted Final tape: 'AAABBB' Final state: HALT
Input: 'bbaa ' Result: rejected Final tape: 'bbaa' Final state: START
2.2 Example 2: A Turing Machine that Accepts PALINDROME#
2.2.1 Definition:#
We define the Turing machine that accepts the language PALINDROME as follows:
\(Q: \{1START, 2, 3, 4, 5, 6, 7, 8HALT\}\), the finite set of states
\(\Sigma = \{a, b\}\), the finite set of input symbols
\(\Gamma = \{a, b\}\), the finite set of tape symbols (excluding the blank symbol)
\(T\): the tape consisting of cells, with the input starting at cell 1.
\(H\): the tape head that starts at position 1.
\(\delta\): the transition function defined as follows:
δ(1_START, a) = (2, △, R)
δ(1_START, b) = (5, △, R)
δ(1_START, △) = (8_HALT, △, R)
δ(2, a) = (2, a, R)
δ(2, b) = (2, b, R)
δ(2, △) = (3, △, L)
δ(3, a) = (4, △, L)
δ(3, △) = (8_HALT, △, R)
δ(4, a) = (4, a, L)
δ(4, b) = (4, b, L)
δ(4, △) = (1_START, △, R)
δ(5, a) = (5, a, R)
δ(5, b) = (5, b, R)
δ(5, △) = (6, △, L)
δ(6, b) = (7, △, L)
δ(6, △) = (8_HALT, △, R)
δ(7, a) = (7, a, L)
δ(7, b) = (7, b, L)
δ(7, △) = (1_START, △, R)
\(△\): the blank symbol, it is not part of the input or tape symbol sets.
2.2.2 Machine Diagram:#
The following diagram visualizes the state transitions of this Turing machine.
stateDiagram-v2
accTitle: State Transitions of a Turing machine
accDescr: a diagram representing state transitions of a Turing machine
direction LR
START: 1 START
q2: 2
q3: 3
q4: 4
q5: 5
q6: 6
q7: 7
HALT: 8 HALT
START --> q2: (a,Δ,R)
START --> q5: (b,Δ,R)
START --> HALT: (Δ,Δ,R)
q2 --> q2: (a,a,R)
q2 --> q2: (b,b,R)
q2 --> q3: (Δ,Δ,L)
q3 --> q4: (a,Δ,L)
q3 --> HALT: (Δ,Δ,R)
q4 --> q4: (a,a,L)
q4 --> q4: (b,b,L)
q4 --> START: (Δ,Δ,R)
q5 --> q5: (a,a,R)
q5 --> q5: (b,b,R)
q5 --> q6: (Δ,Δ,L)
q6 --> q7: (b,Δ,L)
q6 --> HALT: (Δ,Δ,R)
q7 --> q7: (a,a,L)
q7 --> q7: (b,b,L)
q7 --> START: (Δ,Δ,R)
classDef start fill:#9f6,stroke:#333,stroke-width:2px
classDef halt fill:#f96,stroke:#333,stroke-width:2px
classDef state fill:#bbf,stroke:#333,stroke-width:1px
class START start
class HALT halt
class q2,q3,q4,q5,q6,q7 state
2.2.3 How this Turing Machine Works:#
A palindrome is a string that reads the same forward and backward, like “aba” or “abba”. Let us explain in detail how this machine processes inputs. The machine uses a systematic approach of “matching and erasing” from the outside inward. It examines the leftmost character and travels to the rightmost character to check if it’s a match. If they match, erases both and repeats the process; if they don’t match or the machine encounters an unexpected pattern, it rejects the input. If it successfully processes the entire string (reaching the middle with all matches), it accepts the input.
Two Processing Paths:
Upper path (States 2-3-4) for processing ‘a’ characters
Lower path (States 5-6-7) for processing ‘b’ characters
Let us examine each state and its role:
State 1 (START): Examines the first character and directs processing based on whether it’s ‘a’, ‘b’, or blank
State 2: After seeing ‘a’ at the start, scans right until reaching the end of the string
State 3: Looks for a matching ‘a’ at the end of the string
State 4: After finding and erasing the matching ‘a’, returns to the start for the next iteration
State 5: After seeing ‘b’ at the start, scans right until reaching the end of the string
State 6: Looks for a matching ‘b’ at the end of the string
State 7: After finding and erasing the matching ‘b’, returns to the start for the next iteration
State 8 (HALT): Accepts the input as a palindrome
For example, let us process an input: “aba”
Start (State 1): * Machine reads ‘a’, erases it (writes blank Δ), moves right, and enters State 2. Tape: Δba
State 2: Reads ‘b’, keeps it, moves right, stays in State 2. Tape: Δba
State 2 (continued): Reads ‘a’, keeps it, moves right, stays in State 2. Tape: Δba
State 2 → State 3: Reaches the end (reads blank), moves left, enters State 3. Tape: Δba
State 3 → State 4: Reads ‘a’, erases it (writes blank), moves left, enters State 4. Tape: ΔbΔ
State 4 → State 1: Reads ‘b’, keeps it, moves left, stays in State 4. Then reads blank, moves right, returns to State 1. Tape: ΔbΔ
State 1 → State 5: Reads ‘b’, erases it (writes blank), moves right, enters State 5. Tape: ΔΔΔ
State 5 → State 6: Reads blank, moves left, enters State 6. Tape: ΔΔΔ
State 6 → State 8: Reads blank, moves right, enters State 8 (HALT). Input accepted as a palindrome
2.2.4 Code Walkthrough: Turing Machine for PALINDROME#
Concept#
This cell implements a Turing machine that accepts the palindrome language over \(\{a, b\}^*\). The algorithm is “match and erase from the outside inward”:
Read and erase the leftmost character.
Scan to the rightmost character and check if it matches.
If it matches, erase it and repeat; if not, reject.
If the tape becomes empty (or holds only blanks), accept.
Two processing paths handle the two possible first characters:
Path |
States |
Triggered by |
|---|---|---|
Upper path |
2 → 3 → 4 → START |
First character is |
Lower path |
5 → 6 → 7 → START |
First character is |
⚠️ Critical: this cell redefines the TuringMachine class#
This cell contains a second, different definition of
TuringMachine. When this cell runs, it overwrites the class defined in Code Cell 1.The two versions are not interchangeable:
Feature
Cell 1
TuringMachineThis cell’s
TuringMachineInitial state
'START'
'1_START'(hardcoded)HALT detection
state.startswith('HALT')
'8_HALT' in state(substring)Input validation
Yes (
raise ValueError)No
Blank-symbol validation
Yes
No
After this cell runs, calling
create_anbn_tm()will use the palindromeTuringMachineclass. Because that class hardcodescurrent_state = '1_START'and detects HALT via'8_HALT' in state, the \(a^n b^n\) machine (which uses state'START'and halt state'HALT') will behave incorrectly. Re-run Code Cell 1 to restore the general-purpose class before re-runningcreate_anbn_tm().
Dependency and pipeline#
TuringMachine (redefined in this cell)
↑
create_palindrome_tm() ─→ test_palindrome_tm() ─→ [output]
test_palindrome_tm() is defined before it calls create_palindrome_tm() in
source order — both are in the same cell so Python sees both at definition time.
Running outside Jupyter#
python palindrome_tm.py
The if __name__ == "__main__": guard at the bottom means test_palindrome_tm()
runs automatically when the file is executed directly.
# ── FORMAL GROUNDING ────────────────────────────────────────────────────────
# Implements the palindrome-recognising Turing machine.
# Algorithm: "match and erase from outside inward".
# States: 1_START, 2, 3, 4 (a-path), 5, 6, 7 (b-path), 8_HALT.
#
# ⚠️ This cell redefines TuringMachine with palindrome-specific conventions:
# - Initial state hardcoded as '1_START' (not 'START')
# - HALT detection via '8_HALT' in state name (substring check)
# After this cell runs, the Cell 1 class is overwritten in the kernel.
# Re-run Cell 1 before using create_anbn_tm() again.
# Reference: Cohen Chapter 19; Sipser §3.1
# ────────────────────────────────────────────────────────────────────────────
def create_palindrome_tm():
"""
Build and return a TuringMachine that accepts the palindrome language over {a,b}*.
Uses the palindrome-specific TuringMachine class defined later in this cell.
State naming: '1_START', '2'–'7', '8_HALT' (matches state diagram labels).
"""
states = {'1_START', '2', '3', '4', '5', '6', '7', '8_HALT'}
input_symbols = {'a', 'b'}
# Γ = Σ ∪ {△} — no auxiliary markers; palindrome is verified by erasure
tape_symbols = {'a', 'b', '△'}
blank_symbol = '△'
# δ — transition function for the palindrome machine
# Two symmetric paths: states 2-3-4 for 'a', states 5-6-7 for 'b'
transition_function = {
# ── State 1_START: read and erase the leftmost character ──────────
# δ(1_START, a) = (2, △, R) — erase 'a', enter a-path
('1_START', 'a'): ('2', '△', 'R'),
# δ(1_START, b) = (5, △, R) — erase 'b', enter b-path
('1_START', 'b'): ('5', '△', 'R'),
# δ(1_START, △) = (8_HALT, △, R) — tape is blank (all chars matched): accept
('1_START', '△'): ('8_HALT', '△', 'R'),
# ── States 2 and 5: scan right to reach the right end ─────────────
# Both states skip all remaining characters and stop at the first blank.
# a-path: state 2 scans right over the entire remaining string
('2', 'a'): ('2', 'a', 'R'), # δ(2, a) = (2, a, R) — skip 'a'
('2', 'b'): ('2', 'b', 'R'), # δ(2, b) = (2, b, R) — skip 'b'
('2', '△'): ('3', '△', 'L'), # δ(2, △) = (3, △, L) — end reached; back up
# b-path: state 5 scans right identically
('5', 'a'): ('5', 'a', 'R'), # δ(5, a) = (5, a, R) — skip 'a'
('5', 'b'): ('5', 'b', 'R'), # δ(5, b) = (5, b, R) — skip 'b'
('5', '△'): ('6', '△', 'L'), # δ(5, △) = (6, △, L) — end reached; back up
# ── States 3 and 6: check and erase the rightmost character ───────
# a-path: state 3 expects to find 'a' at the right end (matching the
# 'a' erased at the left). Any other character means mismatch → reject.
('3', 'a'): ('4', '△', 'L'), # δ(3, a) = (4, △, L) — match! erase and return
# δ(3, △) = (8_HALT, △, R) — right end is blank: only one 'a' was left (odd
# length palindrome with 'a' in the middle) → accept
('3', '△'): ('8_HALT', '△', 'R'),
# Note: no transition for ('3', 'b') — if rightmost char is 'b', machine
# rejects implicitly (no valid transition defined).
# b-path: state 6 expects to find 'b' at the right end
('6', 'b'): ('7', '△', 'L'), # δ(6, b) = (7, △, L) — match! erase and return
# δ(6, △) = (8_HALT, △, R) — only one 'b' was left (middle of odd palindrome)
('6', '△'): ('8_HALT', '△', 'R'),
# Note: no transition for ('6', 'a') — mismatch → implicit rejection.
# ── States 4 and 7: scan left back to the left boundary ───────────
# After erasing the matched rightmost character, return to START.
# a-path: state 4 scans left over all remaining characters
('4', 'a'): ('4', 'a', 'L'), # δ(4, a) = (4, a, L) — skip 'a'
('4', 'b'): ('4', 'b', 'L'), # δ(4, b) = (4, b, L) — skip 'b'
('4', '△'): ('1_START', '△', 'R'), # δ(4, △) = (1_START, △, R) — hit left blank
# b-path: state 7 scans left identically
('7', 'a'): ('7', 'a', 'L'), # δ(7, a) = (7, a, L) — skip 'a'
('7', 'b'): ('7', 'b', 'L'), # δ(7, b) = (7, b, L) — skip 'b'
('7', '△'): ('1_START', '△', 'R'), # δ(7, △) = (1_START, △, R) — hit left blank
}
return TuringMachine(states, input_symbols, tape_symbols,
transition_function, blank_symbol)
def test_palindrome_tm():
palindrome_tm = create_palindrome_tm()
# Palindromes: "", "a", "b", "aa", "bb", "aba", "bab", "abba", "baab"
# Non-palindromes: "abb", "bba", "abab"
test_strings = ["", "a", "b", "aa", "bb", "aba", "bab",
"abba", "baab", "abb", "bba", "abab"]
print("Testing Palindrome Turing Machine:")
print("----------------------------------")
for test_str in test_strings:
try:
palindrome_tm.set_input(test_str)
result = palindrome_tm.run(1000)
print(f"Input: '{test_str}'")
print(f"Result: {result} | Final state: {palindrome_tm.current_state}"
f" | Final tape: '{palindrome_tm.get_tape_contents()}'")
print("----------------------------------")
except Exception as e:
print(f"Input: '{test_str}', Error: {e}")
print("----------------------------------")
# ── PALINDROME-SPECIFIC TuringMachine CLASS ───────────────────────────────────
# ⚠️ This class overwrites the general-purpose TuringMachine from Code Cell 1.
# Differences from Cell 1's class:
# - __init__ hardcodes current_state = '1_START' (not 'START')
# - step() and run() check '8_HALT' in self.current_state (substring match)
# rather than self.current_state in self.halt_states (set membership)
# - No input-symbol or blank-symbol validation in __init__
# - get_tape_contents() filters ALL blank symbols including mid-tape blanks
class TuringMachine:
"""
Palindrome-specific Turing Machine variant.
Differences from the general class (Code Cell 1):
- Initial state: '1_START' (hardcoded)
- HALT detection: '8_HALT' in current_state (substring, not set membership)
- No input/blank validation in __init__
See Code Cell 1 for the general-purpose version.
"""
def __init__(self, states, input_symbols, tape_symbols,
transition_function, blank_symbol):
self.states = states
self.input_symbols = input_symbols
self.tape_symbols = tape_symbols
self.transition_function = transition_function
self.blank_symbol = blank_symbol
# ⚠️ Hardcoded start state — does not use 'START' convention from Cell 1
self.tape = [None]
self.head_position = 1
self.current_state = '1_START'
def set_input(self, input_string):
for symbol in input_string:
if symbol not in self.input_symbols:
raise ValueError(f"Invalid input symbol: {symbol}")
self.tape = [None] + list(input_string)
self.head_position = 1
self.current_state = '1_START' # reset to palindrome start state
def get_current_symbol(self):
if self.head_position >= len(self.tape):
return self.blank_symbol
return self.tape[self.head_position]
def write_symbol(self, symbol):
while self.head_position >= len(self.tape):
self.tape.append(self.blank_symbol)
self.tape[self.head_position] = symbol
def step(self):
# ⚠️ HALT detection: substring check on '8_HALT', not set membership
if '8_HALT' in self.current_state:
return False
current_symbol = self.get_current_symbol()
key = (self.current_state, current_symbol)
if key not in self.transition_function:
return False # no transition → implicit rejection
next_state, new_symbol, direction = self.transition_function[key]
self.current_state = next_state
self.write_symbol(new_symbol)
if direction == 'L':
self.head_position = max(1, self.head_position - 1)
elif direction == 'R':
self.head_position += 1
return True
def run(self, max_steps=1000):
steps = 0
while steps < max_steps:
if '8_HALT' in self.current_state: # ⚠️ substring check
return 'accepted'
if not self.step():
return 'rejected'
steps += 1
return 'timeout'
def get_tape_contents(self):
if len(self.tape) <= 1:
return ""
content = list(self.tape[1:])
# Remove trailing blanks
while content and content[-1] == self.blank_symbol:
content.pop()
# ⚠️ Also filters all blank symbols mid-tape (erased characters show as absent)
return ''.join(str(s) for s in content if s != self.blank_symbol)
def print_configuration(self):
tape_str = ' '.join(str(s) if s is not None and s != self.blank_symbol
else '△' for s in self.tape[1:])
head_indicator = ' ' * (2 * (self.head_position - 1)) + '^'
print(f"State: {self.current_state}")
print(f"Tape: {tape_str}")
print(f"Head: {head_indicator}")
# Run the tests when this file is executed directly
if __name__ == "__main__":
test_palindrome_tm()
Testing Palindrome Turing Machine:
----------------------------------
Input: ''
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'a'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'b'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'aa'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'bb'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'aba'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'bab'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'abba'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'baab'
Result: accepted | Final state: 8_HALT | Final tape: ''
----------------------------------
Input: 'abb'
Result: rejected | Final state: 3 | Final tape: 'bb'
----------------------------------
Input: 'bba'
Result: rejected | Final state: 6 | Final tape: 'ba'
----------------------------------
Input: 'abab'
Result: rejected | Final state: 3 | Final tape: 'bab'
----------------------------------
3. Processing Input with Turing Machines#
A Turing machine processes input quite differently from a finite automaton or a Pushdown automaton, despite their similarities. This section explains the operation of a Turing machine when processing input and details how the transition function drives this process.
3.1 One-Way vs. Two-Way Infinite Tapes#
It’s worth noting that in Alan Turing’s original 1936 paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” the Turing machine was defined with a tape that stretched infinitely in both directions. In contrast, the model used in this textbook simplifies things by using a tape that’s only infinite to the right. This change introduces a boundary at the first cell, something we’ll discuss below. Even though the tape setup is different, it turns out this doesn’t change what the machine can actually do. Turing machines with one-way infinite tapes are just as powerful as those with two-way infinite tapes. Anything one can compute, the other can too. You just need a bit of extra bookkeeping to manage the boundary on the left side. This equivalence is important because it shows that the fundamental power of Turing machines doesn’t depend on the direction the tape goes. The core idea of what it means for something to be “computable” stays the same.
3.2 How a Turing Machine Processes Input#
Let’s start by understanding what happens when a Turing machine runs on an input string:
Initial Configuration:
The input string is placed on the tape, one symbol per cell, starting at position 1
All other cells are filled with the blank symbol (\(\triangle\))
The tape head starts at position 1 (the leftmost cell of the input)
The machine begins in the START state
Execution Process:
In each step, the machine reads the symbol under the tape head
Based on the current state and the read symbol, the machine:
Transitions to a new state or remains in the current state
Writes a symbol on the current cell (possibly the same symbol)
Moves the tape head one position left or right
This process continues until the machine reaches a HALT state or has no valid transition
Acceptance:
If the machine reaches a HALT state, the input is accepted
If the machine gets stuck (no valid transition exists for the current state and symbol), the input is rejected
If the machine runs forever without halting, the input is neither accepted nor rejected
Important Boundary Condition:
If the TAPE HEAD attempts to move LEFT from cell 1, the machine crashes and immediately rejects the input
This occurs regardless of the state the machine transitions to, even if it’s a HALT state.
This boundary condition exists because the tape is only infinite to the right, not to the left
In our implementation, we’ve enforced this by ensuring the head position never goes below 1
3.3 The Transition Function in Detail#
The transition function \(\delta\) is the heart of a Turing machine. It dictates the machine’s behavior for every possible situation it might encounter. Formally, the transition function maps: \(\delta(Q × \Gamma) = Q × \Gamma × \{L, R\}\) where:
\(Q\) is the set of states
\(\Gamma\) is the set of tape symbols
\(L\) and \(R\) represent left and right movements of the TAPE HEAD
The \(×\) symbol indicates a Cartesian product, \(Q × \Gamma\) meaning the function takes as input a pair consisting of a state and a tape symbol
For each combination of a state \(q_1 \in Q\) and a tape symbol \(a_1 \in \Gamma\), the transition function specifies:
The next state \(q_2 \in Q\)
The symbol \(a_2 \in \Gamma\) to write on the current cell
The direction \(d \in \{L, R\}\) to move the TAPE HEAD
For example, the transition function \(\delta(START, a) = (HALT, b, R)\) means that when the machine is in the START state and reads the symbol \(a\), it transitions to the HALT state, writes \(b\) on the tape, and moves the TAPE HEAD one cell to the right.
In our Python implementation, this is represented as a dictionary where:
The key is a tuple (current_state, current_symbol)
The value is a tuple (next_state, symbol_to_write, direction_to_move)
4. Turing Machines for Regular Languages#
Regular languages are a subset of formal languages that can be recognized by finite automata (FA). Regular languages form a subset of formal languages that can be recognized by finite automata (FA). In the following subsection, we demonstrate that any regular language can also be recognized by a Turing machine (TM). This is achieved by systematically converting a finite automaton into an equivalent Turing machine. This conversion highlights that Turing machines are more powerful than finite automata when it comes to defining or recognizing formal languages.
The process of converting a finite automaton to a Turing machine is straightforward:
Start with an FA that accepts the regular language \(L\)
Transform edge labels: Change each transition label \(a\) to \((a, a, R)\), meaning “read ‘a’, write ‘a’, move right”
Rename the start state: Change the initial state (typically labeled with a “-” symbol in a FA) to “START”
Handle acceptance: Remove the accepting state markers (typically “+” symbols in a FA), and instead add transitions from each accepting state to a new “HALT” state with edge labels \((\triangle, \triangle, R)\), where \(\triangle\) represents the blank symbol.
This conversion works because the Turing machine simulates the FA by:
Reading the input string and moving right, just like an FA would
Following the exact same state transitions as the FA
When reaching the end of the input (indicated by a blank symbol):
If the current state corresponds to an accepting state in the FA, the TM will transition to HALT and accept the input;
If the current state is not an accepting state in the FA, the TM will have no valid transition for the blank symbol and will reject the input.
The resulting TM accepts exactly the same strings as the original FA.
4.1 Example of Converting a FA to a TM#
Consider the following FA, which accepts all strings containing a double occurrence of the letter \(a\) (i.e., the substring \(aa\)).
flowchart LR
accTitle: Example of Converting a FA to a TM
accDescr: a diagram representing Converting a FA to a TM
q0((q0-))
q1((q1))
q2((q2+))
%% Self loop on q0
q0 -->|b| q0
%% Transitions between q0 and q1
q0 -->|a| q1
q1 -->|b| q0
%% Transition from q1 to q2
q1 -->|a| q2
%% Self loop on q2
q2 -->|a,b| q2
%% Style to match the image
%% Position q0 on the left
%% Position q1 in the middle
%% Position q2 on the right
classDef default fill:#fff,stroke:#333,stroke-width:1px
classDef start fill:#fff,stroke:#333,stroke-width:1px
classDef accept fill:#fff,stroke:#333,stroke-width:3px
class q0 start
class q2 accept
It can be converted into an equivalent Turing Machine, as illustrated below:
flowchart LR
accTitle: Example of Converting a FA to a TM
accDescr: a diagram representing a TM converted from a FA
start((1 START))
state2((2))
halt[HALT 3]
%% Self loop on start state
start -->|"(b, b, R)"| start
%% Transition from start to state2
start -->|"(a, a, R)"| state2
%% Transition from state2 to halt
state2 -->|"(a, a, R)"| halt
%% Transition from state2 back to start
state2 -->|"(b, b, R)"| start
%% Style to match the image
classDef default fill:#fff,stroke:#333,stroke-width:1px
classDef halt fill:#fff,stroke:#333,stroke-width:1px,rx:15,ry:15
class halt halt
Note that the HALT state of the Turing Machine does not require looping transitions, as reaching this state signifies that the machine stops processing further input and accepts the string. This conversion technique demonstrates a fundamental relationship between finite automata and Turing machines: Turing machines are strictly more powerful than finite automata, capable of recognizing all regular languages plus many more complex languages that finite automata cannot handle.
5. Three Classes of Input Strings to Turing Machines#
5.1 Definition#
When a Turing machine processes an input string, exactly one of three outcomes must occur:
The machine accepts the input
The machine rejects the input
The machine loops infinitely
These three outcomes define three mutually exclusive and exhaustive classes for all possible input strings to any Turing machine. For any Turing machine \(T\) and input string \(s\), we can classify \(s\) into exactly one of three classes:
Accept class: The set of strings that \(T\) accepts, denoted as \(ACCEPT(T)\)
Reject class: The set of strings that \(T\) explicitly rejects after a finite number of steps, denoted as \(REJECT(T)\)
Loop class: The set of strings on which \(T\) runs forever without halting, denoted as \(LOOP(T)\)
5.2 Examples#
5.2.1 Example 1. Turning Machine that Accepts all strings with \(aa\)#
In the previous section, we discussed how to convert a finite automaton (FA) into a Turing machine (TM), using the language of all strings containing the substring \(aa\) as an example. Now, let’s modify that TM by adding a new loop transition \(\delta(START, △) = (START, △, R)\) to the START state. The updated machine is visualized as follows.
flowchart LR
accTitle: A modified TM
accDescr: a diagram representing a Modified TM by adding a new loop transition
start((1 START))
state2((2))
halt[HALT 3]
%% Self loop on start state
start -->|"(b, b, R)"| start
start -->|"(△, △, R)"| start
%% Transition from start to state2
start -->|"(a, a, R)"| state2
%% Transition from state2 to halt
state2 -->|"(a, a, R)"| halt
%% Transition from state2 back to start
state2 -->|"(b, b, R)"| start
%% Style to match the image
classDef default fill:#fff,stroke:#333,stroke-width:1px
classDef halt fill:#fff,stroke:#333,stroke-width:1px,rx:15,ry:15
class halt halt
This modified TM still accepts the same language. However, there is an important behavioral difference: In the original machine, if the input ended while the TM was in the START state (i.e., it encountered a blank symbol), there was no defined transition, causing the machine to implicitly reject the input by halting without accepting. In the modified version, the new loop transition allows the machine to stay in the START state, write a blank symbol, and move right upon reading a blank. This prevents an immediate rejection and subtly changes how the machine handles end-of-input situations. However, this change also introduces the possibility of infinite looping: if the machine reaches the end of the input in the START state (meaning it has not seen “aa” in the input), it will continue moving right forever, never halting. Thus, some input strings that would have been rejected before will now cause the machine to loop indefinitely instead of halting with a rejection.
The following table categorizes all possible inputs to this Turing machine:
Input Class |
Input Type |
Behavior |
|---|---|---|
Accept Class |
Strings containing “aa” |
The machine finds the pattern “aa”, transitions to state q2, and eventually reaches the HALT state. These strings are accepted in a finite number of steps. Examples: “aa”, “aab”, “baa”, “aaaa”. |
Reject Class |
Strings that end with “a” but don’t contain “aa” |
When processing strings ending with “a” (but not containing “aa”), the machine will be in state q2 when it reads the final symbol “a”. Since q2 does not have a transition on blank sybmol, the machine will crash and implicitly rejects the input. Examples: “a”, “ba”, “baba”. |
Loop Class |
Strings not containing “aa” and not ending with “a” |
The machine never encounters the pattern “aa” and isn’t in state q2 when it reaches the end. When it reaches the end of input (blank symbol) in the START state, it continues moving right indefinitely due to the \(\delta(START, △) = (START, △, R)\) transition. The machine never halts. Examples: “” (empty string), “b”, “bb”, “babab”. |
5.2.2 Example 2#
The following Turing machine recognizes strings over the alphabet \(\{a, b, c\}\) that contain an even number of ‘a’s (including zero ‘a’s) and no ‘c’. The machine works by keeping track of parity: whether it has seen an even or odd number of ‘a’s so far. The START state of the machine is also called q_even, reflecting that we begin having seen 0 ‘a’s (which is an even number).
stateDiagram-v2
accTitle: A TM Accepting Strings containing an even number of 'a's and no 'c'
accDescr: a diagram representing a TM that accepts Strings containing an even number of 'a's and no 'c'
direction LR
START(q_even)
START(q_even) --> q_odd: (a, a, R)
START(q_even) --> START(q_even): (b, b, R)
START(q_even) --> HALT: (△, △, R)
START(q_even) --> q_loop: (c, c, R)
q_odd --> START(q_even): (a, a, R)
q_odd --> q_odd: (b, b, R)
q_odd --> q_loop: (c, c, R)
q_loop --> q_loop: (a, a, R)
q_loop --> q_loop: (b, b, R)
q_loop --> q_loop: (c, c, L)
q_loop --> q_loop: (△, △, L)
How does this machine work:
The machine starts in START(or q_even), indicating we’ve seen 0 ‘a’s so far (which is even)
For inputs without ‘c’:
For each ‘a’ encountered, it toggles between q_even and q_odd states
Each ‘b’ is simply skipped (doesn’t affect the parity count)
When it reaches the end of the input (blank symbol):
If in state q_even, it transitions to HALT (even number of ‘a’s)
If in state q_odd, there is no defined transition, so the machine implicitly crashes and rejects the input
For inputs containing ‘c’:
When the machine encounters ‘c’, it transitions to the q_loop state
In q_loop state, on inputs ‘a’ or ‘b’, it keeps moving right
In q_loop state, on input ‘c’ or blank, it moves left. This creates a “back-and-forth” pattern that never terminates
The following table categorizes all possible inputs to this Turing machine:
Input Class |
Input Type |
Behavior |
|---|---|---|
Accept Class |
Strings with an even number of ‘a’s and no ‘c’s: |
1. Machine processes the input from left to right |
Reject Class |
Strings with an odd number of ‘a’s and no ‘c’s: |
1. Machine processes the input from left to right |
Loop Class |
Strings containing at least one ‘c’: |
1. Machine processes input until it encounters ‘c’ |
5.3 Why the LOOP Class is Essential in Turing Machine Theory#
The LOOP class is a crucial concept in the theory of computation for several important reasons:
Completeness of Classification: The LOOP class completes the classification system for Turing machines. Without this class, we would have no way to categorize inputs that cause a machine to run forever. Every input to a Turing machine must either be accepted, rejected, or cause the machine to loop indefinitely - these three classes together form a complete partitioning of all possible inputs.
Undecidability and the Halting Problem: The existence of the LOOP class is directly connected to one of the most fundamental results in computer science: the Halting Problem. The Halting Problem shows that it is impossible to create an algorithm that can determine, for every possible program and input, whether that program will eventually halt or run forever. The LOOP class represents precisely those inputs for which a machine will never halt.
Differentiating Between Types of Languages: The LOOP class helps us distinguish between different types of languages:
Decidable languages: A language is decidable if there exists a Turing machine that
accepts all strings in the language,
rejects all strings not in the language, and
has an empty LOOP class. These are the most well-behaved languages.
Recognizable languages: A language is recognizable (but not decidable) if there exists a Turing machine that
accepts all strings in the language,
reject or loop forever for strings not in the language.
in this case, the LOOP class is non-empty.
Theoretical Limitations of Computing: The LOOP class represents a fundamental limitation of computation. It shows that there are problems for which an algorithm can be specified, but it will never terminate for certain inputs. This has profound implications:
Not all well-defined problems are effectively computable
Some computational processes cannot be predicted without actually running them
There are inherent limits to what can be calculated algorithmically
5.4 Practical Implications:#
In our example Turing machine that recognizes strings containing “aa” but loops on strings without “aa”, we saw how a small modification (adding a loop transition on blank symbols) dramatically changed the behavior. This illustrates an important practical concern in computing:
Programs can contain infinite loops that might be difficult to detect
Determining whether a program will terminate for all inputs is generally impossible
Software verification and testing must contend with the possibility of non-termination
The LOOP class isn’t merely a theoretical curiosity: it represents a fundamental aspect of computation that affects both the theoretical foundations of computer science and practical aspects of software development.
6. Practice Exercises#
6.1 Turing Machine State Diagram#
Draw a state diagram for a Turing machine that accepts strings over \(\{a, b\}\) that:
End with the letter ‘a’
Contain exactly one ‘b’
Have an odd number of ‘b’s
6.2 Machine Execution Tracing#
For the Turing machine that accepts strings with an even number of ‘a’s and no ‘c’, trace through the execution steps for the following inputs:
“aba”
“baa”
“abba”
Show the state, tape contents, and head position at each step.
6.3 Input Classification#
For the following Turing machine transition function, classify each of the given strings as Accept, Reject, or Loop:
states = {q0, q1, qaccept}
input_symbols = {0, 1}
tape_symbols = {0, 1, _}
initial_state = q0
accept_states = {qaccept}
Transitions:
(q0, 0) -> (q0, 0, R)
(q0, 1) -> (q1, 1, R)
(q0, _) -> (qaccept, _, R)
(q1, 0) -> (q1, 0, R)
(q1, 1) -> (q0, 1, R)
(q1, _) -> (q1, _, L)
Inputs:
“01”
“00”
“101”
“111”
“”
6.4 Converting FA to TM#
Convert the following finite automaton to a Turing machine:
States: {q0, q1, q2}
Input alphabet: {a, b}
Start state: q0
Accept states: {q2}
Transitions:
q0 on ‘a’ → q1
q0 on ‘b’ → q0
q1 on ‘a’ → q1
q1 on ‘b’ → q2
q2 on ‘a’ → q1
q2 on ‘b’ → q0
Show your transition function for the resulting Turing machine.
6.5 Modifying a TM#
Take the Turing machine that accepts strings with an even number of ‘a’s and no ‘c’, modify it by removing the transition between q_odd and q_loop, and analyze how this change affects the machine’s behavior with respect to the three classes of input: ACCEPT, REJECT, and LOOP.
6.6 Implement in Python#
Implement the following Turing machines in Python, using the TuringMachine class from the notebook:
A machine that increments a binary number (e.g., “1011” becomes “1100”)
A machine that recognizes palindromes over {0, 1}
A machine that accepts strings where the number of ‘a’s equals the number of ‘b’s
Test each implementation with appropriate inputs.
6.7 Binary String Doubler#
Design and implement a Turing machine that takes a binary string as input and produces a string that represents twice the binary number. For example:
Input: “101” (decimal 5) → Output: “1010” (decimal 10)
Input: “11” (decimal 3) → Output: “110” (decimal 6)
Input: “1” (decimal 1) → Output: “10” (decimal 2)
6.8 Balanced Parentheses Checker#
Create a Turing machine that accepts strings containing only ‘(’ and ‘)’ characters if and only if the parentheses are balanced. Examples:
“()” → Accept
“(())” → Accept
“(()” → Reject
“)(” → Reject
6.9 String Reverser#
Design a Turing machine that reverses a string over the alphabet {a, b}. The machine should transform the input string into its reverse.
Input: “aba” → Output: “aba”
Input: “abba” → Output: “abba”
Input: “ab” → Output: “ba”
6.10 Prime Number Checker (Unary)#
Create a Turing machine that accepts unary representations of prime numbers. In unary, a number n is represented by n consecutive ‘1’s. For example:
“11” represents 2 (prime) → Accept
“111” represents 3 (prime) → Accept
“1111” represents 4 (not prime) → Reject
“11111” represents 5 (prime) → Accept
7. Further Reading#
“Introduction to the Theory of Computation” by Michael Sipser, Section 3.1
“Introduction to Computer Theory” by Daniel I.A. Cohen, Chapter 19
“Automata Theory, Languages, and Computation” by Hopcroft, Motwani, and Ullman, Chapter 8