[FOM] Universality for unbounded computations

[Vaughan Pratt]

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?   If only 
one tape is involved and the machine does not write (otherwise you would 
  presumably have said "Turing machine") I can't think of a useful 
meaning for a non-regular set such as the Thue-Morse sequence.

> As Wolfram has shown, very simple rules can be universal

There seems to be a double standard here: machines with very simple 
rules are being judged universal (by stretching the allowed initial 
conditions to nonregular sets) yet such allegedly very simple initial 
conditions are being judged nonuniversal (in the sense of not themselves 
contributing nontrivially to the universality of the resulting machine). 
  The passage from nonuniversality to universality can be accomplished 
merely by marking a single cell on an otherwise blank bi-infinite tape 
(tape Z in my PZT * IW example) when there are two independent read-only 
heads (case I).   The set of black cells in tape Z is not only regular 
but finite!  Allowing nonregular reference libraries such as the tape T 
of Triangular numbers or the Thue-Morse sequence makes the resulting 
concept of universality meaningless.

Vaughan Pratt