CS代考计算机代写 Finite State Automaton algorithm Computational Complexity and Computability

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 qabet Time 1 cqbet
Transition
q ⊔ → ⊔, L
q
q q q
Configurations
Time 5 abetq Time 6 abeqt

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