FOM: Wolfram? JoeShipman at
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 mailing list