CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation
Lecture 11:
• TM Variants
Reading: Sipser Ch 3.2
• Closure Properties
Mark Bun March 1, 2020

The Basic Turing Machine (TM)
Tape 𝑎𝑏𝑎𝑎 Finite
…
Input
control
• Input is written on an infinitely long tape
• Head can both read and write, and move in both
directions
• Computation halts when control reaches
“accept” or “reject” state
3/3/2020 CS332 ‐ Theory of Computation 2

Example
𝑞0
⊔ → ⊔, 𝑅
accept
0 → 0,𝑅
⊔ → ⊔, 𝑅 𝑞1
0 → 0,𝑅 reject

Formal Definition of a TM
A TM is a 7‐tuple
􏵹 􏶧􏶨􏶨􏶩􏶍􏶪
􏶫􏶩􏶬􏶩􏶨􏶪
• • • •
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 is the start state
3/3/2020
CS332 ‐ Theory of Computation
4
is the accept state
is the reject state ( 􏶫􏶩􏶬􏶩􏶨􏶪 􏶧􏶨􏶨􏶩􏶍􏶪)

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
3/3/2020 CS332 ‐ Theory of Computation 5

Configuration of a TM
A string with captures the state of a TM together with the contents of the tape
3/3/2020 CS332 ‐ Theory of Computation
6
􏶎
…

Configuration of a TM: Formally
A configuration is a string where
• Tape contents = (followed by blanks • Current state =
• Tape head on first symbol of
and )
∗
3/3/2020 CS332 ‐ Theory of Computation
7
􏶎
…

How a TM Computes
Start configuration:
One step of computation:
• • •
yields
if
yields yields
if if
Accepting configuration: Rejecting configuration:
= =
􏶧􏶨􏶨􏶩􏶍􏶪 􏶫􏶩􏶬􏶩􏶨􏶪
􏵹
3/3/2020 CS332 ‐ Theory of Computation 8

How a TM Computes
• •
in state
􏶧􏶨􏶨􏶩􏶍􏶪 􏶫􏶩􏶬􏶩􏶨􏶪 OR
accepts input if there is a sequence of configurations 􏵶 􏶇 such that:
•􏵶=􏵹
• •
􏶞 yields 􏶞􏵵􏵶 for every
􏶇 is an accepting configuration
3/3/2020
CS332 ‐ Theory of Computation
9
the set of all strings which accepts
is Turing‐recognizable if halts on halts on
for some TM
:
in state runs forever

Recognizers vs. Deciders
• •
in state
􏶧􏶨􏶨􏶩􏶍􏶪 􏶫􏶩􏶬􏶩􏶨􏶪 OR
• •
halts on
in state in state
􏶧􏶨􏶨􏶩􏶍􏶪 􏶫􏶩􏶬􏶩􏶨􏶪
the set of all strings which accepts
is Turing‐recognizable if halts on halts on
for some TM :
is (Turing‐)decidable if halts on
for some TM
3/3/2020
CS332 ‐ Theory of Computation 10
in state runs forever
which halts on every input

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)
3/3/2020 CS332 ‐ Theory of Computation 11

TM Variants
3/3/2020 CS332 ‐ Theory of Computation 12

How Robust is the TM Model?
Does changing the model result in different languages being recognizable / decidable?
So far we’ve seen…
‐ We can require that FAs/PDAs have a single accept state
‐ (CFGs can always be put in Chomsky Normal Form)
‐ Adding nondeterminism does not change the languages recognized by finite automata
Turing machines have an astonishing level of robustness 3/3/2020 CS332 ‐ Theory of Computation 13

Extensions that do not increase the power of
the TM model
• TMs that are allowed to “stay put” instead of moving left or right
Proof that TMs with “stay put” are no more powerful: Simulation: Convert any TM with “stay put” into an
equivalent TM without
Replace every “stay put” instruction in with a move right instruction, followed by a move left instruction in
’
3/3/2020 CS332 ‐ Theory of Computation
14

Extensions that do not increase the power of
the TM model
• TMs with a 2‐way infinite tape, unbounded left to right Input
Tape …𝑎𝑏𝑎 …
Proof that TMs with 2‐way infinite tapes are no more
powerful:
Simulation: Convert any TM with 2‐way infinite tape into
a 1‐way infinite TM with a “two‐track tape”
3/3/2020 CS332 ‐ Theory of Computation 15

Formalizing the Simulation
􏶄􏶄􏶄􏶄􏶄􏶄􏶄
􏵹 􏶧􏶨􏶨􏶩􏶍􏶪 􏶫􏶩􏶬􏶩􏶨􏶪
New tape alphabet: New state set:
means “
, working on upper track” , working on lower track”
means “
New transitions:
􏶄 􏶄
􏵼 􏶒 𝑞,􏶣 , 𝑏,𝑎􏵵 ,𝑅􏶓 Also need new transitions for moving right, lower track, hitting $,
If𝛿 𝑝,𝑎􏶷 􏵼 􏶒𝑞,𝑏,𝐿􏶓,let𝛿′ 𝑝,􏶣 , 𝑎􏶷,𝑎􏵵
initializing input into 2‐track format
3/3/2020 CS332 ‐ Theory of Computation 16

TMs are equivalent to…
• TMs with “stay put”
• TMs with 2‐way infinite tapes
• Multi‐tape TMs
• Nondeterministic TMs
• Random access TMs
• Enumerators
• Finite automata with access to an unbounded queue = 2‐ stack PDAs
• Primitive recursive functions
• Cellular automata …
3/3/2020 CS332 ‐ Theory of Computation 17

Church‐Turing Thesis
The equivalence of these models is a mathematical theorem
Church‐Turing Thesis: Each of these models captures our intuitive notion of algorithms
The Church‐Turing Thesis is not a mathematical statement!
3/3/2020 CS332 ‐ Theory of Computation 18

Multi‐Tape TMs
Finite control
𝑏𝑏𝑎𝑎𝑎 𝑎𝑏⊔𝑎𝑎 ⊔𝑏𝑎𝑎𝑐
Fixed number of tapes (can’t change during computation)
Transition function
􏶇􏶇􏶇
3/3/2020 CS332 ‐ Theory of Computation 19

Multi‐Tape TMs are Equivalent to Single‐Tape TMs
Theorem: Every ‐tape TM with can be simulated by an equivalent single‐tape TM
Finite control
𝑏𝑏𝑎𝑎 𝑎𝑏⊔𝑎 ⊔𝑏𝑎𝑎
Finite control
𝑏𝑏𝑎𝑎#𝑎𝑏⊔𝑎#⊔𝑏𝑎𝑎𝑐# CS332 ‐ Theory of Computation 20
3/3/2020