PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 9:
• Turing Machines
Reading:
Sipser Ch 3.1, 3.3
Mark Bun
February 22, 2021
Turing Machines – Motivation
We’ve seen finite automata as a restricted model of
computation
Finite Automata / Regular Expressions
• Can do simple pattern matching (e.g., substrings), check parity,
addition
• Can’t perform unbounded counting
• Can’t recognize palindromes
Somewhat more powerful (not in this course):
Pushdown Automata / Context-Free Grammars
• Can count and compare, parse math expressions
• Can’t recognize 𝑎𝑎𝑛𝑛𝑏𝑏𝑛𝑛𝑐𝑐𝑛𝑛 𝑛𝑛 ≥ 0}
2/22/2021 CS332 – Theory of Computation 2
Turing Machines – Motivation
Goal:
Define a model of computation that is
1) General purpose. Captures all algorithms that can be
implemented in any programming language.
2) Mathematically simple. We can hope to prove that
things are not computable in this model.
2/22/2021 CS332 – Theory of Computation 3
A Brief History
2/22/2021 CS332 – Theory of Computation 4
1900 – Hilbert’s Tenth Problem
2/22/2021 CS332 – Theory of Computation 5
David Hilbert 1862-1943
Given a Diophantine equation with any
number of unknown quantities and with
rational integral numerical coefficients: To
devise a process according to which it can
be determined in a finite number of
operations whether the equation is
solvable in rational integers.
1928 – The Entscheidungsproblem
2/22/2021 CS332 – Theory of Computation 6
David Hilbert 1862-1943
The “Decision Problem”
Is there an algorithm which
takes as input a formula (in
first-order logic) and
decides whether it’s
logically valid?
Wilhelm Ackermann 1896-1962
1936 – Solution to the Entscheidungsproblem
2/22/2021 CS332 – Theory of Computation 7
Alonzo Church 1903-1995
Alan Turing 1912-1954
“An unsolvable problem of elementary
number theory“
Model of computation: 𝜆𝜆-calculus (CS 320)
“On computable numbers, with an
application to the Entscheidungsproblem”
Model of computation: Turing Machine
Turing Machines
2/22/2021 CS332 – Theory of Computation 8
The Basic Turing Machine (TM)
2/22/2021 CS332 – Theory of Computation 9
Tape 𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑎𝑎
Finite
control
…
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts as soon as control reaches
“accept” or “reject” state
Input
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
𝑞𝑞accept
𝑞𝑞reject
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
Example
𝑞𝑞0 𝑞𝑞1
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
𝑞𝑞accept
𝑞𝑞reject
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
Example
𝑞𝑞0 𝑞𝑞1
Example
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
𝑞𝑞accept
𝑞𝑞reject
0 → 0,𝑅𝑅
⊔→ ⊔,𝑅𝑅
0 → 0,𝑅𝑅
⊔→ ⊔, 𝐿𝐿
𝑞𝑞0 𝑞𝑞1
𝑞𝑞3
What does this TM do on input 000?
a) Halt and accept
b) Halt and reject
c) Halt in state 𝑞𝑞3
d) Loop forever without halting
Three Levels of Abstraction
High-Level Description
An algorithm (like CS 330)
Implementation-Level Description
Describe (in English) the instructions for a TM
• How to move the head
• What to write on the tape
Low-Level Description
State diagram or formal specification
2/22/2021 CS332 – Theory of Computation 13
Example
Determine if a string 𝑤𝑤 ∈ 𝐴𝐴 = 02
𝑛𝑛
𝑛𝑛 ≥ 0}
High-Level Description
Repeat the following forever:
• If there is exactly one 0 in 𝑤𝑤, accept
• If there is an odd number of 0s in 𝑤𝑤 (> 1), reject
• Delete half of the 0s in 𝑤𝑤
2/22/2021 CS332 – Theory of Computation 14
Example
Determine if a string 𝑤𝑤 ∈ 𝐴𝐴 = 02
𝑛𝑛
𝑛𝑛 ≥ 0}
Implementation-Level Description
1. While moving the tape head left-to-right:
a) Cross off every other 0
b) If there is exactly one 0 when we reach the right end of the
tape, accept
c) If there is an odd number of 0s when we reach the right
end of the tape, reject
2. Return the head to the left end of the tape
3. Go back to step 1
2/22/2021 CS332 – Theory of Computation 15
Example
Determine if a string 𝑤𝑤 ∈ 𝐴𝐴 = 02
𝑛𝑛
𝑛𝑛 ≥ 0}
Low-Level Description
2/22/2021 CS332 – Theory of Computation 16
TMs vs. Finite Automata
2/22/2021 CS332 – Theory of Computation 17
Formal Definition of a TM
A TM is a 7-tuple 𝑀𝑀 = (𝑄𝑄, Σ, Γ, 𝛿𝛿, 𝑞𝑞0, 𝑞𝑞accept, 𝑞𝑞reject)
• 𝑄𝑄 is a finite set of states
• Σ is the input alphabet (does not include ⊔)
• Γ is the tape alphabet (contains ⊔ and Σ)
• 𝛿𝛿 is the transition function
…more on this later
• 𝑞𝑞0 ∈ 𝑄𝑄 is the start state
• 𝑞𝑞accept ∈ 𝑄𝑄 is the accept state
• 𝑞𝑞reject ∈ 𝑄𝑄 is the reject state (𝑞𝑞reject ≠ 𝑞𝑞accept)
2/22/2021 CS332 – Theory of Computation 18
TM Transition Function
𝛿𝛿 ∶ 𝑄𝑄 × Γ → 𝑄𝑄 × Γ × {𝐿𝐿,𝑅𝑅}
𝐿𝐿 means “move left” and 𝑅𝑅 means “move right”
𝛿𝛿 𝑝𝑝, 𝑎𝑎 = (𝑞𝑞, 𝑏𝑏,𝑅𝑅) means:
• Replace 𝑎𝑎 with 𝑏𝑏 in current cell
• Transition from state 𝑝𝑝 to state 𝑞𝑞
• Move tape head right
𝛿𝛿 𝑝𝑝, 𝑎𝑎 = (𝑞𝑞, 𝑏𝑏, 𝐿𝐿) means:
• Replace 𝑎𝑎 with 𝑏𝑏 in current cell
• Transition from state 𝑝𝑝 to state 𝑞𝑞
• Move tape head left UNLESS we are at left end of tape, in
which case don’t move
2/22/2021 CS332 – Theory of Computation 19
Configuration of a TM
A string with captures the state of a TM together with the
contents of the tape
2/22/2021 CS332 – Theory of Computation 20
1 0 1 0 1 1 1 ⊔
𝑞𝑞5
…
Configuration of a TM: Formally
A configuration is a string 𝑢𝑢𝑞𝑞𝑢𝑢 where 𝑞𝑞 ∈ 𝑄𝑄 and 𝑢𝑢, 𝑢𝑢 ∈ Γ∗
• Tape contents = 𝑢𝑢𝑢𝑢 (followed by blanks ⊔)
• Current state = 𝑞𝑞
• Tape head on first symbol of 𝑢𝑢
2/22/2021 CS332 – Theory of Computation 21
1 0 1 0 1 1 1 ⊔
𝑞𝑞5
…
Example: 101𝑞𝑞50111
How a TM Computes
Start configuration: 𝑞𝑞0𝑤𝑤
One step of computation:
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢𝑎𝑎𝑐𝑐 𝑞𝑞𝑞 𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐,𝑅𝑅)
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢 𝑞𝑞𝑞 𝑎𝑎𝑐𝑐𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐, 𝐿𝐿)
• If we are at the left end of the tape in configuration 𝑞𝑞 𝑏𝑏𝑢𝑢,
what configuration do we reach if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐, 𝐿𝐿)?
2/22/2021 CS332 – Theory of Computation 22
How a TM Computes
Start configuration: 𝑞𝑞0𝑤𝑤
One step of computation:
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢𝑎𝑎𝑐𝑐 𝑞𝑞𝑞 𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐,𝑅𝑅)
• 𝑢𝑢𝑎𝑎 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑢𝑢 𝑞𝑞𝑞 𝑎𝑎𝑐𝑐𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐, 𝐿𝐿)
• 𝑞𝑞 𝑏𝑏𝑢𝑢 yields 𝑞𝑞𝑞 𝑐𝑐𝑢𝑢 if 𝛿𝛿 𝑞𝑞, 𝑏𝑏 = (𝑞𝑞𝑞, 𝑐𝑐, 𝐿𝐿)
Accepting configuration: 𝑞𝑞 = 𝑞𝑞accept
Rejecting configuration: 𝑞𝑞 = 𝑞𝑞reject
2/22/2021 CS332 – Theory of Computation 23
How a TM Computes
𝑀𝑀 accepts input 𝑤𝑤 if there is a sequence of configurations
𝐶𝐶1, … ,𝐶𝐶𝑘𝑘 such that:
• 𝐶𝐶1 = 𝑞𝑞0𝑤𝑤
• 𝐶𝐶𝑖𝑖 yields 𝐶𝐶𝑖𝑖+1 for every 𝑖𝑖
• 𝐶𝐶𝑘𝑘 is an accepting configuration
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject OR
𝑀𝑀 runs forever
2/22/2021 CS332 – Theory of Computation 24
Recognizers vs. Deciders
𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts
𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject OR
𝑀𝑀 runs forever
𝐴𝐴 is (Turing-)decidable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀
which halts on every input
• 𝑤𝑤 ∈ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞accept
• 𝑤𝑤 ∉ 𝐴𝐴 ⟹ 𝑀𝑀 halts on 𝑤𝑤 in state 𝑞𝑞reject
2/22/2021 CS332 – Theory of Computation 25
Back to Hilbert’s Tenth Problem
Computational Problem: Given a Diophantine equation,
does it have a solution over the integers?
𝐿𝐿 =
• 𝐿𝐿 is Turing-recognizable
• 𝐿𝐿 is not decidable (1949-70)
2/22/2021 CS332 – Theory of Computation 26
BU CS 332 – Theory of Computation
Turing Machines – Motivation
Turing Machines – Motivation
A Brief History
1900 – Hilbert’s Tenth Problem
1928 – The Entscheidungsproblem
1936 – Solution to the Entscheidungsproblem
Turing Machines
The Basic Turing Machine (TM)
Slide Number 10
Slide Number 11
Slide Number 12
Three Levels of Abstraction
Example
Example
Example
TMs vs. Finite Automata
Formal Definition of a TM
TM Transition Function
Configuration of a TM
Configuration of a TM: Formally
How a TM Computes
How a TM Computes
How a TM Computes
Recognizers vs. Deciders
Back to Hilbert’s Tenth Problem