Wolfram Rule 30 Prizes

Post by lacker » Thu, Oct 03, 2019, 6:09 AM UTC

mietek wrote: post #19

lacker wrote: post #11

It is pretty hard in general to prove that calculating things takes at least O(n) time, so I wouldn't expect that one to be solved any time soon. Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone fi…

> Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. Have you seen the Miller-Fredkin paper on circular motion of strings in cellular automata? https://arxiv.org/abs/1206.2060

I haven't seen that, but the fact that you posted this interesting link makes me glad I commented! Will check it out

Post by AlEinstein » Thu, Oct 03, 2019, 12:15 PM UTC

anderskaseorg wrote: post #45

Computing the nth cell clearly takes at least 1 time unit, and by the definition of O(), we have 1 = O(n). I’ll be claiming my $10,000 now. (More seriously, don’t confuse O() with Ω() and Θ(), folks: https://en.wikipedia.org/wiki/Big_O_notation. )

Would you mind providing a little more detail of your reasoning?

For example, say that someone shows that the most efficient algorithm for computing the value (0 or 1) of the central column of the nth row of rule 30 starting with a single 1 cell (i.e., the system under consideration for the prize) takes time n^2. Wouldn’t one then say that the complexity of the calculation is O(n^2)? One couldn’t say that it’s O(n), surely?

Re: Wolfram Rule 30 Prizes

Re: Wolfram Rule 30 Prizes