4 ms·
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.
by reader5000 9y ago
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.
- doubleunplussed 9y agoActually, 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.
- teraflop 9y agoNo, rule 30 isn't known to be Turing complete. You're probably thinking of rule 110.