[FOM] Smallest universal machine

Vaughan Pratt pratt at cs.stanford.edu
Tue Oct 30 03:35:26 EDT 2007

Hector Zenil wrote:
>One could fairly argue that two non-universal coupled automata can reach
 >universality, but it would require the couple to interact at every step,

Thank you, this nicely boils the fallacy down from 55 pages to two 
lines.  Merely providing an initial condition saying how long to run is 
sufficient to turn a nonuniversal machine such as an LBA into a 
universal one, without any further interaction.

Vaughan Pratt

More information about the FOM mailing list