Registered: Aug 2003
Posts: 712

On the fifth anniversary of the publication of A New Kind of Science and shortly after release of Mathematica 6, Wolfram announced a challenge question related to one of the book's conjectures.

All the details of the prize can be found here -

http://www.wolframscience.com/prizes/tm23/index.html

While that site has a lot more detail than I could give you here, if you have specific questions about the system in question I'd be happy to answer them. Or if you want to share ideas about the problem you are invited to post here.

For starters, I note that TuringMachine is a built in function in Mathematica 6, and you can simulate the system involved in the prize, from a blank tape and starting head state 1, with

data = TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, 100] 

To see more steps just raise that 100.

You can get nice TM graphics for any TM with a piece of Todd Rowland's code -

Options[TMGraphics] = Prepend[Options[ArrayPlot], 
"States" -> True];

TMGraphics[data_, s_, k_, opts : OptionsPattern[]] :=
  ArrayPlot[Last /@ data,
   Sequence @@ FilterRules[{opts}, Except["States"]],
   Epilog ->
    If[TrueQ[OptionValue["States"]],
     MapIndexed[
      Translate[
        Rotate[With[{r = .18}, {Disk[{0, 0}, r],
           Polygon[{{r, 0}, {-r, 0}, {0, .6}, {r, 0}}]}],
         2 (#[[1, 1]] - 1) [Pi]/s, {0, 0}], {#[[1, 2]] - 1/2,
         Length[data] - First[#2] + 1/2}] &, data], {}]]

I hope this is useful...

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

This is a very good problem.

My guess (and it's only a guess) is that this given Turing machine is not universal. I say this because it seems that the main thing that this machine does is change red to yellow and yellow to red when the pointer is traveling left and white to yellow in the interior of a red and yellow region and white to red on the border of such a region. It eventually changes all white cells to red or yellow.

When the pointer is travelling right, the pattern is a little less predictible, since sometimes red stays red and yellow stays yellow. But I can't see how this behavior is going to lead to universality. In the long run, when looking at 200 steps of left compressed evolution here: http://www.wolframscience.com/prizes/tm23/gallery/
one witnesses behavior similar to rule 30. It's very random and chaotic.

Most people believe that rule 30 is not universal, myself included. (Although I think I read that Stephen Wolfram believes that rule 30 is universal.) A system can be computationally irreducible but not universal, as I think is the case with rule 30.

What does everyone else think? Does anyone think this Turing machine is universal? Why?

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 20

There is a minor typo in the TMGraphics Code that will prevent it from executing properly. [Pi] should be \[Pi]

__________________
Seth J. Chandler
Foundation Professor of Law
University of Houston Law Center
Houston, Texas 77204

Report this post to a moderator | IP: Logged

Registered: Jun 2006
Posts: 2

I strongly suspect that this problem is either formally undecidable or just impractical to answer.

As far as I know, all previous TM universality proofs have started out with an "engineering model" for the simulation. The elementary rules for the machine itself are then chosen to support the model. The 2,5 Turing machine (NKS p.707) was an exception: this machine was found to be trivially equivalent to cellular automaton rule 110, for which Matthew Cook developed a universal simulation. The 2,3 machine does not appear to simulate any other system in a trivial way, so we are forced to develop a universality model for the TM itself, starting from the given TM rules. This has never been done before.

According to Wolfram's conjecture, any system with sufficient "complexity" or "pseudo-randomness" is universal. Many mathematicians doubt this hypothesis, for a number of reasons:

• As Nobel laureate Prof. Steven Weinberg (Dept. of Physics, U. Texas at Austin) explains in the New York Review of Books, we are lacking a suitable definition of complexity. "Computational irreducibility" is not adequate:
  

  
  "The trouble with Wolfram's conjecture is not only that it has not been proved—a deeper trouble is that it has not even been stated in a form that could be proved. What does Wolfram mean by complex? If his conjecture is not to be a tautology, then we must have some definition of complex behavior independent of the notion of universality. The pattern produced by the rule 110 cellular automaton certainly looks complex, but what criterion for complexity can we use that would tell us that it is complex enough for Wolfram's conjecture to apply?
  
  "There is a well-known parallel problem in defining randomness. The most common precise definition of the randomness of a string of digits or of a sequence of black and white cells on a tape is that it is random if there is no way of describing it with a string of shorter length. The trouble is that according to this definition the string of digits in a number like the square root of two would not qualify as random, because it can be described very simply —it is the square root of two—even though it surely looks random. (Mathematica gives the first thirty digits as 1.41421356237309504880168872420.) In the same way, it wouldn't do to define the output of a cellular automaton like rule 110 with a single black cell in the top row as complex only if it can't be described in simple terms, because it can be described in simple terms—it is the output of rule 110 with a single black cell in the top row. There are other definitions of randomness, such as the absence of correlations: the digits in the square root of two can be said to be random because, as far as is known, being given one digit at an unidentified decimal place tells you nothing at all about what the next digit is likely to be. Wolfram has not even begun to formulate a similar definition of complexity.
  
  "In fact, as he admits, for Wolfram the real test of the complexity of a pattern is that it should look complex."
  

  
  
• Prof. Lawrence Gray (School of Mathematics, U. Minnesota) points out in his AMS review that the universality proof for rule 110 is a highly elaborate construction (NKS p.675-689), which "just barely works" and "shows just how tenuous the original conjecture was." The postulated universality of rule 30 is, according to Gray, "sheer wishful thinking."
  

Last edited by MatthewF on 05-20-2007 at 05:46 PM

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

If one observes for random inputs the behavior of the portion of the output of the prize Turing machine which Wolfram believes seems "complex enough that it could support universality", one always sees randomness and chaos, similar to Rule 30 and the Collatz 3n+1 sequence. But for a system to be universal, the behavior of the system cannot always be random and chaotic. All possible behaviors must be represented in the output for different inputs; therefore, why would anyone think this Turing machine is universal under any reasonable definition of universality?

And not only this, but one can argue that it is expected that simple programs will produce chaotic and random outputs like the prize Turing machine, Rule 30, and the Collatz sequence. Why? If there were no simple programs with this characteristic, then one could determine whether a string of outputs is random (according to Chaitin's definition of randomness) just by looking at it - if it looks random, then it must be random. But this would contradict Chaitin's Theorem, which says that it is impossible to verify that a string is random for sufficiently large strings. Therefore, there must be an intermediate level of complexity - computationally irreducible and random/chaotic, but not universal.

__________________
Craig

Last edited by Craig Feinstein on 06-11-2007 at 01:18 AM

Report this post to a moderator | IP: Logged

Registered: May 2007
Posts: 5

Originally posted by Craig Feinstein
If one observes for random inputs the behavior of the portion of the output of the prize Turing machine which Wolfram believes seems "complex enough that it could support universality", one always sees randomness and chaos, similar to Rule 30 and the Collatz 3n+1 sequence. But for a system to be universal, the behavior of the system cannot always be random and chaotic. All possible behaviors must be represented in the output for different inputs; therefore, why would anyone think this Turing machine is universal under any reasonable definition of universality?

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

Denis,

You said: 'You say "All possible behaviors must be represented in the output for different inputs" but in class 3 for example in rule 30 I think we have this.'

How so? When I examine the output of Rule 30 for various inputs, I only see chaos and randomness. I never see any stability. However, Rule 110 is a different story. One sees stability, chaos and randomness, and self similarity; every possible system is emulated in its output.

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Jun 2006
Posts: 2

We have to be careful with words like "randomness", "chaos" and "stability". Try encrypting a paragraph of text using any respectable encryption algorithm, and it will immediately appear "random". Then change one letter of the original text and encrypt it again, and the entire jumble of encrypted data will change. It would be easy to convince yourself that the encryption algorithm is "random" and "chaotic" - but you know, of course, that no information has been lost, and the encryption is fully reversible. The human eye is not a reliable judge of information content.

The requirement that "all possible behaviors should be represented in the output" is also somewhat vague: I'm still waiting for a proper mathematical definition of "all possible behaviors" that doesn't depend circularly on the definition of universality. In some sense a true random number generator will display all possible behaviors, if you wait long enough. A team of monkeys will eventually type the complete works of Shakespeare, but that doesn't mean you can program them to do so.

Rule 110 was a relatively easy system to program (I say 'relatively', as there were years of work involved), because the information flow was tangible to the human mind. You could see patterns moving and interacting. Rule 30 and the 'prize' Turing machine do not display any intuitive patterns, because the information flow is not localized. However, if you look at the output of these rules with an appropriate "decryption algorithm", the patterns might become blindingly obvious, just as your web browser is capable of tranforming a 128-bit-encrypted stream of data into English. The trouble is, we will probably never know.

Last edited by MatthewF on 06-12-2007 at 05:02 PM

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

MatthewF wrote: "Rule 30 and the 'prize' Turing machine do not display any intuitive patterns, because the information flow is not localized. However, if you look at the output of these rules with an appropriate "decryption algorithm", the patterns might become blindingly obvious, just as your web browser is capable of tranforming a 128-bit-encrypted stream of data into English."

I never thought about this possibility. Thank you for bringing this to my attention!!! Therefore, I take back everything I said previously in this thread.

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

There is no universal 2-state 3-color Turing machine. The reason why is simple. In order for a computer to be universal (not just Turing machines but also cellular automata) it is necessary for the machine to be able to process at least 3 bits of information in a single step of computation. For instance, rule 110 has this characteristic, because each cell is updated based upon three bits of information:

000 -> 0
001 -> 1
010 -> 1
011 -> 1
100 -> 0
101 -> 1
110 -> 1
111 -> 0

A 2-state 3-color Turing machine does not have this characteristic. It can only process log_2 6 bits of information in a single step of computation, since 2x3=6.

The reason why 3 bits is the minimum required for a computer to be universal is in this brief note that I posted here:

http://eprintweb.org/S/article/cs/0706.4440

Update: See the thread "Universal Computation with only 6 states" started by Alastair Hewitt. We see from this that my claim that a machine must be able to process 3 bits of information to be universal does not hold true for Turing machines with a circular tape. It only holds true for Turing machines with infinite tape and cellular automata.

Another Update: I now believe that my proof that there are no 2-state 3-color Turing machines is not valid. I withdrew it from the arxiv.org. I welcome anyone to try to fix my proof.

__________________
Craig

Last edited by Craig Feinstein on 08-30-2007 at 08:00 PM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Since the predecessor statement is true for all TMs, and TMs as a class are the definition of universality, and certainly contain any number universal machines, including e.g. the 2,5 machine given in the book which emulates rule 110, the alleged consequence cannot be correct. The number of bits processed at a single step, as opposed to processed at all over any number of primitive operations, is simply not relevant to the question of universality.

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

Jason said: "Since the predecessor statement is true for all TMs, and TMs as a class are the definition of universality, and certainly contain any number universal machines, including e.g. the 2,5 machine given in the book which emulates rule 110, the alleged consequence cannot be correct."

The statement I made in my post certainly does not apply to all Turing machines. Specifically, it does not apply to the 2,5 Turing machine in NKS which emulates rule 110, because such a Turing machine is able to process at least 3 bits of information on its tape-head, as 2x5=10 and log_2 10>= 3. It also does not apply to 2,4 Turing machines, i.e., it is still possible that there are 2,4 Turing machines that are universal, since such a machine is able to process 3 bits of information on its tape-head, as 2x4=8 and log_2 8=3. Similarly, it is still possible that there are 3,3 universal Turing machines, since 3x3=9 and log_2 9>= 3.

However, there is no way that a 2,3 Turing machine can be universal. It's simply too dumb to be universal, as its tape-head cannot even process 3 bits of information, which is necessary for universality.

Jason also said “The number of bits processed at a single step, as opposed to processed at all over any number of primitive operations, is simply not relevant to the question of universality.”

If what Jason is saying is true, that the number of bits that are processed at a single step is not relevant to the question of universality, then why can’t there exist a 3-state 2-color universal Turing machine or a 2-state 2-color universal Turing machine? (It is already accepted that such Turing machines cannot be universal.)

__________________
Craig

Last edited by Craig Feinstein on 07-03-2007 at 02:19 AM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

There is no requirement that an emulation use the same number of steps as the emulated system. It is perfect typical for, e.g., the simpler system to use a large block of cells to encode a single cell in the emulated system and details of its perhaps more sophisticated state. All TMs have access to a potentially infinite tape array on which they can write and read back an infinite number of bits. If an operation corresponding to a single step of the emulated system needs 5 bits or 10 bits, then the emulating system may need to encode a state and operation pair on a block of tape cells 10 wide or whatever. That is perfectly allowed, and nothing in the PDF at the archive link addresses the question. (The archive PDFs (1) or (2) need not be encoded in the head state, but might instead be encoded in whether the parity of the emulating machine's tape in a region 4 long is even or odd, or whatever).

As for that, or why, simpler TMs are not universal, we can simple enumerate them all and see what all of them do, and none of them do anything complex enough to support universal computation. Our knowledge in the matter is not a function of a theorem about the required per step information, but an empirical observation of their actual behavior. For the 2,3 machine in question, it is entirely possible that it can't support universal computation, but this has not yet been shown. It clearly does more than any of the 2,2s does.

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

Jason wrote: “There is no requirement that an emulation use the same number of steps as the emulated system. It is perfect typical for, e.g., the simpler system to use a large block of cells to encode a single cell in the emulated system and details of its perhaps more sophisticated state. All TMs have access to a potentially infinite tape array on which they can write and read back an infinite number of bits. If an operation corresponding to a single step of the emulated system needs 5 bits or 10 bits, then the emulating system may need to encode a state and operation pair on a block of tape cells 10 wide or whatever. That is perfectly allowed, and nothing in the PDF at the archive link addresses the question.”

And I respond that this is all irrelevant to the argument in my paper. The argument in my paper is independent of the specifics of how the universal Turing machine encodes the rules and tape of the Turing machine that it is emulating. My paper does not need to address this question.

Jason wrote: “(The archive PDFs (1) or (2) need not be encoded in the head state, but might instead be encoded in whether the parity of the emulating machine's tape in a region 4 long is even or odd, or whatever).”

I respond to Jason, consider the following scenario:

I want to teach a dog calculus. The dog does not have the intellectual capacity to learn calculus; however, if I attach to the dog’s collar a tape with lots of instructions written on it encoding the rules for calculus, then the dog should then be able to understand calculus or at least perform calculus calculations.

Does this make sense? Of course not! Yet, this is what you are arguing one can do in order to teach a 2,3 Turing machine to be universal, even though its brain, the tape head, clearly doesn’t have this capacity, since its tape head cannot even process 3 bits of information.

Jason wrote: “As for that, or why, simpler TMs are not universal, we can simple enumerate them all and see what all of them do, and none of them do anything complex enough to support universal computation. Our knowledge in the matter is not a function of a theorem about the required per step information, but an empirical observation of their actual behavior.”

Jason, you think it is a coincidence that there are no 3-state 2-color universal machines or 2-state 2-color universal machines? It’s an accident that just happens to be true when you empirically look at the actual behavior of such machines? You can’t be serious. Obviously, the reason why there are no 3-state 2-color or 2-state 2-color universal TMs is because the tape head of such machines does not have enough processing power to support universality. Similarly, 2-state 3-color Turing machines don’t have enough processing power to support universality.

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 35

Because I don't want my note describing the solution to the Wolfram prize puzzle to be misinterpreted as I believe Jason misinterpreted it, I made some changes to it here: http://arxiv.org/abs/0706.4440

See the second version for the changes.

__________________
Craig

Report this post to a moderator | IP: Logged