Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Suppose I ask the same question about rule 250 instead of rule 30. Do I have to calculate a half million cell colors to get the answer? Here is my answer and my work.
The center column at step 1 is 1, at step 2 is 0, then alternates. Therefore a formula exists for the center cell at step n. It is Center250[n] = n mod 2. 1000 is even, i.e. 1000 mod 2 is 0. (I can tell very easily because its last base 10 digit is 0 and 10 is divisible by 2). So the answer is 0101010101. That is all my work. Didn't take a half million calculations, did it?
I could have calculated every step, and I'd get the right answer. The existence of a slow way to get the right answer does not suffice to make the problem complex. Since a fast way also exists, the problem is not complex. With rule 30, it is not the existence of the slow way that makes it complex. It is the non-existence of a fast way.
With addition, I can add 567 and 345 together with this slow algorithm -
567 minus 1 is 566. 345 plus 1 is 346. Continue until the first register reaches zero. Then return the value in the second register. This takes twice as many steps as the value entered in the first register. Does this make it complex?
Well, here is another way instead. 7 plus 6 is 13. Enter 3, carry 1. 6 plus 4 plus 1 is 11. Enter 1, carry 1. 5 plus 3 plus 1 is 9. Enter 9. Return 913. But ah, you will say, using facts like 7 plus 6 is 13 includes a subcalculation. Fine. I still reduce the number of operations to around 40, down from 1134. Addition is normally well behaved.
Not all seemingly simple mathematical operations are, though. The 3n+1 problem is an example of one that isn't. Factoring large integers can be hard enough to form a basis of practical encryption schemes. Chapter 4 is full of such examples.
Complexity is a formal phenomenon, not an observational one or some artifact of our deficient knowledge of something. It is true there can be cases at the margins, where something appears complex at first, but after hard analysis work we manage to find a "crack" (figuring out what is going on, in some simplified way) that produces a general formula.
Or we may see complexity in one scheme or representation, while we can find simplicity in another. (For example, the Golden Ratio in decimal expansion is pretty complicated, but in a continued fraction expansion it is 1,1,1,1,1,1...). Any choice of representation may present a few problems as simple.
But others will always remain complex. And scads of formal problems with simple statements but no simple solution will arise for which there is no apparent "crack". Even e.g. in integer Diophantine equations in number theory, undecidability will crop up in practice, and can be proved to be ineradicable in theory.
What this repeated phenomenon is telling us is simply that formal complexity is real, does not depend on point of view or basis of representation, and does not require elaborately specified problems or complex rules or constraints, nor does it depend on any underlying stochastic externals or "inside-outside gap", observational limitations. Instead, the onset of complexity is "early and often", purely formally.
I hope this is interesting.
Report this post to a moderator | IP: Logged