News for hackers. Stuff that matters.

A comment on Oh My Gosh, It’s Covered in Rule 30s. Parent comment

Re:Oh My Gosh, It’s Covered in Rule 30s by reader5000 on Friday June 02, 2017 @07:17AM (#14469062)
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.
[ Parent | on HN ]
Re:Oh My Gosh, It’s Covered in Rule 30s by teraflop on Friday June 02, 2017 @11:00AM (#14470366)
No, rule 30 isn't known to be Turing complete. You're probably thinking of rule 110.
[ Parent | on HN ]
Re:Oh My Gosh, It’s Covered in Rule 30s by doubleunplussed on Friday June 02, 2017 @10:23AM (#14470091)
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.

[ Parent | on HN ]