Message Boards Message Boards

0
|
2120 Views
|
0 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Is Rule 30 Turing complete?

Posted 3 years ago

I know this is an open question, but I wanted to run down a few arguments on it. Rule 30 is a well-known ECA. Wikipedia has a fine introduction to that topic if you're unfamiliar. Here's a 60-second version of the mechanism:

  1. Let $s_0 \leftarrow 1$.
  2. Let $s_{i+1} \leftarrow s_{i}00$, but altered by stepping through the bits left to right and flipping all of them except for those followed by more than one $0$. (The last two bits can wrap around to the beginning for this purpose.)
  3. Repeat step $2$ ad infinitum.

Where not otherwise specified, I'll be referring to the Wolfram standard configuration of a single "seed" cell with a value of $1$ set against an infinite $0$ background as the initial row. For the purposes of this question, I'm also asserting that a few as-yet-unproven properties of Rule 30, which are widely believed to be almost certainly true, are true, in particular that every finite binary sequence on a row or column appears somewhere within the light cone generated by the initial seed cell.

rule 30, first 50 rows, eye candy

There are several defining and/or typical properties of TC systems that seem to be in a gray area w.r.t Rule 30. (Skip down to Bi-simulation for the part I find the most vexing.)

Limits on computation as pure function mapping?

First, I strongly believe that every total computable function will be computed as the structure unfurls. In particular, there will be infinitely many row segments which could have $k$ bits set as the input to a function, where each of the $2^{2^k}$ distinct mappings from $k$ input bits to a single output bit will eventually appear in infinitely many cells down the road, in every column.

It's important to note that the computing taking place to arrive at these answers is legitimate, and would give the correct result if we went in manually and altered the inputs, or found another copy of the algorithm with different "hardcoded" inputs resulting from the single $1$ seed cell. The computing will almost certainly be extremely slow and scattered, but each individual logical step required will actually take place, so there's no trickery in that sense.

That said, my understanding is that what's going on is the enumeration of increasingly complex boolean circuits, or whatever analogous interpretation you prefer. This means that every complete computation it can do was guaranteed to terminate from the outset, which would seem disqualifying. You could maybe make an argument that in one sense, given a sufficiently hard problem, it will continue to try more and more complex algorithms and if one does solve it, it will eventually compute it; if none exists, it never will. In that narrow sense, the behavior seems the same as a TC system to me.

Lack of organization

Also problematic is the apparent utter unpredictability of the system. While we may be able to prove that all of these functions must be represented and computed somewhere, it seems unlikely that there's ever going to be any kind of map or organized order which would make these computations effectively accessible. For now, the only way (that I know of) to find a set of input cells and output cell that exhibit your goal behavior is to mostly brute force your way through all the computations in the whole structure, keeping an eye out for what you want.

And again, it's unclear to me how disqualifying this is or not. A well-behaved TC system should have translator programs so it can bi-simulate other TC systems, but such a thing almost certainly can't exist for Rule 30; or to be more precise, it could exist, but it would be doing an amount of work (largely bookkeeping, redundant, unrelated) that most likely dwarfs whatever would be involved for the target computation itself, and I'm not sure that counts. But the structure is lousy with computational tidbits, and as proof of concept, it was trivial to find an early spot that functions as a half-adder.

An emergent virtual machine?

Okay, this one is probably more of a stretch, but since digital computers are essentially big finite state machines (or bounded linear automatons? whatever it is), and they fundamentally run on basic logic, such structures should also exist somewhere in the Rule 30 structure, a virtual computer perfectly set up to tackle whatever problem we're interested in. Conceivably there could even be a mechanism wherein memory is not limited and the process continues farther down as needed. Note that the Rule 30 structure is constantly expanding, increasing capacity for computation and with it some form of memory, and this unbounded expansion is one sense in which it seems more Turing-Machine-like after all.

Bi-simulation

This is maybe the same point as the last, but it deserves emphasis. The gold standard for proving something Turing complete is the ability for a known TC system and your system to be able to emulate each other perfectly. Any operation that one system can carry out, the other must be able to, even if it seems like a very different computational architecture.

Clearly any TC system can emulate Rule 30 trivially. The question is whether Rule 30 can emulate, say, a Universal Turing Machine. If we were handed the specs for a UTM, we could not (for now) sit down and run it through a simple translator and run it in Rule 30. However, if every computation really is carried out, then if you run Rule 30 long enough, it is guaranteed to precisely mimic every last one of the UTM's states and instructions. Even if it involves an open-ended loop, there will be further computation downstream in Rule 30 that behaves as though it used such a loop.

So if we know the simulation is there, perhaps scattered invisibly in the noise, but functional and real nonetheless, does that count or not? Particularly because we really could build a translator program, in theory, even if it did use brute force and would be slower than sin. That seems like a mark in favor of TC-ness for Rule 30.

Summing up

I am interested in opinions on which of these points are persuasive or not, and overall, whether or not a case could be made for Rule 30 being Turing complete. If someone can point out where one or more required criteria for TC-ness absolutely are or are not met, or if someone can point me towards resources substantially addressing this question, that'd be great.

POSTED BY: Trevor Cappallo
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract