4 ms·

I'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally tu

I'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally turing complete including Magic The Gathering. [1] http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html http://beza1e1.tuxen.de/articles/accidentally_turing_complet...

Dylan16807 8y ago
I've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic. When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete. It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine, but it's also not doing much at all by itself. A Turing machine is simple, and half a Turing machine is really simple. It's missing the point of "accidental Turing completeness" if it can't iterate to an actual result.
- IggleSniggle 8y ago
  Off the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.
  - svachalek 8y ago
    In CSS itself, I don't know of a way to feed one result back into an earlier one and thus create a loop. If you're talking about JavaScript, it is and was intended to be Turing complete. Edit: Just saw the HTML/CSS3 example on the page. Mind blown.
gwern 8y ago
I have a more up-to-date list at https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete
- Y_Y 8y ago
  I've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.
- eindiran 8y ago
  Why do you consider it surprising that Peano Arithmetic is Turing complete?
  - gwern 8y ago
    Because they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.

Dylan16807 8y ago

I've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic. When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete. It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine, but it's also not doing much at all by itself. A Turing machine is simple, and half a Turing machine is really simple. It's missing the point of "accidental Turing completeness" if it can't iterate to an actual result.

IggleSniggle 8y ago
Off the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.
- svachalek 8y ago
  In CSS itself, I don't know of a way to feed one result back into an earlier one and thus create a loop. If you're talking about JavaScript, it is and was intended to be Turing complete. Edit: Just saw the HTML/CSS3 example on the page. Mind blown.

gwern 8y ago

I have a more up-to-date list at https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete

Y_Y 8y ago
I've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.
eindiran 8y ago
Why do you consider it surprising that Peano Arithmetic is Turing complete?
- gwern 8y ago
  Because they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.