Kevin Wampler wrote:
> Are you *sure* that rule 30 is the right CA here?  

No, actually. I thought that sounded wrong, and 110 sounds much more like 
what I remember, but I wasn't about to dig out the 30 pound tome to check. :-)

> and there was a later proof by Matthew Cook establishing this provided 
> proper tape initialization and processing is done.

Right. There's a proper proof *providing* the initialization of the first 
state is done. That's what I'm not sure is valid. I'm not saying it isn't, 
but I'm not convinced it is. AFAIR, the definition of a turing machine 
requires anything past a finite initial portion of the tape to be all 
initialized to the same symbol.

Sorry for any confusion.

-- 
Darren New, San Diego CA, USA (PST)
   Forget "focus follows mouse." When do
   I get "focus follows gaze"?

Post a reply to this message