[Predicting future states of rules... #30?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

Predicting future states of rules... #30?
(Click here to view the original thread with full colors/images)

Posted by: Val Smith

Mostly I have been experimenting with rules 60 and 90 and occasionally other things that I can do with my esoteric equipment.

I do believe that Rule 60 is predictable indefinitely based on initial condition and by future iteration number and cell position. Each marked cell in the initial state generates a sierpinski triangle described by the bitwise AND function of it's coordinates, and these are all XORed together for any particular cell at any particular "time" (this method replaces the time with an unchanging second coordinate).

Iterations work by XORing neighboring cells,
which is not predictive.

Some rules obviously are binary counters, such as 60, and another one that is even more compact, with the diagonal lines representing carries.

Perhaps someone recalls the logical function of Rule 30, before I figure it out again, and try to make a "predictive" translation of it.

I propose a theory that there is a function,
state=f(rule,initialstate,x,y) that gives the
state of any cell in all 256 rules instantly,
with no iteration or recursion especially
in the case of the initial state having one dot, and that it's a bitwise boolean logic function.

I propose another theory that Rule 90 can predict not only the oddness of the binomial coefficients (anything in rule 90 is predictable) but also that the binomial coefficient can be entirely generated for all it's bits using the row and column number of the desired coefficient in Pascal's triangle, which is most often generated like a CA using addition as a rule. But the other bits of the coefficients also form Rule-90-like patterns. I'm currently pondering the Pascal's triangle as the powers of 11 in base 11 without carry, that is, each digit being a often high unary value.

(I am trying to calculate binomial coefficients instantly without factorials, but my main point is that it appears to me that all CA are in some sort of intangible but instantly readable 2D-coordinate logical space.)

I've mentioned before...
look at a graph of (X AND Y)=0

Start at a googol if you please,
and imagine how much "time" you saved.

Posted by: Jason Cawley

There is no such function, in general, that can be implemented using appreciably fewer logical operations than just running the rule explicitly through every step. Yes you can find one for additive rules like rule 90 - we say therefore that those are reducible. But reducibility in this sense is a special property of the simpler rules, not a general one that follows in any way from simply being the result of deterministic rules. There is no formula that shortcuts the evolution of rule 30. It is not a matter of no one having had the idea or having looked - it simply isn't there.

See page 618 and the surrounding sections, which show the minimal boolean expressions for a few steps of various ECA rules. For 6 steps, the minimal expression for rule 30 involves 261 terms, when put into the smallest possible disjunctive normal form. Wolfram addresses the entire question directly on pages 615 through 620. See also the corresponding section of the notes, from 1094 to 1098. The intuition that there must be simple formulas for everything is simply incorrect. That intuition stems from a habitual restriction to overly simply cases in the previous history of math, and not from any formal necessity.

We call systems whose behavior cannot be compressed into a simple formula much shorter than the system's own evolution, irreducibly complex. From the existence of irreducible complexity and the definition of universality, it is clear the universal rules will sometimes exhibit such irreducible complexity. As Wolfram describes it, sometimes the computations being performed within the system are as sophisticated as any we do when analysing them, and we do not outrun them. Our best way of predicting what they will do is to simulate them directly, walking through their evolution.

Systems or rules that are, on the contrary, readily reducible, can be thought of as wasting computational effort, and our analysis of them can effectively find lots of cancelling or simplifying substitution. We can thereby compress a bunch of their steps into a few smarter ones. But this is a special property of the simpler rules, and does not generalize to the genuinely complex behaviors seen in most class 3 and class 4 systems.

Posted by: Val Smith

Ok, but on the second question, does anyone else see reducible patterns on the higher bits of Pascal's triangle numbers similar to rule 90?

Most applets to play with that sort of thing tend to show mod, and mod 2 just happens to work like AND 1. (Generates rule 90 from odd Pascal's triangle numbers)

I need to calculate nCr fast on realtime data, and using large factorials is very inconvenient for the very long rows in the triangle.
(Such as row 1000 or 1000000.)

Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings