[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)