# [FOM] Universality for unbounded computations

Todd Rowland rowland at wolfram.com
Tue Nov 20 18:01:37 EST 2007

```>Todd Rowland wrote:
>> B={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.
```