Hacker News Reader

>Maybe they were going for the randomness that rule 30 provides (you can build a PRNG from it) but Game of Life doesn't?

You can build a PRNG in Game of Life, since you can build a Turing Machine.

http://rendell-attic.org/gol/tm.htm

View on HN

Isn't rule 30 also Turing complete? Therefore GoL and rule 30 can both emulate the other, modulo possible exponential blowups in time/space requirements.

No, rule 30 isn't known to be Turing complete. You're probably thinking of rule 110.

Actually, according to the extended Church-Turing thesis, all Turing complete systems can emulate each other with at most polynomial overhead, so no exponential blow-ups.

The only possible exception we know of is quantum computers.

Reply on news.ycombinator.com