Kevin Wampler wrote:
> I see.  I had asked partially since if rule 30 isn't Turing complete it 
> provides a nice counterexample to the "it's a CA with non-trivial 
> behavior so it's probably Turing complete" viewpoint (which you were 
> also arguing against).

Fair enough.

> I swear I'd read a nice blog post about this at some point but I cannot 
> seem to find it again.  As far as I remember the main gist was "you have 
> to be careful with the initialization since it's possible to combine two 
> non-Turing complete components and get a Turing complete result"

Yes, that was my concern. In particular, a TM with an infinite pattern on 
the initial tape isn't obviously as simple as a similar TM with a finite 
pattern on the initial tape. It's not clear to me whether the same is true 
of a CA that does an infinite computation at every step to start with.

How much of the human's understanding of what the pattern means is really 
involved? How much of the infinite pattern being unimportant is just the 
human's understanding that "oh, that's just the clock pulse". How much of 
that infinite complexity is dismissed only because of "understanding" which 
is specifically denied to the formalism?

For example, a TM with any finite initial pattern on the tape can be 
trivially turned into a finite TM with a completely blank tape to start, 
simply by prepending a series of instructions to write the appropriate 
pattern to the tape. This isn't true of an infinite pattern, even if it's 
repetitive. It *is* true of a CA, but you'd have to change the rule of the 
CA in the middle of evaluation, and there's no obvious way in the formalism 
to do that, since CAs don't keep any sort of state (corresponding to the 
head position and state number) outside the actual "tape." I just never got 
into the whole deal enough to know the answers to such questions, and I'm 
not sure it even makes a difference. It would be interesting to know whether 
there's a proof or a disproof of whether an infinite repetitive initial tape 
for a TM makes a difference in what you can compute.

> Ahh, I *think* this is what I was remembering:
> http://forum.wolframscience.com/showthread.php?s=&threadid=1472

That seems to be talking about TMs, not CAs. Two different beasts when 
talking about infinite tapes, since a CA does infinite computation at every 
step, while a TM does not.  I'm also almost certain that the Rule 110 
universal machine starts with a repeating pattern (other than the "program") 
so would fall under the "computational properties of linear cellular 
automata on configurations that differ from spatially periodic ones in only 
finitely many places" rule.  Since the author seems to claim (in the 
abstract) that "is the same on these configurations as on the space of 
finite configurations" then it would seem they think they proved that Rule 
110 is indeed turing complete in spite of needing infinite initialization.

The 2,3 TM is interesting only in that it's tiny. But if you're going to 
argue that simple systems can make really complex results, the fact that a 
2,3 TM can do so doesn't seem that much more surprising than a 3,5 TM for 
example.  Especially since all the TMs require sophisticated interpretation 
of their results to support any of these proofs - you already have all kinds 
of encoding issues outside the TM to interpret what's on the tape to figure 
out the isomorphisms with other machines.

I think Wolfram's wanking with his smallest-TM contests in a way that 
doesn't really add anything to his basic premise.

Interesting links tho. I'll have to read them in my copious spare time. ;-)

> As near as I can tell, maybe it's best to view rule 110 as "weakly 
> universal" since the universality proof requires an infinite (and AFAIK 
> non-repetitive) initialization?  That seems to convey the idea that it 
> has some interesting properties with respect to Turing completeness, but 
> that it's not quite the full-blown form of Turing completeness you'd 
> normally expect.

Sure. I just didn't find it interesting, given there *are* CAs that are 
known to be (and easily provable to be) turing complete. OK, so now there's 
a linear one. So?  Only Wolfram crowing about how trivial it is made it 
interesting, and I didn't consider it to be particularly trivial if it 
needed an infinite amount of initialization. The Conway CAs that are indeed 
turing complete have initial states that are scaled relative to the size of 
the turing machine they're emulating, so the fact that they're "big" in some 
absolute measure isn't all that interesting. They're still only 4 rules, at 
absolute worst a 512-range CA instead of a 256-range (or was Wolfram's a 
128-range?).

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

Post a reply to this message