MA/CSSE 474 Theory of Computation Universal Turing Machine Church-Turing Thesis (Winter 2016, these slides were also used for Day 33) Your Questions? Previous class days' material Reading Assignments HW 14 problems

Tuesday's exam Anything else Another Two Tape Example: Addition Exercise: Use multiple tapes to multiply two non-negative integers represented in binary. Description can be high-level. Universal Turing Machine The Universal Turing Machine U U, when given descriptions of a TM M and an input string w, does what M would do when given input w.

To define the Universal Turing Machine U we need to: 1. Define an encoding scheme for TMs. 2. Describe the operation of U when it is given input , the encoding of: a TM M, and an input string w. Encoding a Turing Machine M We need to describe M = (K, , , , s, H) as a string: The states The tape alphabet The transitions

Encoding the States Let i be log2(|K|). Each state is encoded by a letter and a string of i binary digits. Number the states from 0 to |K|-1 in binary: The start state, s, is numbered 0. Number the other states in any order.

If t is the binary number assigned to state t, then: If t is the halting state y, assign it the string yt. If t is the halting state n, assign it the string nt. If t is the halting state h, assign it the string ht. If t is any other state, assign it the string qt. Example of Encoding the States Suppose M has 9 states. i=4 s = q0000, Remaining states (suppose that y is 3 and n is 4):

q0001 q0101 q0010 q0110 y0011 q0111 n0100 q1000 Encoding a Turing Machine M, Continued

The tape alphabet: Let j be log2(| |). Each tape alphabet symbol is encoded as ay for some y {0, 1}+, |y| = j The blank symbol gets the j-character representation of 0 Example: = { q, a, b, c }. q= a= b= c= a00

a01 a10 a11 j = 2. Encoding a Turing Machine M, Continued The transitions: Example: Specify s as q000. Specify H. (state, input, state, output, move)

(q000, a000, q110, a000, ) A Special Case We will treat this as a special case: An Encoding Example Consider M = ( { s, q, h }, { a, b, c }, { q, a, b, c }, , s, { h } ): state symbol

state/symbol representation s q (q, q, ) s q00

s a (s, b, ) q q01 s

b (q, a, ) h h10 s c (q, b, )

q a00 q q (s, a,) a

a01 b a10 q a (q, b, ) c

a11 q b (q, b, ) q c

(h, a, ) Decision problem: Given a string w, is there a TM M such that w= ? Is this problem decidable? = (q00,a00,q01,a00,), (q00,a01,q00,a10,),

(q00,a10,q01,a01, ), (q00,a11,q01,a10,), (q01,a00,q00,a01,), (q01,a01,q01,a10,), (q01,a10,q01,a11,), (q01,a11,h10,a01,) Enumerating Turing Machines Theorem: There exists an infinite lexicographic enumeration of: (a) All syntactically valid TMs. (b) All syntactically valid TMs with specific input alphabet . (c) All syntactically valid TMs with specific input alphabet and specific tape alphabet .

Enumerating Turing Machines Proof: Fix = {(, ), a, q, y, n, h, 0, 1, comma, , }, ordered as listed. Then: 1. Lexicographically enumerate the strings in *. 2. As each string s is generated, check to see whether it is a syntactically valid Turing machine description. If it is, output it. To restrict the enumeration to symbols in sets and , check, in step 2, that only alphabets of the appropriate sizes are allowed. We can now talk about the ith Turing machine. Can the ith and jth TMs ever be the same machine?

Another Win of Encoding One big win of defining a way to encode any Turing machine M: We can talk about operations whose input and output are programs (TMs). Example of a Transforming TM T: Input: a TM M1 that reads its input tape and performs some operation P on it. Output: a TM M2 that performs P on an empty input tape. Encoding Multiple Inputs Let:

mean a single string that encodes the sequence of individual values x1, x2, , xn The Specification of the Universal TM On input , U must simulate M's action on w: Halt iff M halts on w. If M is a deciding or semideciding machine, then: If M accepts, accept. If M rejects, reject. If M computes a function, then

U() must equal M(w). How U Works U will use 3 tapes: Tape 1: Ms tape (using the alphabet encoding). Tape 2: , the program that U is running. Tape 3: Ms state. The Universal TM Initialization of U (start with on tape 1, other tapes blank): 1. Copy onto tape 2. 2. Look at , figure out what i is, and write the encoding of state

s on tape 3. After initialization: The Operation of U Simulate the steps of M : 1. Until M would halt do: 1.1 Scan tape 2 for a quintuple that matches the current state, tape symbol pair. 1.2 Perform the associated action, by changing tapes 1 and 3. If necessary, extend the tape. 1.3 If no matching quintuple found, halt. Else loop. 2. Report the same result M would report.

How long does U take? If A Universal Machine is Such a Good Idea Could we define a Universal Finite State Machine? Such a FSM would accept the language: L = { : F is a FSM, and w L(F) } The Church-Turing Thesis Are We Done? FSM PDA Turing machine Is this the end of the line? There are still problems we cannot solve with a TM:

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? 1. Can we come up with a system of axioms that makes all true statements be theorems (I.e. provable from the axioms)? The set of axioms can be infinite, but it must be decidable 2.

Can we always decide whether, given a set of axioms, a statement is a theorem or not? In the early 20th century, it was widely believed that the answer to both questions was "yes." Gdels Incompleteness Theorem Kurt Gdel showed, in the proof of his Incompleteness Theorem [Gdel 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.

Complete: All true statements in the language of the theory are theorems The Entscheidungsproblem From Wikipedia: The Entscheidungsproblem ("decision problem", David Hilbert 1928) asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language, and produce as output either "True" or "False" according to whether the statement is true or false. The algorithm need not justify its answer, nor provide a proof, so long as it is always correct. Three equivalent formulations: 1. Does there exist an algorithm to decide, given an arbitrary

sentence w in first order logic, whether w is valid? 2. Given a set of axioms A and a sentence w, does there exist an algorithm to decide whether w is entailed by A? 3. 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 isnt a formal statement, so we cant prove it. But many different computational models have been proposed and they all turn out to be equivalent. The Church-Turing Thesis 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 Conways Game of Life One dimensional cellular automata DNA-based computing Lindenmayer systems The Lambda Calculus The successor function: ( 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 number data type. All expressions are functions. But the natural numbers can be defined as lambda calculus functions. So the lambda calculus can effectively describe numeric functions. The Lambda Calculus > (define Y (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))))

> (define H (lambda (g) (lambda (n) (if (zero? n) 1 (* n (g (- n 1))))))) > ((Y H) 5) 120 > -Calculus in Scheme The Applicative Y Combinator

> (((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))) (lambda (g) (lambda (n) (if (zero? n) 1 (* n (g (- n 1))))))) 5) 120 Tag Systems A tag system (or a Post machine) is an FSM augmented

with a FIFO queue. Simple for WW: Not so simple for PalEven The Power of Tag Systems Tag systems are equivalent in power to Turing machines because the TMs tape can be simulated with the FIFO queue. Suppose that we put abcde into 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 TMs 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. The Game of Life Playing the game

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). Well say that a game halts iff it reaches some stable configuration. Elementary Cellular Automata Wolframs Rule 110 is a universal

computer, if you can figure out how to encode the program and the input in the initial configuration: For some fascinating pictures, look up Rule 110. Conjectured in 1985 to be Turing complete, proved in 2000 by Matthew Cook. Also: http://en.wikipedia.org/wiki/A_New_Kind_of_Science