7 ms·

CSS Turing Machine

57 points by mr_tyzic 6y ago

mr_tyzic 6y ago
More on this: https://notlaura.com/is-css-turing-complete/ https://notlaura.com/is-css-turing-complete/ https://stackoverflow.com/questions/2497146/is-css-turing-complete https://stackoverflow.com/questions/2497146/is-css-turing-co...
deleted 6y ago
[deleted]
bidirectional 6y ago
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.
- colejohnson66 6y ago
  That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using `<input type="checkbox"/>`) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a] [a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle of the top of [0]) [0]: https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit_2GB_PC2-5300U-555.jpg https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit...
  - arcticbull 6y ago
    Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.
    - bawolff 6y ago
      Why not? I can imagine a modified abstract css machine which applies the styles to an infinitely long html document. That's much more contrived than the python case, but if we are going to be making arbitrary changes from finite machines, im not sure under what basis we would draw the line.
      - maweki 6y ago
        The html document is potentially infinite, but its finite length is not encoded in the program (css). One idea is, to have the same program, and if it terminates, it will terminate if you pick a large enough machine. You don't need to "rewrite" the program to use a larger machine. So in this case the html document is the tape. Potentially infinite, but not in reality. The css program may handle it as infinite.
    - weare138 6y ago
      >that there exists an abstract Python machine wherein the memory does not need to be so described This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and like anything we do on modern computers, can be reduced to assembly where again memory has to be 'described'. Python may hide it for us but it's there.
      - deleted 6y ago
        [deleted]
- deleted 6y ago
  [deleted]
- saagarjha 6y ago
  (This is also why C is not Turing complete.)
  - Aardwolf 6y ago
    Does there exist any formal terminology for "something that is like a Turing machine if it would have infinite memory"? I'm asking because since the true definition of a Turing machine requires infinite memory, in theory nothing can be a Turing machine in the observable universe, so this definition doesn't help describe anything that's used in practice. On the other hand, there's an obvious difference in power of a language like C, versus non Turing-complete languages like regexp. So it's useful to talk about this concept, but we could never formally call any of those Turing complete (C pointers are limited to so many bits, for example). The discussion about this detail comes up every time, so is there some proper formal term for this? Something related to how much code is required to use the finite pool of memory you have in any way you want, or so (where a non turing complete language may require enumerating all possibilites and thus too large code size)
    - roywiggins 6y ago
      You can assume that, if the machine runs out of memory, that someone comes along and installs another gigabyte and sets it going again. Predicting whether programs will halt under those conditions is exactly the same as if they really had an infinite tape. It's a bit tricky with real programs because eventually you might expect you'd run out of address space, so you might have to relax constraints and say that at least some integer types don't have a defined maximum value, or stuff like that.
  - noctune 6y ago
    It is Turing complete if you access the tape using something like fread/fwrite.
- j-pb 6y ago
  This still proves that CSS layout algorithms are O(EVIL). Enumerating and memoizing all possible states will still be impractical, even for small machines.
dane-pgp 6y ago
> You need to enable JavaScript to run this app. That seems like it's cheating, somehow.
- colejohnson66 6y ago
  It's a React.js "SPA"[0] that generates a "data:" URI containing the entire "machine". When visiting that, there's no JavaScript. [0]: https://github.com/brandondong/css-turing-machine https://github.com/brandondong/css-turing-machine

57 points by mr_tyzic 6y ago

More on this: https://notlaura.com/is-css-turing-complete/ https://notlaura.com/is-css-turing-complete/ https://stackoverflow.com/questions/2497146/is-css-turing-complete https://stackoverflow.com/questions/2497146/is-css-turing-co...

deleted 6y ago

[deleted]

bidirectional 6y ago

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.

colejohnson66 6y ago
That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using `<input type="checkbox"/>`) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a] [a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle of the top of [0]) [0]: https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit_2GB_PC2-5300U-555.jpg https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit...
- arcticbull 6y ago
  Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.
  - bawolff 6y ago
    Why not? I can imagine a modified abstract css machine which applies the styles to an infinitely long html document. That's much more contrived than the python case, but if we are going to be making arbitrary changes from finite machines, im not sure under what basis we would draw the line.
    - maweki 6y ago
      The html document is potentially infinite, but its finite length is not encoded in the program (css). One idea is, to have the same program, and if it terminates, it will terminate if you pick a large enough machine. You don't need to "rewrite" the program to use a larger machine. So in this case the html document is the tape. Potentially infinite, but not in reality. The css program may handle it as infinite.
  - weare138 6y ago
    >that there exists an abstract Python machine wherein the memory does not need to be so described This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and like anything we do on modern computers, can be reduced to assembly where again memory has to be 'described'. Python may hide it for us but it's there.
    - deleted 6y ago
      [deleted]
deleted 6y ago
[deleted]
saagarjha 6y ago
(This is also why C is not Turing complete.)
- Aardwolf 6y ago
  Does there exist any formal terminology for "something that is like a Turing machine if it would have infinite memory"? I'm asking because since the true definition of a Turing machine requires infinite memory, in theory nothing can be a Turing machine in the observable universe, so this definition doesn't help describe anything that's used in practice. On the other hand, there's an obvious difference in power of a language like C, versus non Turing-complete languages like regexp. So it's useful to talk about this concept, but we could never formally call any of those Turing complete (C pointers are limited to so many bits, for example). The discussion about this detail comes up every time, so is there some proper formal term for this? Something related to how much code is required to use the finite pool of memory you have in any way you want, or so (where a non turing complete language may require enumerating all possibilites and thus too large code size)
  - roywiggins 6y ago
    You can assume that, if the machine runs out of memory, that someone comes along and installs another gigabyte and sets it going again. Predicting whether programs will halt under those conditions is exactly the same as if they really had an infinite tape. It's a bit tricky with real programs because eventually you might expect you'd run out of address space, so you might have to relax constraints and say that at least some integer types don't have a defined maximum value, or stuff like that.
- noctune 6y ago
  It is Turing complete if you access the tape using something like fread/fwrite.
j-pb 6y ago
This still proves that CSS layout algorithms are O(EVIL). Enumerating and memoizing all possible states will still be impractical, even for small machines.

dane-pgp 6y ago

> You need to enable JavaScript to run this app. That seems like it's cheating, somehow.

colejohnson66 6y ago
It's a React.js "SPA"[0] that generates a "data:" URI containing the entire "machine". When visiting that, there's no JavaScript. [0]: https://github.com/brandondong/css-turing-machine https://github.com/brandondong/css-turing-machine