[FOM] Universality for unbounded computations

[Todd Rowland]

>Todd Rowland wrote:
>> 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.
>
>What does "finite state machine" and "run on" mean exactly?

The finite state machine decides whether there are an odd or even number 
of 1's in the binary digits of x.  More precisely, as Mathematica code, 
Fold[Mod[#+#2,2]&, 0, IntegerDigits[x,2]] (where we start the sequence B 
at x==0). Mod[#+#2,2]& adds the state and color mod 2 to get the next 
state, and Fold performs the iteration.  At the end we read the final 
state.

There are many other ways to realize the Thue-Morse sequence in terms of 
mathematical functions that effectively speed up its computation.
http://www.wolframscience.com/nksonline/page-889c-text
http://www.wolframscience.com/nksonline/page-1092a-text

This example of a background construction is simple enough to be allowable 
in emulations, as it is barely more sophisticated in its behavior than the 
machine that makes the background zero.

One of the reasons to reconsider the definition of universality is that we 
are interested in more than the existence of a universal machine. We want 
to know which ones are universal.

The examples we face usually have no apparent connection to traditional 
mathematics (even the integers), but all are tied together through the 
primitive notion of computation.  It is a challenge to make a formal 
definition that matches intuition from a broad collection of examples, but 
it could be very useful.