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

BU CS 332 – Theory of Computation
Lecture 12:
• TM Variants
Reading:
Sipser Ch 3.2, 4.1
• Decidable Languages
Mark Bun March 4, 2020

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/4/2020
CS332 ‐ Theory of Computation 2
in state runs forever
which halts on every input

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

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

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

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
• “Turing‐complete” programming languages (C, Python, Java…)
…
3/4/2020 CS332 ‐ Theory of Computation 6

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

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

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 9
3/4/2020

Simulating Multiple Tapes
Implementation‐Level Description
On input
􏵶􏶊􏵳
1. Format tape into
2. For each move of :
􏵶􏶊􏵳
Scan left‐to‐right, storing current symbols in finite control Scan left‐to‐right, writing new symbols,
Scan left‐to‐right, moving each tape head
If a tape head goes off the right end, insert blank If a tape head goes off left end, move back right
3/4/2020 CS332 ‐ Theory of Computation 10

3/4/2020 CS332 ‐ Theory of Computation 11

Why are Multi‐Tape TMs Helpful?
To show a language is Turing‐recognizable or decidable, suffices to construct a multi‐tape TM
Very helpful for proving closure properties
Ex. Closure of recognizable languages under union. Suppose 𝑀􏵶 is a
single‐tape TM recognizing 𝐿􏵶, 𝑀􏶊 is a single‐tape TM recognizing 𝐿􏶊
3/4/2020 CS332 ‐ Theory of Computation 12

Nondeterministic TMs
At any point in computation, may nondeterministically branch. Accepts iff there exists an accepting branch.
Transition function
Ex. NTM for is a binary number representing the product of two positive integers
3/4/2020 CS332 ‐ Theory of Computation 13

Nondeterministic TMs
Theorem: Every nondeterministic TM has an equivalent deterministic TM
Proof idea:
Systematically try all 1‐step computations, all 2‐step computations, … and see if one of them accepts
3/4/2020 CS332 ‐ Theory of Computation 14

Nondeterministic TMs
Theorem: Every nondeterministic TM has an equivalent deterministic TM
Proof idea: Simulate an NTM 𝑤􏵶 𝑤􏶊 𝑤􏶋 𝑤􏶑
using a 3‐tape TM
Finite control
𝑤􏵶 ⊔
# 𝑤􏶋 3 7
𝑤􏶑
Input 𝑤 to 𝑁 (read‐only) Simulation tape (run 𝑁 on 𝑤 using
3/4/2020
CS332 ‐ Theory of Computation 15
1 3
nondeterministic choices from tape 3) Address in computation tree

3/4/2020 CS332 ‐ Theory of Computation 16

Enumerators
Finite control
Work tape “Printer”
• Starts with two blank tapes • Prints strings to printer
strings eventually printed by
• May never terminate (even if language is finite) • May print the same string many times
3/4/2020 CS332 ‐ Theory of Computation 17

Enumerable = Turing‐Recognizable
Theorem: A language is Turing‐recognizable some enumerator enumerates it
Start with an enumerator for and give a TM
3/4/2020 CS332 ‐ Theory of Computation
18

Enumerable = Turing‐Recognizable
Theorem: A language is Turing‐recognizable some enumerator enumerates it
Start with a TM for and give an enumerator
3/4/2020 CS332 ‐ Theory of Computation 19

Mid‐Semester Feedback Form
https://forms.gle/LTBEY1BoSZh8nupV6
3/4/2020 CS332 ‐ Theory of Computation 20