CS21 Decidability and Tractability
Lecture 10 January 26, 2024
Turing Machine diagrams
start state qreject
Copyright By PowCoder代写 加微信 powcoder
b → R transition label: (tape symbol read →
(1 accept + 1 reject)
tape symbol written, direction moved)
– a → R means “read a, move right”
– a → L means “read a, move left”
– a → b, R means “read a, write b, move right
January 26, 2024 CS21 Lecture 10 2
“_” means blank tape square
Example TM diagram
0,1→R 0,1→R 0,1,#→L 0,1→R x→R
#→R _→L _→R #→R
q1 q3 q5 q7 q9
0 → x, R 0 → x, L
x → R x → R
q11 _→R q12 #→R q13 _→R qaccept
0,1,x,# → L
#→R 1 → _,R
q2 q4 q6 q8 q10 #→R _→L _→R #→R
0,1→R 0,1→R 0,1,#→L 0,1→R x→R
January 26, 2024 CS21 Lecture 10 3
TM formal definition
• A TM is a 7-tuple
(Q, Σ, Γ, δ, q0, qaccept, qreject) where:
– Q is a finite set called the states
– Σ is a finite set called the input alphabet
– Γ is a finite set called the tape alphabet
– δ:Q x Γ→ Q x Γ x {L, R} is a function called the
transition function
– q0 is an element of Q called the start state
– qaccept, qreject are the accept and reject states
January 26, 2024 CS21 Lecture 10 4
#01 #01 #01 #01 #01 #00 #1 0
January 26, 2024
start start start start t
CS21 Lecture 10
program for “binary successor”
Example TM operation
start start start start t
0 1 _ # 0 1 #
(start, 0, R) (start, 1, R) (t, _, L) (start, #, R) (accept, 1, -) (t, 0, L) (accept, #, R)
TM configurations
• At every step in a computatio• nta,peacTonMtenists:inuv
a configuration determined by:
• in state q
– the contents of the tape • reading first
– the state
– the location of the read/write head
• next step completely determined by current configuration
• shorthand: string uqv with u,v ∈ Γ*, q ∈ Q January 26, 2024 CS21 Lecture 10 6
followed by blanks
symbol of v
TM configurations
• configuration C1 yields configuration C2 if TM can legally* move from C1 to C2 in 1 step
–notation:C1 ⇒C2
– also: “yields in 1 step” notation: C1 ⇒1 C2 – “yields in k steps” notation: C1 ⇒k C2
if there exists configurations D1,D2,…Dk-1 for
which C1 ⇒D1 ⇒D2 ⇒…⇒Dk-1 ⇒C2
– also: “yields in some # of steps” (C1 ⇒* C2)
*Convention: TM halts upon entering qaccept, qreject January 26, 2024 CS21 Lecture 10 7
TM configurations
• Formal definition of “yields”:
uaqibv ⇒uqjacv if δ(qi, b) = (qj, c, L), and
uaqibv ⇒uacqjv if δ(qi, b) = (qj, c, R)
(qi ≠ qaccept, qreject) –leftend:qibv ⇒qjcvifδ(qi,b)=(qj,c,L)
• two special cases:
– right end: uaqi same as uaqi_
January 26, 2024 CS21 Lecture 10 8
u,v ∈ Γ* a,b,c ∈ Γ qi,qj ∈Q
TM acceptance
• start configuration: q0w (w is input)
• accepting config.: any config.with state qaccept • rejectingconfig.:anyconfig.withstateqreject
TM M accepts input w if there exist configurations C1, C2, …, Ck
– C1 is start configuration of M on input w –Ci ⇒Ci+1 fori=1,2,3,…,k-1
–Ck isanacceptingconfiguration
January 26, 2024 CS21 Lecture 10 9
Deciding and Recognizing
• accept input machine • reject
• TM M: • loop forever
– L(M) is the language it recognizes
– if M rejects every x ∉ L(M) it decides L
– set of languages recognized by some TM is
called Turing-recognizable or recursively enumerable (RE)
– set of languages decided by some TM is called Turing-decidable or decidable or recursive
January 26, 2024 CS21 Lecture 10 10
Deciding and Recognizing
• accept input machine • reject
• TM M: • loop forever
– L(M) is the language it recognizes
– if M rejects every x ∉ L(M) it decides L
– set of languages recognized by some TM is called Turing-recognizable or recursively enumerable (RE)
– set of languages decided by some TM is called Turing-decidable or decidable or recursive
January 26, 2024 CS21 Lecture 10 11
Classes of languages
context free languages
all languages
regular languages
• Weknow:regular⊆CFL(propercontainment) • CFL⊆decidable
– decidable ⊆ RE ⊆ all languages
January 26, 2024 CS21 Lecture 10 12
Multitape TMs
• A useful variant: k-tape TM
input tape
011001110100 …
011001110100 … …
CS21 Lecture 10 13
finite control
011001 …
k read/write heads
k-1 “work tapes”
January 26, 2024
Multitape TMs
• Informal description of k-tape TM:
– input written on left-most squares of tape #1 – rest of squares are blank on all tapes
– at each point, take a step determined by
• current k symbols being read on k tapes • current state of finite control
– a step consists of
• writing k new symbols on k tapes
• moving each of k read/write heads left or right • changing state
January 26, 2024 CS21 Lecture 10 14
Multitape TM formal definition
• A TM is a 7-tuple
(Q, Σ, Γ, δ, q0, qaccept, qreject) where:
– everything is the same as a TM except the transition function:
δ:QxΓk →QxΓk x{L,R}k
δ(qi, a1,a2,…,ak) = (qj, b1,b2,…,bk, L, R,…, L) =
“in state qi, reading a1,a2,…,ak on k tapes,
move to state qj, write b1,b2,…,bk on k tapes, move L, R on k tapes as specified.”
January 26, 2024 CS21 Lecture 10 15
Multitape TMs
Theorem: every k-tape TM has an equivalent single-tape TM.
– Idea: simulate k-tape TM on a 1-tape TM.
January 26, 2024 CS21 Lecture 10 16
Multitape TMs simulation of k-tape TM by single-tape TM:
… • addnewsymbol x for each old x
• marks location of . . . “virtual heads”
(input tape)
#abab#aa#bbcd#… January 26, 2024 CS21 Lecture 10 17
abab a a bbcd
Multitape TMs
. . . Repeat:
• scan tape, remembering the symbols under each virtual head in the state (how many new states needed?)
•makechangestoreflect1stepofM
• if hit #, shift to right to make room if M halts, erase all but 1st string
#abab#aa#bbcd# …
January 26, 2024 CS21 Lecture 10 18
Nondeterministic TMs
• A important variant: nondeterministic TM • informally, several possible next
configurations at each step • formally, a NTM is a 7-tuple
(Q, Σ, Γ, δ, q0, qaccept, qreject) where:
– everything is the same as a TM except the transition function:
δ:Q x Γ → P(Q x Γ x {L, R})
January 26, 2024 CS21 Lecture 10 19
NTM acceptance
• start configuration: q0w (w is input)
• accepting config.: any config.with state qaccept • rejectingconfig.:anyconfig.withstateqreject
NTM M accepts input w if there exist configurations C1, C2, …, Ck
– C1 is start configuration of M on input w –Ci ⇒Ci+1 fori=1,2,3,…,k-1
–Ck isanacceptingconfiguration
January 26, 2024 CS21 Lecture 10 20
Nondeterministic TMs
Theorem: every NTM has an equivalent (deterministic) TM.
– Idea: simulate NTM with a deterministic TM
January 26, 2024 CS21 Lecture 10 21
Nondeterministic TMs Simulating NTM M with a deterministic TM:
January 26, 2024
• computations of M are a tree • nodes are configs
• fanout is b = maximum number of choices in transition function
• leaves are accept/reject configs.
CS21 Lecture 10 22
Nondeterministic TMs
Simulating NTM M with a deterministic TM:
• idea: breadth-first search of tree
• if M accepts: we will encounter accepting leaf and accept
• if M rejects: we will encounter all rejecting leaves, finish traversal of tree, and reject
• if M does not halt on some branch: we will not halt…
January 26, 2024 CS21 Lecture 10 23
Nondeterministic TMs
Simulating NTM M with a deterministic TM: – use a 3 tape TM:
• tape 1: input tape (read-only)
• tape 2: simulation tape (copy of M’s tape at point corresponding to some node in the tree)
• tape 3: which node of the tree we are exploring (string in {1,2,…b}*)
– Initially, tape 1 has input, others blank – STEP 1: copy tape 1 to tape 2
January 26, 2024 CS21 Lecture 10 24
Nondeterministic TMs Simulating NTM M with a deterministic TM:
– STEP 2: simulate M using string on tape 3 to determine which choice to take at each step
• if encounter blank, or a # larger than the number of choices available at this step, abort, go to STEP 3
• if get to a rejecting configuration: DONE = 0, go to STEP 3
• if get to an accepting configuration, ACCEPT
– STEP 3: replace tape 3 with lexicographically next
string and go to STEP 2
• if string lengthened and DONE = 1 REJECT; else DONE = 1
January 26, 2024 CS21 Lecture 10 25
Examples of basic operations
• Convince yourself that the following types of operations are easy to implement as part of TM “program”
(but perhaps tedious to write out…)
– incrementing/decrementing – arithmetic operations +, -, *, /
January 26, 2024 CS21 Lecture 10 26
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com