CSS Turing Machine
brandondong.github.io
CSS Turing Machine
1–10 of 23 posts
Re: CSS Turing Machine
#2Re: CSS Turing Machine
#3[deleted]
Re: CSS Turing Machine
#4I 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.
Re: CSS Turing Machine
#5> You need to enable JavaScript to run this app.
That seems like it's cheating, somehow.
Re: CSS Turing Machine
#6I 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…
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 ``) 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...
Re: CSS Turing Machine
#7> You need to enable JavaScript to run this app. That seems like it's cheating, somehow.
It's a React.js "SPA"[0] that generates a "data:" URI containing the entire "machine". When visiting that, there's no JavaScript.
Re: CSS Turing Machine
#8I 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…
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 ` `) 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…
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.
Re: CSS Turing Machine
#9Earlier quoted context omitted.
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 ` `) 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…
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.
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.
Re: CSS Turing Machine
#10Earlier quoted context omitted.
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.
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.
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.