FOM: Wolfram?

JoeShipman@aol.com 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 mailing list