Formal Definition - Turing Machine
📘 Formal Definition - Turing Machine
A Turing Machine is a nine-tuple
where:
-
Q – a finite set of states
(typically denoted ...). -
Σ – the input alphabet,
which does not contain the blank symbol B or the left-end marker ⊢. -
Γ – the tape alphabet, satisfying
Every cell of the tape contains one symbol from Γ.
-
δ – the transition function
Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state.
-
s ∈ Q – the initial (start) state.
-
B ∈ Γ – the blank symbol, representing the empty tape cell.
-
⊢ ∈ Γ – the left-end marker, which appears at the extreme left of the tape and is never overwritten.
-
t ∈ Q – the accepting state.
-
r ∈ Q – the rejecting state, with
🧠 Informal Behavior
-
The tape is infinite to the right and begins with ⊢ on the leftmost cell.
-
The input string is written immediately to the right of ⊢.
-
All remaining cells are filled with blanks (B).
-
The head starts on the first input symbol (just right of ⊢) in the start state .
-
The machine repeatedly applies δ until it enters or , at which point it halts.
Transition function
is defined as follows.
For each pair where
and ,
where:
-
is the next state the machine enters,
-
is the symbol written in the current tape cell (possibly replacing ), and
-
indicates the direction of head movement
-
= move one cell to the left
-
= move one cell to the right
-
🧠 Intuitive Explanation
If the machine is in state and the tape head is scanning the symbol ,
then means:
-
Replace the symbol on the tape with ,
-
Move the head one cell in direction (either left or right),
-
Enter the new state .
⚠️ Special Conventions (Kozen’s Model)
-
The left-end marker (⊢) is never overwritten, i.e.,
if , then and .
This ensures the head never moves left of the tape’s beginning. -
The blank symbol (B) represents an empty cell, and blanks extend infinitely to the right.
-
The function δ is undefined for and r— because the machine halts when it reaches either of these states.
🧩 Example
Suppose
This means:
-
When in state scanning symbol
a
, -
write
X
on the tape, -
move the head one cell to the right,
-
and change to state
s₁
.
Similarly,
means:
-
When in state
s₁
scanningb
, -
write
Y
, move left, and go to states₂
Comments
Post a Comment