# 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