Prepared by group 3
Turing Youasf Rahil
Machine
Sohaib Ashraf
Ali Abdul Rehman
Shawaiz Shafeeq
History
• By the 1930s, machines were already capable
of performing physical tasks, such as turning
gears or doing basic calculations.
• These machines worked in a fixed mechanical
way and could not make logical decisions.
• Machines that performed calculations were
built for specific purposes, meaning each
machine could perform only one type of task.
Intro to Turing
machine
• In 1936, Alan Turing proposed the idea
of the Turing Machine.
• It is a theoretical model that defines
how logical operations can be
performed.
Basic idea of
• ATuring machine
Turing Machine works using three main
ideas:
• An infinite tape to store data, a head
that reads and writes symbols, and a set
of rules that guide each step.
• The Turing Machine was the first
computational model that allowed both
reading from and writing to memory
during computation.
Working of a
Turing Machine
• A Turing Machine works by following
simple rules.
• It reads one symbol at a time, decides
what action to take, writes a symbol if
needed, and then moves left or right
on the tape.
• By repeating these steps, it can solve
logical problems
Components of
Turing machine
• Infinite Tape
• Read/Write Head
• Finite States
• input Alphabet
• Tape Alphabet
Tape Component
• Infinite Memory : Extends infinitely in both
directions, providing unlimited storage space
• Divided into Cells : Each cell holds exactly
one symbol from the tape alphabet
• Symbol Storage : Initially contains input
string with blank symbols filling the rest
• Tape Alphabet (Γ) : Includes input symbols
plus special symbols like blank
Head Component
• Read Operation: Scans the symbol in the current
tape cell
• Write Operation: Can replace the current symbol
with any symbol from tape alphabet
• Movement: Moves one cell left (L) or one cell right
(R) after each operation
• Controlled by Transition Function: Actions
determined by current state and scanned symbol
States Component
• Finite Set of States (Q): A limited
number of states
Example: Q = { q₀, q₁, q_accept,
q_reject }
• Start State (q₀): The state where
computation begins
• Accept State (q_accept): If reached,
the input is accepted then Machine
stops
• Reject State (q_reject): If reached,
Input Alphabet
• Component
Finite Set (Σ) - Contains all symbols that
can appear in the input string
Input alphabet (Σ) is a proper subset of
tape alphabet (Γ)
• Excludes Blank Symbol - The blank
symbol (␣) is not part of the input alphabet
• Language-Specific - Different Turing
Machines can have different input alphabets
Tape Alphabet
• Component
Superset of Input Alphabet - Tape
alphabet (Γ) includes all input symbols
(Σ)
• Blank Symbol - Special symbol (␣)
representing empty tape cells
• Marker Symbols - Additional symbols
for marking processed cells during
computation
• Mathematical Relationship - Σ ⊂ Γ
(Input alphabet is a proper subset of
How a Turing Machine Works
Transition Rules & Step-by-
Step Execution
Transition Rules
Transition rule is an instruction that tells the Turing
Machine what
to write, where to move, and which state to go to, based on
the current
state and tape symbol.
• A Turing Machine works entirely on transition
rules
• Each rule tells the machine what action to take
• Rules depend on:
⚬ Current state
Structure of a Transition Rule
• Transition rules control the machine’s behavior
• A rule tells the machine:
⚬ What symbol to write
⚬ Where to move the head
⚬ Which state to go next
Formal Rule:
Meaning of a Rule
• q → Current state
• a → Symbol read
• p → Next state
• b → Symbol written
• D → Direction (Left or Right)
• Each rule gives one complete instruction.
Each Step Follows a Rule
• The machine reads one symbol at a time
• It selects only one matching rule
• That rule is executed completely
• No step is skipped or guessed
Step-by-Step Working
• Step 1: Machine starts in the initial state
• Step 2: Tape head reads the current symbol
• Step 3: Matching transition rule is selected
• Step 4: Symbol is written on the tape
• Step 5: Head moves left or right
• Step 6: Machine changes to next state
• Step 7: Process repeats for the next step
Example Rule:
• The machine is in state q₀
• It reads symbol 1 from the tape
• It replaces 1 with X
• Then the tape head moves one step to the right
• Finally, the machine changes its state to q₁
• This is one complete step of the Turing Machine.