JoeShipman at aol.com
Wed Jun 5 17:14:37 EDT 2002
I have read that Wolfram's new book also contains a proof (originally due to Matthew Cook) that a certain 1-dimensional cellular automaton with 2 cell states and a 3-cell neighborhood (there are only 256 of these, and this one is "Rule 110") is computation-universal.
I don't know about this 2-state 5-symbol periodic-background UTM -- what is the record for (states*symbols) in a UTM with ordinary finite background?
-- Joe Shipman
More information about the FOM