Computational Complexity and Computability
Lecture 2 – Turing Machines
Koushik Pal
University of Toronto
January 13, 2021
Motivation
Goal
Define computation as abstractly and generally as possible Obtain a rigorous definition of algorithm
Obtain a rigorous definition of efficiency
Turing Machine
start
q q q
qreject
Control Unit
qaccept
Tape
⊔
a
b
e
t
⊔
… …
Read Write Head
Blank Symbol
Tape
⊔
a
b
e
t
⊔
… …
Read Write Head
The read write head at each time step does the following: 1. Reads a tape symbol
2. Writes a tape symbol
3. Moves Left or Right
Examples
Example1 Example2
Time 0
Time 0
⊔
a
b
e
t
⊔
⊔
a
b
e
t
⊔
… … … …
Time 1 Time 1
… … … …
⊔
a
d
e
t
⊔
⊔
c
b
e
t
⊔
1. Reads a
2. Writes c
3. Moves Right
1. Reads b
2. Writes d
3. Moves Left
Input String
Input String
… …
⊔
a
d
e
s
t
⊔
Head starts at the leftmost position of the input string Rest of the cells on the tape contain the blank symbol
Blank Symbol
States & Transitions
q a → b, R qj q a → b, L qj ii
1. Reads a
2. Writes b
3. Moves Right
4. Transitions from qi to qj
1. Reads a
2. Writes b
3. Moves Left
4. Transitions from qi to qj
Transitions & Configurations
Example1 Example2
Time 0
Time 5
⊔
a
b
e
t
⊔
⊔
a
b
e
t
⊔
… … … …
q q Time 1 Time 6
… … … …
⊔
a
b
et
⊔
⊔
c
b
e
t
⊔
q Transition
a → c, R
Configurations
Time 0 qabet Time 1 cqbet
Transition
q ⊔ → ⊔, L
q
q q q
Configurations
Time 5 abetq Time 6 abeqt
Halting and Acceptance
There are two special states — qaccept and qreject. These are final states, i.e., there are no transitions going out of them. A Turing machine halts if and only if it reaches a final state.
If the machine halts in qaccept, the machine accepts the input.
If the machine halts in qreject or the machine enters an infinite loop (aka, never reaches a final state), the machine rejects the input.
The set L(M) = {w | M accepts w} is called the language recognized by the Turing Machine M.
Turing Machine Example
Goal : Describe a TM on the alphabet {, } that recognizes the language +.
start
q
Σ = {,}
Γ = {,,⊔}
→ , R
→ , R q ⊔ → ⊔, L qaccept
qreject
→ , R ⊔ → ⊔, R
→ , R
Accept Example
Input : 00
Time 0 Time 1
… … … …
q q
q →,R q q →,R q
Time 2 Time 3
… … … …
⊔
⊔
⊔
⊔
⊔
⊔
⊔
⊔
q qaccept
q
⊔ → ⊔, L qaccept
Halt and accept!
Reject Example
Input : 001
Time 0 Time 1
… … … …
q q
q →,R q q →,R q
Time 2 Time 3
… … … …
⊔
⊔
⊔
⊔
⊔
⊔
⊔
⊔
q qreject
q
→ ,R qreject
Halt and reject!
Infinite Loop Example
→ , R → , L
Σ = {,},
Γ = {,,⊔}
start
Input : 01
q
⊔ → ⊔, R
qaccept
Time 0
Time 1
Time 2
⊔
⊔
⊔
⊔
… … … … …
⊔
⊔
…
q q q
q →,R q q →,L q
Infinite Loop!
Formal Definition
Definition (Turing Machine)
A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q, qaccept, qreject), where Q, Σ, Γ are all finite sets and
Q is the set of states,
Σ is the input alphabet not containing the blank symbol ⊔, Γ isthetapealphabet,where⊔∈Γ andΣ⊆Γ,
δ:Q×Γ→Q×Γ×{L,R}isthetransitionfunction,
q ∈ Q is the start state,
qaccept ∈ Q is the accept state, and
qreject ∈ Q is the reject state, where qreject ̸= qaccept.
TM vs FSA
The following are the primary differences between a Turing Machine and a Finite State Automaton:
TM can read as well as write symbols.
TM has an infinite tape.
Head can move left or right, thereby allowing a TM to have no limitation on access to input.
Special accept and reject states that stop computation immediately.
One more example – PAL
Goal : Describe a TM on the alphabet {, } for the languauge PAL = {set of even length palindromes} = {yyR | y ∈ {,}∗}.
One more example – PAL start q
⊔ → R qaccept
, → R q
q
, → R
q
q
q
, → L
→ ⊔, L
→ ⊔, R
⊔→R
⊔→L
⊔→L
→ ⊔, R
→ ⊔, L