On 1/4/2011 12:56 PM, Darren New wrote:
>
> Given that a CA does an infinite amount of computation each step, I just
> don't know if that's problematic or not. Naturally Wolfram says it
> isn't, but I haven't heard it addressed anywhere, and I've looked.
>

Right after the rule 110 UTM result was announced I read something 
talking about exactly your argument: 
http://cs.nyu.edu/pipermail/fom/2007-October/012156.html (response from 
Tod Rowland here 
http://forum.wolframscience.com/showthread.php?s=&threadid=1472)

I haven't read the proof, so I can't comment on it with any actual 
knowledge, but this is the internet so I'll go ahead and say that my 
impression is that the definition of "smallest universal machine" wasn't 
defined precisely enough in the first place, and it seems, not 
surprisingly, that you can "abuse" the initialization of the cells in a 
CA.  How one measures the "complexity" of such a machine seems to be a 
matter of social convention more than anything else.  I'd personally be 
inclined not to allow such initializations, but clearly Wolfram is of a 
different mind.

Post a reply to this message