4 ms·
Rule 110 is so simple that practically everything can represent its rules. You don't need to be Turing complete to do it. Indeed, the rules are even representab
by Grue3 11y ago
Rule 110 is so simple that practically everything can represent its rules. You don't need to be Turing complete to do it. Indeed, the rules are even representable in Presburger arithmetic, which, unlike Peano arithmetic, is decidable! You can deduce formulas for every single step of the process, just like with CSS! But I'm sure we can all agree that this is not Turing completeness, otherwise the term itself becomes a farce.
- Jtsummers 11y agoRule 110 is Turing complete. Therefore anything which can implement/simulate it is also Turing complete. The same is true of any other model of a Turing machine. If your host computer can simulate a Turing complete machine then the host is also Turing complete.
- gwern 11y ago> You can deduce formulas for every single step of the process, just like with CSS! You can deduce the formulas, but can you make the formulas self-deducing when driven only by a mechanical clock like a steady mouse-click? Or will it require constant adjustment and intervention by the operator? > But I'm sure we can all agree that this is not Turing completeness I'm not sure we can. TC can be tricky. That's why people try to give constructions rather than just claim something or other is TC.