[HN Gopher] CSS Turing Machine ___________________________________________________________________ CSS Turing Machine Author : mr_tyzic Score : 18 points Date : 2021-01-14 20:37 UTC (2 hours ago) (HTM) web link (brandondong.github.io) (TXT) w3m dump (brandondong.github.io) | mr_tyzic wrote: | More on this: | | https://notlaura.com/is-css-turing-complete/ | | https://stackoverflow.com/questions/2497146/is-css-turing-co... | bidirectional wrote: | I disagree that this proves the Turing completeness of CSS. | Part of the definition of Turing machines is access to | unbounded memory. In Python, for example, we meet this | requirement by saying that any underlying request to new memory | will succeed, or we can imagine an implementation of Python | without a stack limit and lambda-encode everything. Ultimately, | Python as an abstract language has no memory limitations, | that's just an artifact of us implementing it on real-world | machines. The same could be said for Haskell or Javascript. | | CSS on the other hand (or at least the encoding presented | here), requires us to state upfront, in the CSS file, how many | cells we need. This is equivalent to non-Turing complete finite | state machines. If we must encode memory bounds in the program, | we can solve the halting problem, can't translate certain | Python programs, can solve the Busy Beaver problem via a lookup | table, etc. One of the main goals of Turing when defining | computability was describing potentially infinite processes | with a finite language. | [deleted] ___________________________________________________________________ (page generated 2021-01-14 23:00 UTC)