[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