1. Summary of Universal Cellular Automata
A Discussion of Universal Turing Machines and How CAs can Emulate Them1.1. Opening
Kris began by showing some images that raised some questions.
-
Kris showed an image from Steven Wolfram's book , A New Kind of Science, that displayed a CA that displays the prime numbers.
-
Main Question: How complicated of a computation can a CA perform? What useful calculations can a CA do?
-
Rule # 30 is an example of what Wolfram refers to as Class III, "aperiodic, random-like patterns". In 1990 Erica Jen proved that the "central" cells values are non periodic given the intial data string ...00000100000....
-
Rule # 110 is an example of what Wolfram refers to as Class IV, "a complex pattern with localized structure that eventually becomes homogenous." The CA falls into a predictable patern after 2,780 updates.
-
Mark raised another key question: How much does a CA depend on the initial string?
1.2. Turing Machines & Universal Turing Machines
Kris explained what a Turing Machine and a Universal Turing Machine are. Here are some of the issues that were raised.
-
Alan Turing was interested in what can be done algorithmically and what cannot.
-
Turing machines can be thought of as the following.
-
It is a machine that processes an infitely long tape.
-
The part of the tape entering the machine has input coded in binary as does the part of the tape leaving the machine (ouput).
-
Inside the machine there is a rule table. The rule table states "If the reader reads 0 or 1 and the sate of the machine is n then write either 1 or 0 and either move 1 left, move 1 right, or stop and change the state of the machine to m."
-
A task is computable if you can write a turing machine to do it.
-
Some helpful terms:
-
The instantaneous description (ID) for a turing machine is the number coding for all te data on the tape, the machine state, the position of the head, and if the machine is stopped.
-
The machine number (MN) for a turing machine is the number coding for the rule table and tell which turing machine this is
-
A computable number is a real number whose decimal expansion is given by some turing machine, 1/3, Pi, e, sqrt(2), etc.
-
T_n(M) = P means that the machine #n acting on input M produces output P
-
T_n(M) = "box" means that the machine #n acting on input M doesn't stop
-
Universal Turing Machine, U(n,M) = T_n(M), a Turing machine that takes as input another Turing machine (n) and an infinite tape.
-
A Universal Turing Machine exhibits arbitrarily complicated behavior.
-
Turing's Theorem (The Halting Theorem) There does not exist a Turing machine that takes as input (n,M), stops in finite time, and also ouputs 0 or wond depending on if T_n(M)="box"
-
Kris showed a proof of this using an argument similar to Cantor's diagonalization process.
1.3. Turing Machines and Cellular Automata
-
Proposition: Any Turing machine with x states can be simulated by a one-dimensional, nearest-neighbor cellular automata with 2 + 2x colors.
-
Definition: A cellular automata simulates a Turing machine if there is a bijection from the possible instantaneous descriptions of the Turing machine to the possible instantaneous descriptions of the cellular automata, so that if the cellular automata is run with initial state M, for a fixed number i, the ith instantaneous description of the cellular automata is equal to the ith instantaneous description of the Turing machine if run with the initial state M.
1.4. How Simple Can a Universal CA be?
-
1970's, 18 color nearest-neighbor CA constructed
-
1980's, 7 color nearest-neighbor CA constructed
-
1987 (Don Gordon),9139 color nearest-neighbor totalistic CA constructed, 967 for semi-totalistic
-
Conway's Game of Life is universal (semi-totalistic)
-
1990's Matthew Cook showed that rule #110 is universal. Thus, we cannont determine whether rule # 110 with input M will ever code for a stopped Turing machine.
