Note on Wolfram's 'principle of computational equivalence'

Stephen Wolfram has discussed his "principle of computational equivalence" extensively in his book A New Kind of Science and elsewhere. Herewith is this writer's understanding of the reasoning behind the PCE:

1. At least one of Wolfram's cellular automata is known to be Turing complete. That is, given the proper input string, such a system can emulate an arbitrary Turing machine. Hence, such a system emulates a universal Turing machine and is called "universal."

2. One very simple algorithm is Wolfram's CA Rule 110, which Matthew Cook has proved to be Turing complete. Wolfram also asserts that another simple cellular automaton algorithm has been shown to be universal or Turing complete.

3. In general, there is no means of checking to see whether an arbitrary algorithm is Turing complete. This follows from Turing's proof that there is no general way to see whether a Turing machine will halt.

4. Hence, it can be argued that very simple algorithms are quite likely to be Turing complete, but because there is no way to determine this in general, the position taken isn't really a conjecture. Only checking one particular case after another would give any indication of the probability that a simple algorithm is universal.

5. Wolfram's principle of computational equivalence appears to reduce to the intuition that the probability is reasonable -- thinking in terms of geochrons -- that simple algorithms yield high information outputs.

Herewith the writer's comments concerning this principle:

1. Universality of a system does not imply that high information outputs are common (recalling that a bona fide Turing computation's tape halts at a finite number of steps). The normal distribution would seem to cover the situation here. One universal system is some algorithm (perhaps a Turing machine) which produces the function f(n) = n+1. We may regard this as universal in the sense that it prints out every Turing machine description number, which could then, notionally, be executed as a subroutine. Nevertheless, as n approaches infinity, the probability of happening on a description number goes to 0. It may be possible to get better efficiency, but even if one does so, many description numbers are for machines that get stuck or do low information outputs.

2. The notion that two systems in nature might both be universal, or "computationally equivalent," must be balanced against the point that no natural system can be in fact universal, being limited by energy resources and the entropy of the systems. So it is conceptually possible to have two identical systems, one of which has computation power A, based on energy resource x, and the other of which has computation power B, based on energy resource y. Just think of two clone mainframes, one of which must make do with half the electrical power of the other. The point here is that "computational equivalence" may turn out not to be terribly meaningful in nature. The probability of a high information output may be mildly improved if high computation power is fairly common in nature, but it is not easy to see that such outputs would be rather common.

A mathematician friend commented:

I'd only add that we have very reasonable ideas about "most numbers," but these intuitions depend crucially on ordering of an infinite set.  For example, if I say, "Most integers are not divisible by 100", you would probably agree that is a reasonable statement.  But in fact it's meaningless.  For every number you show me that's not divisible by 100, I'll show you 10 numbers that are divisible by 100.  I can write an algorithm for a random number generator that yields a lot more numbers that are divisible by 100 than otherwise.  "But," you protest, "not every integer output is equally likely under your random number generator."  And I'd have to agree, but I'd add that the same is true for any random number generator.  They are all infinitely biased in favor of "small" numbers (where "small" may have a different meaning for each random number generator).

Given an ordering of the integers, it is possible to make sense of statements about the probability of a random integer being thus-and-so.  And given an ordering of the cellular automata, it's possible to make sense of the statement that "a large fraction of cellular automata are Turing complete."

My reply:

There are 256 cellular automata in NKS. The most obvious way to order each of these is by input bit string, which expresses an integer. That is, the rule operates on a bit-string stacked in a pyramid of m rows. It is my thought that one would have to churn an awfully long time before hitting on a "universal." Matthew Cook's proof of the universalism of CA110 is a proof of principle, and gives no specific case.

As far as I know, there exist few strong clues that could be used to improve the probability that a specific CA is universal. Wolfram argues that those automata that show a pseudorandom string against a background "ether" can be expected to show universality (if one only knew the correct input string). However, let us remember that it is routine for functions to approach chaos via initial values yielding periodic outputs.

So one might need to prove that a set of CA members can only yield periodic outputs before proceeding to assess probabilities of universalism.

Perhaps there is a relatively efficient means of forming CA input values that imply high probability of universalism, but I am unaware of it.

Another thought: Suppose we have the set of successive integers in the interval [1,10]. Then the probability that a randomly chosen set member is even is 1/2. However, if we want to talk about an infinite set of integers, in line with my friend's point, the probability of a randomly selected number being even is meaningless (or, actually, 0, unless we invoke the axiom of choice). Suppose we order the set of natural numbers thus: {1,3,5,7,9,2,11,13,15,17,4...}. So we see that the probability of a specific property depends not only on the ordering, but on an agreement that an observation can only take place for a finite subset.

As my friend points out, perhaps the probability of hitting on a description number doesn't go to 0 with infinity; it depends on the ordering. But, we have not encountered a clever ordering and Wolfram has not presented one.