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

BU CS 332 – Theory of Computation
Lecture 10:
• Turing Machines
Reading:
Sipser Ch 3.1‐3.2
• TM Variants
Mark Bun February 26, 2020

Turing Machines – Motivation
So far in this class we’ve seen several limited models of computation
Finite Automata / Regular Expressions
• Can do simple pattern matching (e.g., substrings), check parity, addition
• Can’t recognize palindromes
Pushdown Automata / Context‐Free Grammars
• Can count and compare, parse math expressions • Can’t recognize 𝑎􏵳𝑏􏵳𝑐􏵳 𝑛 􏶖 0􏶤
2/26/2020 CS332 ‐ Theory of Computation 2

Turing Machines – Motivation
Goal:
Define a model of computation that is
1) General purpose. Captures all algorithms that can be implemented in any programming language.
2) Mathematically simple. We can hope to prove that things are not computable in this model.
2/26/2020 CS332 ‐ Theory of Computation 3

A Brief History
2/26/2020 CS332 ‐ Theory of Computation 4

1900 – Hilbert’s Tenth Problem
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
2/26/2020 CS332 ‐ Theory of Computation
5
David Hilbert
1862‐1943

1928 – The Entscheidungsproblem The “Decision Problem”
Wilhelm Ackermann 1896‐1962
David Hilbert
1862‐1943
2/26/2020
CS332 ‐ Theory of Computation
6
Is there an algorithm which takes as input a formula (in first‐order logic) and decides whether it’s logically valid?

1936 – Solution to the Entscheidungsproblem “An unsolvable problem of elementary
Alonzo Church 1903‐1995
Alan Turing 1912‐1954
Model of computation: Turing Machine CS332 ‐ Theory of Computation 7
2/26/2020
number theory“
Model of computation: 𝜆‐calculus (CS 320)
“On computable numbers, with an application to the Entscheidungsproblem”

Turing Machines
2/26/2020 CS332 ‐ Theory of Computation 8

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
2/26/2020 CS332 ‐ Theory of Computation 9

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

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

TMs vs. Finite / Pushdown Automata
2/26/2020 CS332 ‐ Theory of Computation 12

Three Levels of Abstraction
High‐Level Description
An algorithm (like CS 330)
Implementation‐Level Description
Describe (in English) the instructions for a TM • How to move the head
• What to write on the tape
Low‐Level Description
State diagram or formal specification
2/26/2020 CS332 ‐ Theory of Computation 13

Example
Decide if
􏶊􏶵
High‐Level Description
Repeat the following:
• If there is exactly one
• If there is an odd number of • Delete half of the s in
, accept s in
2/26/2020 CS332 ‐ Theory of Computation
14
in
, reject

Example
Decide if
􏶊􏶵
Implementation‐Level Description
1.
While moving the tape head left‐to‐right:
2. 3.
Return the head to the left end of the tape Go back to step 1
a) Cross off every other 0
b) If there is exactly one 0 when we reach the right end of the tape, accept
c) If there is an odd number of 0s when we reach the right end of the tape, reject
2/26/2020 CS332 ‐ Theory of Computation 15

Example
Decide if
􏶊􏶵
Low‐Level Description
2/26/2020 CS332 ‐ Theory of Computation 16

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
2/26/2020
CS332 ‐ Theory of Computation
17
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
2/26/2020 CS332 ‐ Theory of Computation 18

Configuration of a TM
A string with captures the state of a TM together with the contents of the tape
2/26/2020 CS332 ‐ Theory of Computation
19
􏶎

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 )

Example:
􏶎
2/26/2020 CS332 ‐ Theory of Computation
20
􏶎

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