A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- The Universality of Rule 110 and the ability to iterate over all inputs (http://forum.wolframscience.com/showthread.php?threadid=961)

The Universality of Rule 110 and the ability to iterate over all inputs

I have a rather general question about the universality of Rule 110. This is more of a
"philosophical" question I suppose. Variants of this question may have been asked before, but after perusing the forum I didn't really see anything exactly like it, so I'm going to venture it here:

The nature of Rule 110 affords the inputs a simple representation. In
fact, each input can be represented as a binary integer: {0, 1, 10, 11,
110, 111, ...}, with 1's representing black squares and 0's whites.

This makes it easy for one to "iterate" over all inputs. By which I
mean, one could run Rule 110 on multiple threads with each thread
corresponding to a different input. An interation over the binary
representation of all positive integers (or actually just over the odd
integers since sets like {10, 100, 1000, ...} and {11, 110, 1100, ..},
etc. yield equivalent outputs) should thus execute Rule 110 with every
possible input, correct?

So here is my main question. If Rule 110 is universal, then it can
emmulate any computation, which means that iterating over all of its
possible inputs in this fashion should in a sense perform "every
possible" computation (I guess this would be the same as generating every binary string
and then forcing your computer to run each one as if it were a binary executable.)

But what exactly does it mean to perform "every possible" computation? When is some set,
some data, some pattern of any kind NOT a compuation? And more importantly, if one
believes that the set of data that totally describes the very system in
which we live can be reduced to an input and a set of evolution rules,
would such an iteration of Rule 110 iterate over IT? That is, does our
universe correspond precisely to some input of Rule 110?

I feel like if our universe is a "computation", then by the very definition of a universal machine Rule 110 would have to have some input that corresponds to it. So then I guess the question is: "Is our universe a computation"? How could it NOT be a computation? Would this make sense? Would a non-deterministic state machine not be capable of being emulated by a universal deterministic machine such as Rule 110 (shades of QM here...)?

On a more humorous note, I wrote a simple program a year ago that performed such a multi-threaded iteration over Rule 110, and bragged to all my friends that it "generates the sum of all existence--our universe as well as all other logical systems." Is this boast in any way accurate?

Any information is greatly appreciated! Also, does anyone have any suggestions as to good texts on discrete math/computability theory to read that would be relevant? I heard that
Sipser's "Introduction to the Theory of Computation" was good...

All the best,
--Stedman

There are two separate issues going on here.

The first is what sequences can rule 110 produce, and the second is which sequences can be produced by a computation.

It has been known for a long time in mathematical logic, the branch of recursion theory, that there are infinite sequences which cannot be produced by computations. For instance, given a Turing machine with an undecidable halting problem, there is the sequence of 0 and 1's where a 1 at position n signifies that the machine halts on the nth input.

Sequences which can be computed are called computable.

The point about 110 being universal is that it can emulate any computation. That means there is a way to translate its output to match that of any computation. But it may not be literally the same 0's and 1's.

Looking at the actual rule 110, it is easy to see that it does not produce all computable states. So the translations to other computations cannot be literal. For instance, it is impossible to produce a single black cell on a white background after any number of steps with rule 110. Such a thing could be the output of a computation which computes mod 2.

It would be of interest to understand the minimal language of rule 110 and to go from there to show its universality.

Todd, yes thank you for that very enlightening response. It definitely helped clear things up a bit. I guess the main question that I have now relates to one of the points you brought up. I is about the nature of the "translation" of one computation to another that you speak of.

For instance, say you had some output of Rule 110, which won't contain a single black cell at some number n of steps. One could "translate" every line of Rule 110 by effecting mod 2 on each of these sequences. Now I believe that mod 2 is a homomorphism (in either addition or multiplication) from the integers to {0, 1}. In this way, as you said, you now actually would have only white lines and single black squares in this "translated output". Of course, this wouldn't make Rule 110 behave like mod 2. It would just make it behave like some other weird computation I guess.

The main thing is that I'm wondering if a map like Mod 2 would be a suitable translation. What are the criteria on a function that translates the computation of Rule 110 into another computation (thus showing their equivalence)? That is, I have wondered since reading the NKS book how exactly one would show, in general, a computation to be "emmulating" another. Does a translating map have to be homomorphic or have some kind of structure preserving quality? What exactly is the structure we're trying to preserve here? If I listed all the inputs of Rule 110, and then their respective outputs after say n steps, and then said that there is some map such that, for each input and output of Rule 110, it returns the input and corresponding output of some other computation, would we have just shown equivalence?

To say that Rule 110 is emmulating another computation given some input, do we only need to show that certain changes in the input affect the output correctly, or does the whole process in which Rule 110 (or any universal machine) actually cranks out the output matter?

And what do you mean by the translation isn't "literal"? Do you simply mean that the actual two binary strings of each separate computation are not the same, or is this somekind of stronger constraint about how you could map one to the other?

Thanks again.
--Stedman