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

BU CS 332 – Theory of Computation

Lecture 12:

• TM Variants

• Decidable Languages

Mark Bun March 4, 2020

Reading:

Sipser Ch 3.2, 4.1

Recognizers vs. Deciders

𝐿𝐿(𝑀𝑀) = the set of all strings 𝑤𝑤 which 𝑀𝑀 accepts

𝐴𝐴 is Turing-recognizable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀:

•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞accept

•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞rejectOR 𝑀𝑀 runs forever

𝐴𝐴 is (Turing-)decidable if 𝐴𝐴 = 𝐿𝐿(𝑀𝑀) for some TM 𝑀𝑀

which halts on every input

•𝑤𝑤∈𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞 accept

•𝑤𝑤∉𝐴𝐴 ⟹ 𝑀𝑀haltson𝑤𝑤instate𝑞𝑞reject

3/4/2020 CS332 – Theory of Computation 2

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

𝑀𝑀′ = (𝑄𝑄′,Σ,Γ′,𝛿𝛿′,𝑞𝑞′,𝑞𝑞′ ,𝑞𝑞′ ) 0 accept reject

New tape alphabet: Γ′ = (Γ × Γ) ∪ {$} New state set: 𝑄𝑄′ = 𝑄𝑄 × {+,−}

(𝑞𝑞, −) means “𝑞𝑞, working on upper track”

(𝑞𝑞, +) means “𝑞𝑞, working on lower track” New transitions:

If𝛿𝛿 𝑝𝑝,𝑎𝑎 =(𝑞𝑞,𝑏𝑏,𝐿𝐿),let𝛿𝛿′ 𝑝𝑝,− , 𝑎𝑎 ,𝑎𝑎 =( 𝑞𝑞,− , 𝑏𝑏,𝑎𝑎 ,𝑅𝑅) −−++

Also need new transitions for moving right, lower track, hitting $, 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

𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑐𝑐

Fixed number of tapes 𝑘𝑘 (can’t change during computation) Transitionfunction𝛿𝛿∶𝑄𝑄×Γ𝑘𝑘 →𝑄𝑄×Γ𝑘𝑘 × 𝐿𝐿,𝑅𝑅,𝑆𝑆 𝑘𝑘

Finite control

3/4/2020 CS332 – Theory of Computation 8

Theorem: Every 𝑘𝑘-tape TM 𝑀𝑀 with can be simulated by an equivalent single-tape TM 𝑀𝑀′

𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎

𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎 𝑎𝑎𝑏𝑏⊔𝑎𝑎 ⊔𝑏𝑏𝑎𝑎𝑎𝑎𝑐𝑐#

Multi-Tape TMs are Equivalent to Single-Tape TMs

Finite control

Finite control

3/4/2020

CS332 – Theory of Computation 9

#

#

Simulating Multiple Tapes

Implementation-Level Description

Oninput𝑤𝑤=𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛 ̇ ̇

1. Formattapeinto#𝑤𝑤̇ 𝑤𝑤 …𝑤𝑤 #⊔#⊔#…# 2. Foreachmoveof𝑀𝑀:1 2 𝑛𝑛

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

1 single-tape TM recognizing 𝐿𝐿1, 𝑀𝑀2 is a single-tape TM recognizing 𝐿𝐿2

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.

Transitionfunction𝛿𝛿∶𝑄𝑄×Γ →𝑃𝑃(𝑄𝑄×Γ × 𝐿𝐿,𝑅𝑅,𝑆𝑆 ) 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

𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4

Input 𝑤𝑤 to 𝑁𝑁 (read-only) Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using

nondeterministic choices from tape 3) Address in computation tree

Finite control

𝑤𝑤1 ⊔

𝑤𝑤3 𝑤𝑤4

#

3/4/2020

CS332 – Theory of Computation 15

1

3

3

7

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

Decidable Languages

3/4/2020 CS332 – Theory of Computation 20

1928 – The Entscheidungsproblem The “Decision Problem”

Is there an algorithm which takes as input a formula (in first- order logic) and decides whether it’s logically valid?

3/4/2020 CS332 – Theory of Computation 21

Design a TM which takes as input a DFA 𝐷𝐷 and a string 𝑤𝑤, and determines whether 𝐷𝐷 accepts 𝑤𝑤

Let 𝐷𝐷 = (𝑄𝑄, Σ, 𝛿𝛿, 𝑞𝑞 , 𝐹𝐹). List each component of the tuple

Questions about regular languages

How should the input to this TM be represented?

separated by ;

0

• Represent 𝑄𝑄 by ,-separated binary strings

• Represent Σ by ,-separated binary strings

• Represent 𝛿𝛿 ∶ 𝑄𝑄 × Σ → 𝑄𝑄 by a ,-separated list of triples (𝑝𝑝, 𝑎𝑎, 𝑞𝑞), …

Denotetheencodingof𝐷𝐷,𝑤𝑤by 𝐷𝐷,𝑤𝑤

3/4/2020 CS332 – Theory of Computation 22

Representation independence

Computability (i.e., decidability and recognizability) is not affected by the choice of encoding

Why? A TM can always convert between different encodings

For now, we can take to mean “any reasonable encoding”

3/4/2020 CS332 – Theory of Computation 23

A “universal” algorithm for recognizing regular

𝐴𝐴 = 𝐷𝐷,𝑤𝑤 DFA𝐷𝐷accepts𝑤𝑤} DFA

languages

Theorem: 𝐴𝐴DFA is decidable

Proofsketch:DefineaTM𝑀𝑀whichoninput 𝐷𝐷,𝑤𝑤: 1. Check if 𝐷𝐷, 𝑤𝑤 is a valid encoding (reject if not)

2. 3.

Simulate 𝐷𝐷 on 𝑤𝑤, i.e.,

• Tape 2: Maintain 𝑤𝑤 and head location of 𝐷𝐷

• Tape 3: Maintain state of 𝐷𝐷, update according to 𝛿𝛿

Accept iff 𝐷𝐷 ends in an accept state

3/4/2020 CS332 – Theory of Computation 24

Other decidable languages

𝐴𝐴DFA = 𝐷𝐷, 𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤} 𝐴𝐴NFA = 𝑁𝑁, 𝑤𝑤 NFA 𝑁𝑁 accepts 𝑤𝑤}

𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤}

3/4/2020 CS332 – Theory of Computation 25

CFG Generation

Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is Turing-

recognizable

Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴

CFG

Oninput 𝐺𝐺,𝑤𝑤

1. Enumerate all strings that can be generated from G

(i.e., all length-1 derivations, all length-2 derivations, …) 2. If any of these strings equal w, accept

3/4/2020 CS332 – Theory of Computation 26

CFG Generation

Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable

• Can have a rule 𝑆𝑆 → 𝜀𝜀

• Allremainingrulesoftheform𝐴𝐴→𝐵𝐵𝐵𝐵or𝐴𝐴→𝑎𝑎 • Cannot have 𝑆𝑆 on the RHS of any rule

Chomsky Normal Form for CFGs:

Lemma: Any CFG can be converted into an equivalent CFG in Chomsky Normal Form

Lemma: If 𝐺𝐺 is in Chomsky Normal Form, any nonempty string w that can be derived from 𝐺𝐺 has a derivation with at most2 𝑤𝑤 −1steps

3/4/2020 CS332 – Theory of Computation 27

CFG Generation

Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴CFG

Oninput 𝐺𝐺,𝑤𝑤

1. Convert 𝐺𝐺 into Chomsky Normal Form 2.Enumerateallstringsderivablein≤2𝑤𝑤 −1steps 3. If any of these strings equal 𝑤𝑤, accept

3/4/2020 CS332 – Theory of Computation 28

Mid-Semester Feedback Form

https://forms.gle/LTBEY1BoSZh8nupV6

3/4/2020 CS332 – Theory of Computation 29