3 ms·
I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombi
by yorwba 8y ago
I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377 https://news.ycombinator.com/item?id=15712377
- mettamage 8y agoI'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 agoI'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 agoOff the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.
- svachalek 8y agoIn 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 agoI have a more up-to-date list at https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete
- Y_Y 8y agoI've heard you can perform arbitrarily difficult calculations just by getting gwern interested enough to write an article.
- eindiran 8y agoWhy do you consider it surprising that Peano Arithmetic is Turing complete?
- gwern 8y agoBecause 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.
- mrob 8y agoThis version is better because all the moves are forced. The previous version only worked if all players cooperate by taking optional actions.
- UncleMeat 8y agoNo it hasnt. This is a new result that requires no choices by either player. It is in the paper.
- justinmchase 8y agoWhere is the actual paper? I just see the overview in the bibliography.
- Zanni 8y agoThere's a download link to the right of the abstract. Here's the PDF, in case it's not showing up on mobile, or whatever: https://arxiv.org/pdf/1904.09828.pdf https://arxiv.org/pdf/1904.09828.pdf