Darren New wrote:
> 
> That seems to be talking about TMs, not CAs.

I can't believe I missed that.  Once I read enough to see that the was 
the link I remembered I clearly didn't read enough extra to verify that 
it was actually talking about a CA!  That'll learn me.  The overall gist 
still seems relevant though.

> 
> Sure. I just didn't find it interesting, given there *are* CAs that are 
> known to be (and easily provable to be) turing complete.

Personally I find it interesting, but interesting in a "ok, that's sort 
of neat" way rather than as providing any sort of fundamental insight. 
I basically agree with your assessment otherwise though.

Post a reply to this message

Kevin Wampler wrote:
>> Sure. I just didn't find it interesting, given there *are* CAs that 
>> are known to be (and easily provable to be) turing complete.
> 
> Personally I find it interesting, but interesting in a "ok, that's sort 
> of neat" way rather than as providing any sort of fundamental insight. I 
> basically agree with your assessment otherwise though.

Well, yeah. I mean, it was interesting that something as simple as a tiny 
linear CA could be made turing complete without actually obviously emulating 
a machine. I didn't find it "fundamentally" interesting. Certainly not 
something I'd call a "new science" for example. I.e., I think I'm agreeing 
with you.

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

Post a reply to this message

Kevin Wampler wrote:

> Are you *sure* that rule 30 is the right CA here?
> 
> It seems more likely that the proof you're talking about was done for 
> rule 110, which is the CA that Wolfram proposes to be Turing complete, 
> and there was a later proof by Matthew Cook establishing this provided 
> proper tape initialization and processing is done.

Hmm, maybe you're right. I don't memorise these code numbers...

Post a reply to this message

WIN!

Post a reply to this message

>>> Sure. I just didn't find it interesting, given there *are* CAs that 
>>> are known to be (and easily provable to be) turing complete.
>>
>> Personally I find it interesting, but interesting in a "ok, that's 
>> sort of neat" way rather than as providing any sort of fundamental 
>> insight. I basically agree with your assessment otherwise though.
> 
> Well, yeah. I mean, it was interesting that something as simple as a 
> tiny linear CA could be made turing complete without actually obviously 
> emulating a machine. I didn't find it "fundamentally" interesting. 
> Certainly not something I'd call a "new science" for example.

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.

(Presumably such a result would include deciding exactly when a simple 
system is or isn't Turing-complete.)

I still wouldn't describe it as a "new kind of science". Indeed, from 
what I can gather, NKS isn't some sweeping new paradigm. It's just a new 
and unusual way of looking at and thinking about things. That's not to 
say there aren't interesting things to be learned from this point of 
view, but it hardly rocked my world.

Fractal geometry already tells us that simple rules can generate complex 
behaviour. Chaos theory already tells us that deterministic, simple 
systems can still be highly unpredictable. NKS doesn't seem to add very 
much. There's a few small, specific things which are interesting, but 
it's not nearly as radical as people are saying.

But then again, isn't this the same Mr Wolfram who claims that 
Mathematica fundamentally transforms the way computer mathematics 
happens? Or that Wolfram Alpha is going to revolutionise the human race?

Sure, Mathematica is a great piece of software, but I guess we should 
take anything Mr Wolfram says with a pinch of salt...

Post a reply to this message

Darren New wrote:

> Right. There's a proper proof *providing* the initialization of the 
> first state is done. That's what I'm not sure is valid. 

And I still think it ought to be possible to do this without all that 
initialisation. I just haven't proved it yet. ;-)

(Don't hold your breath for that...)

Post a reply to this message

Invisible wrote:
> 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.

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

We already have that too.

> I still wouldn't describe it as a "new kind of science". Indeed, from 
> what I can gather, NKS isn't some sweeping new paradigm. It's just a new 
> and unusual way of looking at and thinking about things. That's not to 
> say there aren't interesting things to be learned from this point of 
> view, but it hardly rocked my world.

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

> Fractal geometry already tells us that simple rules can generate complex 
> behaviour. Chaos theory already tells us that deterministic, simple 
> systems can still be highly unpredictable. NKS doesn't seem to add very 
> much. There's a few small, specific things which are interesting, but 
> it's not nearly as radical as people are saying.

I don't think anyone but Wolfram are saying it's radical. :-)

> But then again, isn't this the same Mr Wolfram who claims that 
> Mathematica fundamentally transforms the way computer mathematics 
> happens? Or that Wolfram Alpha is going to revolutionise the human race?
> 
> Sure, Mathematica is a great piece of software, but I guess we should 
> take anything Mr Wolfram says with a pinch of salt...

Yep.

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

Post a reply to this message

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

Invisible wrote:
> Sure. But a UTM is carefully *designed* to be universal. Wolfram asserts 
> that many kinds of things "just happen to be" universal.

No, he asserts that many things just happen to be capable of being designed 
to be universal. A UTM is just the kind of TM that's universal. Rule 110 is 
only universal if you initialize it with the appropriate program in the 
cells to start with.

> demonstrates that just one of them is definitely Turing-complete.

It's turing complete only when running on the right program, initialized 
with the right set of data on the cells. 110 itself doesn't calculate 
anything except what rule 110 says to calculate.

>>> (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?

Sure. The ones that can emulate arbitrary turing machines are turing 
complete. :-)  Oh, you mean, can I tell that just by looking without doing 
any mathematical proofs? No. :-)

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

He's getting at "Hey! Hey, look at me! I should be famous!"

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

Post a reply to this message

>> Sure. But a UTM is carefully *designed* to be universal. Wolfram 
>> asserts that many kinds of things "just happen to be" universal.
> 
> No, he asserts that many things just happen to be capable of being 
> designed to be universal. A UTM is just the kind of TM that's universal. 
> Rule 110 is only universal if you initialize it with the appropriate 
> program in the cells to start with.

Like I said, I think you can set up the CA more easily than the proof 
demonstrates. But whatever...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message