>> If you could prove not that one particular "simple" system is 
>> Turing-complete, but that huge classes of simple systems are, *that* 
>> would be an interesting result.
> 
> Um, we already have that. It's called "A Turing Machine." :-)  I mean, 
> that was the whole point of defining Turing machines, then coding a 
> universal turing machine, then proving that all kinds of multi-tape 
> multi-this multi-that all reduce down to the same single-tape 
> single-program UTM-capable machine.

Sure. But a UTM is carefully *designed* to be universal. Wolfram asserts 
that many kinds of things "just happen to be" universal. Now if he had 
offered a proof rather than an assertion (i.e., a theorum stating 
exactly which kinds of things are Turing-complete), that might have been 
interesting. As it is, he just goes through a collection of CAs and 
demonstrates that just one of them is definitely Turing-complete.

>> (Presumably such a result would include deciding exactly when a simple 
>> system is or isn't Turing-complete.)
> 
> We already have that too.

Really? So you can tell me exactly which CAs are or aren't 
Turing-complete then?

(Actually, I have a sinking feeling the general question might be 
undecidable, but anyway...)

> I think he was asserting that science should look at computational 
> systems as the basis of science, rather than (say) the closed form 
> fomulas of how the world works that science uses now. However, since he 
> didn't do what you're talking about, namely being able to point at the 
> attributes of a system and determine how computationally complex it is, 
> he failed at that task.

Yeah, even after reading NKS, I'm still not *exactly* sure what he was 
getting at. Maybe he isn't either...

Post a reply to this message