L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.
Rony
Chapter18TheChurch-TuringThesisFile.pptThe Church-Turing Thesis
Chapter 18
Are We Done?
FSM PDA Turing machine
Is this the end of the line?
There are still problems we cannot solve:
● There is a countably infinite number of Turing machines
since we can lexicographically enumerate all the strings
that correspond to syntactically legal Turing machines.
● There is an uncountably infinite number of languages over
any nonempty alphabet.
● So there are more languages than there are Turing
machines.
What Can Algorithms Do?
Can we make all true statements theorems?
Can we decide whether a statement is a theorem?
Gödel’s Incompleteness Theorem
Kurt Gödel showed, in the proof of his Incompleteness Theorem [Gödel 1931], that the answer to question 1 is no. In particular, he showed that there exists no decidable axiomatization of Peano arithmetic that is both consistent and complete.
The Entscheidungsproblem
Does there exist an algorithm to decide, given an arbitrary sentence w in first order logic, whether w is valid?
Given a set of axioms A and a sentence w, does there exist an algorithm to decide whether w is entailed by A?
Given a set of axioms, A, and a sentence, w, does there exist an algorithm to decide whether w can be proved from A?
The Entscheidungsproblem
To answer the question, in any of these forms, requires formalizing the definition of an algorithm:
● Turing: Turing machines.
● Church: lambda calculus.
Turing proved that Turing machines and the lambda calculus are equivalent.
Church's Thesis
(Church-Turing Thesis)
All formalisms powerful enough to describe everything we think of as a computational algorithm are equivalent.
This isn’t a formal statement, so we can’t prove it. But many different computational models have been proposed and they all turn out to be equivalent.
Examples of equivalent formalisms:
● Modern computers (with unbounded memory)
● Lambda calculus
● Partial recursive functions
● Tag systems (FSM plus FIFO queue)
● Unrestricted grammars:
aSa B
● Post production systems
● Markov algorithms
● Conway’s Game of Life
● One dimensional cellular automata
● DNA-based computing
● Lindenmayer systems
The Church-Turing Thesis
The Lambda Calculus
The successor function:
(λ x. x + 1)
(λ x. x + 1) 3 = 4
Addition: (λ x. λ y. x + y) 3 4
This expression is evaluated by binding 3 to x to create the new function (λ y. 3 + y), which is applied to 4 to return 7.
In the pure lambda calculus, there is no built in data type number. All expressions are functions. But the natural numbers can be defined as lambda calculus functions. So the lambda calculus can effectively describe numeric functions just as we have done.
Tag Systems
A tag system (or a Post machine) is an FSM augmented with a FIFO queue.
A tag system for WW:
What about a tag system for PalEven?
The Power of Tag Systems
Tag systems are equivalent in power to Turing machines because the TM’s tape can be simulated with the FIFO queue.
Suppose that we push abcde onto the queue:
a b c d e
To read the queue, we must remove the a first.
But suppose we want to remove e first:
The Power of Tag Systems
Tag systems are equivalent in power to Turing machines because the TM’s tape can be simulated with the FIFO queue.
Suppose that we push abcde onto the queue:
a b c d e
To read the queue, we must remove the a first.
But suppose we want to remove e first:
Treat the queue as a loop.
Post Production Systems
A Post system P is a quintuple (V, , X, R, S):
● V is the rule alphabet,
● is a subset of V,
● X is a set of variables whose values are drawn from V*,
● R (the set of rules) is a finite subset of:
(V X)* (V X)*
Every variable on the RHS must also be on the LHS.
● S can be any element of V - .
● LHS may contain multiple symbols.
● Rules may contain variables.
● LHS must match entire string. So, A B becomes:
XAY XBY
A Post Production System
WW = {ww : w {a, b}*}.
P = ({S, a, b}, {a, b}, {X, Y}, R, S), R =
(1) XS XaS /* Generate (a b)* S.
(2) XS XbS
(3) XS XX /* Create a second copy of X.
This Post system can generate, for example, the string abbabb:
S (using (1) and letting X match )
aS (using (2) and letting X match a)
abS (using (2) and letting X match ab)
abbS (using (3) and letting X match abb)
abbabb
A Markov algorithm M is a triple (V, , R), where:
● V is the rule alphabet, which contains both working symbols
and input symbols. If M is a decider or a semidecider, V will
contain two special working symbols, Accept and Reject.
● is a subset of V, and
● R is an ordered list of rules, each of which is an
element of V* V*. There are two kinds of rules:
● Continuing, written as X Y, and
● Terminating, written as X Y
As with Turing machines, there is no special start symbol, but there will be an input string.
Markov Algorithms
A Markov Algorithm Interpreter
Markovalgorithm(M, w) =
1. Until no rules apply or the process has been terminated by
executing a terminal rule do:
1.1 Find the first rule in the list R that matches against w.
If that rule matches w in more than one place, choose
the leftmost match.
1.2 If no rule matches then exit.
1.3 Apply the matched rule to w by replacing the substring
that matched the rule’s LHS with the rule’s RHS.
1.4 If the matched rule is a terminating rule, exit.
2. If w contains the symbol Accept then accept.
3. If w contains the symbol Reject then reject.
4. Otherwise, return w.
Notice: Markov algorithms are deterministic.
A Markov Algorithm for AnBnCn
(1) #a %
(2) #b Reject
(3) #c Reject
(4) %a a%
(5) %b ?
(6) % Reject
(7) ?b b?
(8) ?c
(9) ? Reject
(10) # Accept
(11) #
Example: aabbbccc
The Power of Markov Algorithms
Theorem: The Markov algorithm formalism is equivalent in power to the Turing machine.
Proof: By two constructions. Show that each formalism can simulate the other.
The Game of Life
At each step of the computation, the value for each cell is determined by computing the number of neighbors (up to a max of 8) it currently has, according to the following rules:
● A dead cell with exactly three live neighbors becomes a live cell
(birth).
● A live cell with two or three live neighbors stays alive (survival).
● In all other cases, a cell dies or remains dead (overcrowding or
loneliness).
We’ll say that a game halts iff it reaches some stable configuration.
Elementary Cellular Automata
Wolfram’s Rule 110 is a universal computer if you can
figure out how to encode the program and the input in the
initial configuration:
DNA Computing
Let G be a directed graph, with one vertex s designated as the start vertex and another vertex d designated as the end vertex. A Hamiltonian path through G is a path that begins at s, ends at d, and visits each other node in G exactly once.
The Hamiltonian path problem: given a directed graph G, with designated s and d, does there exist a Hamiltonian path through it?
n3
n2
s n4
n5
n1
d
Adelman’s Procedure
1. He chose a particular graph G (with 7 vertices and 14 edges).
2. He encoded each vertex of G as a sequence of 8 nucleotides. For example, a vertex might be represented as ACCTGCAG.
3. He encoded each directed edge of G as a sequence of 8 nucleotides, namely the last four from the encoding of the start vertex and the first four from the encoding of the end vertex. So an edge from ACTTGCAG to TCGGACTG would be encoded as:
GCAGTCGG.
5. He combined the vertex-complement molecules and the edge molecules in a test tube, along with water, salt, some important enzymes, and a few other chemicals required to support the natural biological processes.
Adelman’s Procedure
4. He synthesized many copies of each of the edge sequences, as well as many copies of the DNA complements of all the vertex encodings.
Example: The complement of ACTTGCAG is TGAACGTC.
6. He allowed to happen the natural process by which complementary strands of DNA in solution will meet and stick together (anneal).
G C A G T C G G
T G A A C G T C A G C C T G A C
Adelman’s Procedure
Adding another edge:
G C A G T C G G A C T G G G C T
T G A A C G T C A G C C T G A C
7. He allowed a second biological reaction to occur. The enzyme ligase that had been added to the mixture joins adjacent sequences of DNA.
8. He used the polymerase chain reaction (PCR) technique to make massive numbers of copies of exactly those sequences that started at the start vertex and ended at the end one. Other sequences were still present in the mix after this step, but in much lower
numbers.
9. He used gel electrophoresis to select only those molecules whose length corresponded to a Hamiltonian path through the graph.
Adelman’s Procedure
10. He checked that each of the remaining vertices occured in the selected molecules. For each intermediate vertex do:
10.1. Use a DNA “probe” to attract molecules that contain the DNA sequence for the vertex that is being checked.
10.2. Use a magnet to attract the probes.
10.3. Throw away the rest of the solution.
11. Only molecules that corresponded to paths that started at the start vertex, ended at the end vertex, had the correct length for a path that visited each vertex exactly once, and contained each of the vertices could still be present. So if any DNA was left, a Hamiltonian path existed.
Adelman’s Procedure
