[FOM] Universality for unbounded computations

[Todd Rowland]

A definition for universality needs to take into account how the term will 
be used, and what the examples are. Because of Wolfram's Principle of 
Computational Equivalence (PCE), we can expect many new examples besides 
those already known. There are ECA 110, the Wolfram 2,3 machine which are 
known to emulate any other unbounded computation. Moreover, part of the 
PCE says that there will be many systems, in the form of scientific and 
practical applications, that will be shown to be universal.  It is 
important to know whether something is universal, and so we need a 
definition which can be used in practice.

In the traditional framework, when the computations of a deterministic 
system X are interpreted by the halting of X, the computations of X can be 
emulated by a Turing machine with halting states. In contrast, for 
unbounded computations there is nothing analogous to halting. 
Intuitively, computations are being performed, and any attempt to augment 
the system by adding halting conditions is unnatural (even if it were 
meaningful).

The traditional definition of universality is useful for its textbook 
uses, e.g., a concrete defintion is needed to establish the existence of 
universal machines.  It captures well the intuition of universal 
computation for finite computations.  But it does not match the intuition 
behind emulating unbounded machines.

The main point which has been under discussion recently is what initial 
conditions should be allowed in an emulation. It is fitting to mention the 
Thue-Morse sequence as an example of an initial condition background that 
is simple enough to be allowed, while being non-repetitive.

One way to construct this sequence is recursively.

B[0]={0};
B[n_] = B[n-1] + F[B[n-1]]
where F[s] == 1-s == BitNot[s] == ReplaceAll[s, {0->1, 1->0}] (replace all 
0's with 1's and vice versa)

Not only does this have very simple behavior, but it is also reducible. 
If one wants to know the value at position x, there is a finite state 
machine that can be run on the binary digits of x.  It is also worth 
mentioning that the simplicity of the program is not a very good condition 
for a definition. As Wolfram has shown, very simple rules can be 
universal, but the simplicity of the behavior of a rule is a very good 
indication of its universality status.  It should not be a question of how 
tedious the encoding is or how much storage is needed, especially if the 
encoding is reducible.

As for the formalization of the PCE, as Kovas Boguta says, it is most 
useful as a scientific principle.  That does not rule out that there is a 
formal theorem that can show its limitations and applicability.

On a somewhat different topic, concerning the status of Alex Smith's 
Complex Systems paper, he is still writing it up.

Anyone can let me know if they are interested in being a referee and 
giving a timely report.


Todd Rowland

Managing Editor
Complex Systems
rowland at wolfram.com