FOM: Wolfram?

[Robert M. Solovay]

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
posting.

On Wed, 5 Jun 2002 JoeShipman at aol.com 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
>