程序代写代做代考 c++ compiler assembly Java algorithm CS 3800: Theory of Computing Turing Machines

CS 3800: Theory of Computing Turing Machines
Fall 2016 Instructor: Daniel Wichs

A General Model of Computation
• What is an algorithm in its full generality?
• Algorithms have been around since dawn of time. – Long addition, multiplication, division.
– Compass and straightedge constructions
– Euclid’s greatest common divisor algorithm
– Quadratic formula: finding roots of polynomials – Etc.
• Traditionally, algorithms were understood as a human construct. No precise mathematical definition.

Limited Notions of an Algorithm
• Already saw other limited notions of an algorithm: DFA, NFA, PDA.
• Proved that there are some problems that are not computable in these models.
• But all such models are restricted in some seemingly arbitrary ways.
– Trisecting an angle is easy with “protractor”
– Recognizing strings of the form anbncn is easy in JAVA.

The Big Questions
• Can we rigorously define a general notion of an algorithm?
• Are there problems that cannot be solved by any algorithm?

Entscheidungsproblem (English: “Decision Problem”)
In 1928, David Hilbert asked for an “algorithm” that takes as input a mathematical statement and decides weather the statement is true or false.
(A similar dream was already discussed by Leibniz in 17th century)
Source: wikipedia

In the years 1931 – 1936, a series of works showed there is no algorithm for the Entscheidungsproblem.
Kurt Gödel Alonzo Church
Alan Turing

In the years 1931 – 1936, a series of works showed there is no algorithm for the Entscheidungsproblem.
Each of these works included a different definition of a “general algorithm”.
• KurtGödelreliedonrecursivefunctions.
• AlonzoChurchdeveloped𝜆-calculus.
• AlanTuringdevelopedtheTuringMachine.
All of these definitions turn out to be equivalent!
Turing Machines are perhaps the most intuitive. Provide an inspiration for a general computer.

Our Plan
• Define Turing Machines (TMs). See how they work.
• Convince ourselves that TMs are powerful enough to implement any “reasonable algorithm”.
– Once we do this, a TM will be a synonym for algorithm. To show existence of a TM can just give pseudocode, and ignore the formal definition.
• Show that some problems are “undecidable”.

Turing Machine: like DFA with infinite memory tape.
• Initially, tape contains input, followed by “blanks”.
• Transitionsread/writeundertape-head
and also move the tape-head R (right) or L (left).
– detail: if attempt to move left of start, tape-head stays in place.
• There are accept and reject states. If the computation
enters such a state, it immediately halts. – otherwise can go on forever (loop)!
0 →1, R
0
1
0
1
1
0
0
1
0
–
–
–
…
tape head

EXAMPLE

Definition: Syntax Definition: A Turing Machine consists of a tuple
M = (Q, Σ, Γ, 𝛿, qstart, qaccept, qreject) where:
• Q is a finite set called the states.
• Σ is a input alphabet.
• Γ is tape alphabet such that Σ ⊆ Γ and Γ contains special blank symbol ‘-’ which is not in Σ.
• qstart ∈ Q is the start state.
• qaccept ∈ Q is the accept state , qreject ∈ Q is the reject state.
• 𝛿 : Q’ × Γ → Q × Γ × {L,R} is the transition function, where
Q’ = Q – { qaccept, qreject }
– Input: a state, read symbol.
– Output: next state, write symbol, tape-head direction.

Definition: Computation
Definition: Let M = (Q, Σ, Γ, 𝛿, qstart, qaccept, qreject) be a Turing Machine.
• A configuration of M is a tuple C=(u,q,v) such that u,v ∈ Γ∗ and q ∈ Q. (Can write uqv without commas.)
• A configuration C yields C’ if M goes from C to C’ in 1 step. – C = uqbw , C’ = ub’q’w and 𝛿(q,b) = (q’, b’, R)
– C = uaqbw, C’ = uq’ab’w and 𝛿(q,b) = (q’, b’, L)
– C = qbw, C’ = q’b’w and 𝛿(q,b) = (q’, b’, L) (tape-head on very left)
u
v
0
1
0
1
1
0
0
1
0
–
–
-…
tape head

Definition: Computation
Definition: Let M = (Q, Σ, Γ, 𝛿, qstart, qaccept, qreject) be a Turing Machine.
• A configuration of M is a tuple C=(u,q,v) such that u,v ∈ Γ∗ and q ∈ Q. (Can write uqv without commas.)
• A configuration C yields C’ if M goes from C to C’ in 1 step.
• A start configuration of M on input w is qstartw.
• An accepting (resp. rejecting) configuration is one where the state is qaccept (resp. qreject).

Definition: Computation
Definition: Let M = (Q, Σ, Γ, 𝛿, qstart, qaccept, qreject) be a Turing Machine.
M accepts (resp. rejects) w if there is a sequence of configurations C1 , C2 ,…, Cn such that:
• C1 is the start configuration of M on input w
• Ci yields Ci+1 for i = 1,…,n-1.
• Cn is an accepting (resp. rejecting) configuration

Language of a TM
• A TM M on input w can either accept, reject, or loop.
halt
• For a TM M, we define L(M) = { w | M accepts w}.
Say that M recognizes the language L(M).
• We say that M decides L if
– M accepts w ∈ L and M rejects w ∉ L.
– equivalently: M recognizes L and M always halts.
• A language L is recognizable (resp. decidable) if there is some TM recognizes (resp. decides) L.

Specifying a Turing Machine • Draw a state diagram, use formal definition:
too tedious – we will never do this!
• Give a “tape-head” level description:
– Imagine tape-head has small local memory which is
“fixed” and cannot grow with input size (states of TM).
– Describe how the tape-head should walk across the tape and what should it write.

Tape-Head Level Description L = { 02𝑛 : n ≥ 0 } all powers of 2.
• Walk tape-head from left to right and cross out every other 0.
– If tape contained a single 0, accept.
– Else if number of 0s was odd, reject.
– Else return to the left-hand end of tape, repeat.

Tape-Head Level Description L = { w#w: w ∈ {0,1}* }
• Check input is of form {0,1}*#{0,1}* reject otherwise.
• Walk tape-head from left to right:
– If everything crossed out other than #, accept.
– Find first non crossed out b ∈ {0,1} on the left of # and the first non crossed out b’ ∈ {0,1} to the right of #
• if one of b or b’ doesn’t exist, reject. • If b ≠ b’, reject.
– Return tape-head all the way to the left, and repeat.

Beyond Boolean Functions
Can also consider TMs that output more than just “accept/reject”.
Define the output of a TM as the contents of its tape when it enters an accept/reject state.
A TM M computes a function f : Σ* → Σ* if on every input w ∈ Σ* the TM halts and its tape contains f(w).
We say that f is computable if some TM M computes it.
Can check that basic functions such as addition, multiplication, division etc. are computable.

Variants of TMs
• Show: adding various features to TMs does not make them any more powerful.
• Can build a “compiler” that takes a TM with additional features and converts it to a standard TM.

Variant: Multi-Tape TM
0
1
0
1
1
0
0
1
0
–
–
–
…
0
0
1
1
0
–
–
–
–
–
–
–
…
1
1
1
1
0
0
0
0
0
–
–
–
…

Compiler: Multi-Tape to One Tape
0
1
0
1
#
1
1
0
#
1
0
1
–
-…
• Store contents of all tapes sequentially on a single tape separated by #.
• Remember tape-head positions by storing an “underlined” version of tape symbols.
• Each step of multi-tape TM is simulated by scanning entire tape of single-tape TM.
• Might need more space on one of the tapes – in that case shift everything over by 1 to the right.

Tape-Head Level Description
Show: There is a TM that computes binary addition. Input: a, b (binary). Output: a+ b
• Use two extra tapes. Copy a to tape1, b to tape2 in reverse order (unit position on left) and clear main tape.
• Return all tape heads to the left. Remember 1 bit: carry=0.
• Add two bits under tape-heads 1 and 2 plus carry (blank=0). Place result modulo 2 on main tape, update carry.
Move all tape heads one right.
Repeat until values under tape-head 1 and 2 both blank.
• Reverse contents of main tape.

Variant: Random Access TM
Can read/write to arbitrary locations in memory without scanning a tape. Memory modeled as infinite array R.
• In addition to standard tape that contains the input the TM has “location” and “value” tapes.
• There is a special “write” transition which sets R[location] = value using content of tapes.
• There is a “read” transition which sets the contents of the value tape to R[location].

Compiler: Random-Access to Multi-Tape
Can simulate Random Access TM with a multi-tape TM (and therefore also with single-tape TM).
• Store contents of array R on a tape as tuples (location1, value1), (location2, values2), …
• To simulate a read, scan R until find locationi that matches content of location tape. Write valuei on value tape. Put a blank if no such value is found.
• To simulate a write, scan R until you find locationi that matches content of location tape. Update valuei. If none found, append (location, value) to end of R.

How Powerful Are TMs?
Theorem: Any function computable in any programming language (JAVA, C++, LISP,…) is also computable by a TM.
Proof Outline:
Design a compiler that converts a JAVA program into TM.
• All programming languages are already compiled to “assembly code” for modern CPUs.
• Assembly code instructions can be implemented on a Random-Access TM.

Church-Turing Thesis
Any “algorithm” (in an informal sense) can be implemented on a Turing Machine.
• This is not a formal statement and hence cannot prove or disprove it.
• Turing Machines capture our informal understanding of what an algorithm is.

TM = Algorithm
• From now on, to describe a TM can just describe an
algorithm using high-level pseudocode .
– Should be sufficiently clear that a human can follow. – Can be confident that we can convert it to a TM.

TM = Algorithm
• Inputs to TM are strings. But, can encode anything as a string!
• For object O let denote encoding of O as a string.
– If i is an integer, can be representation of i in (e.g.,) binary.
– If G is a graph, many different ways to define : for each vertex
list all edges, 0/1-matrix, etc. Doesn’t matter which one is used.
– If M is a TM, can define by writing down the formal definition M = (Q, Σ, Γ, 𝛿, qstart, qaccept, qreject).