Kevin Wampler wrote:
> 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)

Cool. Altho I think we're talking more about the Cawley post on that page. I 
understand the abstract, but I'm not sure what the implications are of 
having CAs whose behavior is decidable on all finite initializations and 
undecidable on an infinite repetative initialization.

> How one measures the "complexity" of such a machine seems to be a 
> matter of social convention more than anything else.  

Well, I think it's more than one needs to define what is meant.

If you can prove that an infinite repetitive initialization doesn't ever 
give you more power than a constant initialization (i.e., in a similar way 
as you can prove that extra tapes don't help a TM be more universal), then 
I'd accept the 110 proof. But I didn't know if the Cawley paper makes that 
implication or not.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message