FOM: Wolfram?

Robert M. Solovay solovay at
Thu Jun 6 03:46:21 EDT 2002

The result on TM's is deduced from the result on rule 110. [I haven't
thought through all the details on either proof.]

For what I know about the prior state of the art see my immediately prior
posting. I didn't know about the Conway result till I read Tennant's

On Wed, 5 Jun 2002 JoeShipman at wrote:

> 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