7 ms·

Is CSS Turing Complete?

61 points by cordite 13y ago

okonomiyaki3000 13y ago
More importantly, can it be expanded to the point that it is able to read mail and, if not, when will it be replaced with something that can?
cheepin 13y ago
Can someone explain how the demo proves that it is Turing Complete? I haven't taken automata yet.
- choudharism 13y ago
  It doesn't. As someone pointed out, Tic Tac Toe can be implemented in Finite State Machines [1], which have less computational ability than Turing Machines [2]. [1] https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [2] https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/Turing_machine
  - Buge 13y ago
    Isn't the only difference between a finite-state machine and a Turing machine whether the memory is finite or not? Then you could argue that nothing has ever been made that is Turing complete because everything can be simulated by a finite-state machine because of memory limitations.
    - Dewie 13y ago
      Yes; in the strictest sense, CPU+RAM is a finite state machine, not a Turing machine with an unbounded memory.
    - edmccard 13y ago
      There is a difference, though, between a finite state machine and a Turing machine with a finite amount of memory. An FSM cannot recognize context-free languages, but a Turing machine can--even when it's implemented on a computer without infinite memory. (Actually, you only need a pushdown automata for context-free languages--I forget what the next step up in the hierarchy is, the one that does require Turing completeness)
      - mikeash 13y ago
        A Turing machine without infinite memory can't recognize context-free languages. Take the standard example of recognizing the language of balanced parentheses. With finite memory, there's a limit to how many parentheses you can keep track of. That limit is going to be gigantic for any reasonable amount of memory, but it's still a limit. The language of balanced parentheses with a depth limit is no longer a context-free language, but a regular language, and as such can be recognized by a FSM. It's trivial to demonstrate that a Turing machine with finite memory is equivalent to a FSM. Enumerate all possible memory contents. This number is, again, large for any reasonable amount of memory, but it is finite. For each possible memory content, enumerate the Turing machine states. Each memory state plus machine state becomes one FSM state. The Turing machine defines a transition from one state to another plus an action on memory, which becomes an FSM transition to the state that encodes both the new machine state and the new memory state.
        timtadh 13y ago
        Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have.[1] It can be matched by a Push Down Automata PDA. The primary difference between a PDA and an FSM is a PDA has a stack which acts as memory. Thus, a PDA can remember how many parens it has seen before. Every time it sees an open paren it will push it onto the stack, when it sees a close paren it pops. When the stack is empty it matches if the input has been consumed. The difference between a PDA and a Turing machine is the stack is now a read/writable tape which can move in either direction. Notice how in both formulations there is no limit on the memory (the PDA stack is could be infinite as can the Turing machine tape). In contrast a Finite State Machine doesn't have any memory. The finite refers to the number of states not the amount of memory. Indeed, Turing machines are traditionally formulated with finite states as well. Thus, a FSM can never match the langauge of matching parens but a Turing machine can. It will either match or consume all of its memory if memory is limited. Memory limitations are not a statement on computational power but rather a statement on feasibility. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... EDIT: Your second paragraph is of course correct - you could encode every possible stack as a FSM if there is a bound on the stack. HOWEVER, if you have a limit on memory but it is essentially unknown (you know memory is finite but you don't know exactly what the limit is) a PDA or a Turing machine will of course be able to match things your FSM cannot (because they can take advantage of the memory your FSM cannot assume it has in its states). Memory limitations are in some sense an implementation detail. We could design a computer to pause while we buy more ram. Then it could use as much memory (in theory) as the human race could produce. That sounds like infinite for some definition of the word.
    - im3w1l 13y ago
      In my opinion an important point is that for a turing complete language being run on a machine with finite memory, if you have problem for which it runs out of memory, you could conceivably throw more memory at the problem and have it work. If you a non-complete language, more memory is not enough, you will have to do a rewrite in addition.
- evanb 13y ago
  If CSS really can implement rule 110, then it is Turing Complete, because rule 110 is itself Turing Complete: https://en.wikipedia.org/wiki/Rule_110#Interesting_properties https://en.wikipedia.org/wiki/Rule_110#Interesting_propertie...
  - schoen 13y ago
    There seems to be a semantic problem here, though, because an infinite cellular automaton that applies rule 110 over and over again is Turing complete. Whereas this CSS application applies one iteration of rule 110 at a time in a way that the human user can then choose to repeat by pressing keys when prompted.
    - nubs 13y ago
      Isn't that analogous to how a CPU only applies one instruction at a time? Replace the user clicking a button with an automated process and it's easy to see that the CSS+HTML is what is doing the actual processing. Alternatively, putting a button on a computer that must be pressed to have the CPU execute an instruction and move on to the next doesn't mean that programs on this computer aren't turing complete.
      - aninhumer 13y ago
        >Replace the user clicking a button with an automated process and it's easy to see that the CSS+HTML is what is doing the actual processing. In which case the complete system including the "automated process" is Turing complete, but the CSS itself is not. >Alternatively, putting a button on a computer that must be pressed to have the CPU execute an instruction and move on to the next doesn't mean that programs on this computer aren't Turing complete. "Programs" can't be Turing complete, it's a property of computation systems. And putting the button on the computer would indeed mean it wasn't Turing complete (unless you consider the human pushing the button part of the system).
      - bdonlan 13y ago
        Non-termination is a fundamental property of turing machines; after all, if all programs terminate, a halting problem decider is trivial to write. While you could certainly argue that the CSS + human system is a turing-complete system, the CSS is a bit superfluous there; the human could just be doing all the work on their own. As such, when a language or system is proven to be turing complete, it generally has to be shown to emulate another turing-complete system _until termination_ without external assistance.
bilalq 13y ago
One of the answers towards the bottom linked to an incredibly interesting read on programming using nothing but Procs[1]. I found it to be incredibly fascinating, and it even goes into implementing FizzBuzz under these constraints. [1]: http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing
- jacquesm 13y ago
  If you liked that you'll love this: http://matt.might.net/articles/compiling-up-to-lambda-calculus/ http://matt.might.net/articles/compiling-up-to-lambda-calcul... and http://matt.might.net/articles/implementing-a-programming-language/ http://matt.might.net/articles/implementing-a-programming-la...
  - voltagex_ 13y ago
    Related: What if you started with no OS? http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/c0ewj2c http://www.reddit.com/r/programming/comments/9x15g/programmi... Includes some really great links to going from (DOS) echo to a working COM executable: http://lists.canonical.org/pipermail/kragen-discuss/2011-April/001156.html http://lists.canonical.org/pipermail/kragen-discuss/2011-Apr...
  - bilalq 13y ago
    Thanks for the links. I really regret that I didn't pursue topics like this while in school, but I suppose its never too late to keep on learning.
    - SixSigma 13y ago
      You sound like you're resigned to learning rather than enthused. How old are you ? (although that's rhetorical) I'm 45 and I still read a textbook a month. There does come a time when young that you can say "finally, no more education!" What I have found when revisiting topics is that my life experience contributes into the subject for me rather than merely being a set of facts & analogies from someone else. I only recently read The Annotated Turing by Petzold, that was the kind of eye opener that would have looked far to dry a subject to me years ago. Time has given me the ability to peek through Turing's eyes and imagine the sociological and pedagogical environment he was operating in which really adds to the material.
andrewguenther 13y ago
I'm coining it now, Guenther's law, corollary to Atwood's law: Anything that can be implemented in CSS, shouldn't be.
- theandrewbailey 13y ago
  I really hope that's sarcasm. Otherwise we will have people ripping out CSS, like how some people don't optimize because premature optimization is evil. I also don't want to go back to font tags.
  - andrewguenther 13y ago
    Did we even read the same post? I'm joking that people shouldn't write Turing complete code in CSS. Add style properties for days, more power to you, but if someone posts an implementation of Git in CSS next week I will promptly jump off a bridge, laughing all the way down.
    - baddox 13y ago
      Your phrasing of the proposed law isn't quite right. According to it, red text should not be implemented in CSS since it can be implemented in CSS.
      - theandrewbailey 13y ago
        Bingo!
deleted 13y ago
[deleted]
rectangletangle 13y ago
So who's going to be the first to write a full blown web-framework in CSS? I'm mean who really wants the unnecessary bloat of a dependency like JavaScript?
Grue3 13y ago
The easiest way to prove that CSS is not Turing complete is to demonstrate that every CSS "program" terminates, therefore halting problem is solvable for CSS. Indeed, a proper CSS engine will process a set of CSS rules in finite time, or display an error. Therefore CSS cannot be Turing complete.
- muyuu 13y ago
  Where's this proof?
catkin 13y ago
This is called a Turing tarpit (https://en.wikipedia.org/wiki/Turing_tar_pit https://en.wikipedia.org/wiki/Turing_tar_pit): where a system is technically Turing-complete, but in reality is too awkward to do anything useful with.

61 points by cordite 13y ago

More importantly, can it be expanded to the point that it is able to read mail and, if not, when will it be replaced with something that can?

cheepin 13y ago

Can someone explain how the demo proves that it is Turing Complete? I haven't taken automata yet.

choudharism 13y ago
It doesn't. As someone pointed out, Tic Tac Toe can be implemented in Finite State Machines [1], which have less computational ability than Turing Machines [2]. [1] https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [2] https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/Turing_machine
- Buge 13y ago
  Isn't the only difference between a finite-state machine and a Turing machine whether the memory is finite or not? Then you could argue that nothing has ever been made that is Turing complete because everything can be simulated by a finite-state machine because of memory limitations.
  - Dewie 13y ago
    Yes; in the strictest sense, CPU+RAM is a finite state machine, not a Turing machine with an unbounded memory.
  - edmccard 13y ago
    There is a difference, though, between a finite state machine and a Turing machine with a finite amount of memory. An FSM cannot recognize context-free languages, but a Turing machine can--even when it's implemented on a computer without infinite memory. (Actually, you only need a pushdown automata for context-free languages--I forget what the next step up in the hierarchy is, the one that does require Turing completeness)
    - mikeash 13y ago
      A Turing machine without infinite memory can't recognize context-free languages. Take the standard example of recognizing the language of balanced parentheses. With finite memory, there's a limit to how many parentheses you can keep track of. That limit is going to be gigantic for any reasonable amount of memory, but it's still a limit. The language of balanced parentheses with a depth limit is no longer a context-free language, but a regular language, and as such can be recognized by a FSM. It's trivial to demonstrate that a Turing machine with finite memory is equivalent to a FSM. Enumerate all possible memory contents. This number is, again, large for any reasonable amount of memory, but it is finite. For each possible memory content, enumerate the Turing machine states. Each memory state plus machine state becomes one FSM state. The Turing machine defines a transition from one state to another plus an action on memory, which becomes an FSM transition to the state that encodes both the new machine state and the new memory state.
      - timtadh 13y ago
        Not at all true, the language of balanced parens is not regular and cannot be matched by a FSM no matter how much memory you have.[1] It can be matched by a Push Down Automata PDA. The primary difference between a PDA and an FSM is a PDA has a stack which acts as memory. Thus, a PDA can remember how many parens it has seen before. Every time it sees an open paren it will push it onto the stack, when it sees a close paren it pops. When the stack is empty it matches if the input has been consumed. The difference between a PDA and a Turing machine is the stack is now a read/writable tape which can move in either direction. Notice how in both formulations there is no limit on the memory (the PDA stack is could be infinite as can the Turing machine tape). In contrast a Finite State Machine doesn't have any memory. The finite refers to the number of states not the amount of memory. Indeed, Turing machines are traditionally formulated with finite states as well. Thus, a FSM can never match the langauge of matching parens but a Turing machine can. It will either match or consume all of its memory if memory is limited. Memory limitations are not a statement on computational power but rather a statement on feasibility. https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... EDIT: Your second paragraph is of course correct - you could encode every possible stack as a FSM if there is a bound on the stack. HOWEVER, if you have a limit on memory but it is essentially unknown (you know memory is finite but you don't know exactly what the limit is) a PDA or a Turing machine will of course be able to match things your FSM cannot (because they can take advantage of the memory your FSM cannot assume it has in its states). Memory limitations are in some sense an implementation detail. We could design a computer to pause while we buy more ram. Then it could use as much memory (in theory) as the human race could produce. That sounds like infinite for some definition of the word.
  - im3w1l 13y ago
    In my opinion an important point is that for a turing complete language being run on a machine with finite memory, if you have problem for which it runs out of memory, you could conceivably throw more memory at the problem and have it work. If you a non-complete language, more memory is not enough, you will have to do a rewrite in addition.
evanb 13y ago
If CSS really can implement rule 110, then it is Turing Complete, because rule 110 is itself Turing Complete: https://en.wikipedia.org/wiki/Rule_110#Interesting_properties https://en.wikipedia.org/wiki/Rule_110#Interesting_propertie...
- schoen 13y ago
  There seems to be a semantic problem here, though, because an infinite cellular automaton that applies rule 110 over and over again is Turing complete. Whereas this CSS application applies one iteration of rule 110 at a time in a way that the human user can then choose to repeat by pressing keys when prompted.
  - nubs 13y ago
    Isn't that analogous to how a CPU only applies one instruction at a time? Replace the user clicking a button with an automated process and it's easy to see that the CSS+HTML is what is doing the actual processing. Alternatively, putting a button on a computer that must be pressed to have the CPU execute an instruction and move on to the next doesn't mean that programs on this computer aren't turing complete.
    - aninhumer 13y ago
      >Replace the user clicking a button with an automated process and it's easy to see that the CSS+HTML is what is doing the actual processing. In which case the complete system including the "automated process" is Turing complete, but the CSS itself is not. >Alternatively, putting a button on a computer that must be pressed to have the CPU execute an instruction and move on to the next doesn't mean that programs on this computer aren't Turing complete. "Programs" can't be Turing complete, it's a property of computation systems. And putting the button on the computer would indeed mean it wasn't Turing complete (unless you consider the human pushing the button part of the system).
    - bdonlan 13y ago
      Non-termination is a fundamental property of turing machines; after all, if all programs terminate, a halting problem decider is trivial to write. While you could certainly argue that the CSS + human system is a turing-complete system, the CSS is a bit superfluous there; the human could just be doing all the work on their own. As such, when a language or system is proven to be turing complete, it generally has to be shown to emulate another turing-complete system _until termination_ without external assistance.

bilalq 13y ago

One of the answers towards the bottom linked to an incredibly interesting read on programming using nothing but Procs[1]. I found it to be incredibly fascinating, and it even goes into implementing FizzBuzz under these constraints. [1]: http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing

jacquesm 13y ago
If you liked that you'll love this: http://matt.might.net/articles/compiling-up-to-lambda-calculus/ http://matt.might.net/articles/compiling-up-to-lambda-calcul... and http://matt.might.net/articles/implementing-a-programming-language/ http://matt.might.net/articles/implementing-a-programming-la...
- voltagex_ 13y ago
  Related: What if you started with no OS? http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/c0ewj2c http://www.reddit.com/r/programming/comments/9x15g/programmi... Includes some really great links to going from (DOS) echo to a working COM executable: http://lists.canonical.org/pipermail/kragen-discuss/2011-April/001156.html http://lists.canonical.org/pipermail/kragen-discuss/2011-Apr...
- bilalq 13y ago
  Thanks for the links. I really regret that I didn't pursue topics like this while in school, but I suppose its never too late to keep on learning.
  - SixSigma 13y ago
    You sound like you're resigned to learning rather than enthused. How old are you ? (although that's rhetorical) I'm 45 and I still read a textbook a month. There does come a time when young that you can say "finally, no more education!" What I have found when revisiting topics is that my life experience contributes into the subject for me rather than merely being a set of facts & analogies from someone else. I only recently read The Annotated Turing by Petzold, that was the kind of eye opener that would have looked far to dry a subject to me years ago. Time has given me the ability to peek through Turing's eyes and imagine the sociological and pedagogical environment he was operating in which really adds to the material.

andrewguenther 13y ago

I'm coining it now, Guenther's law, corollary to Atwood's law: Anything that can be implemented in CSS, shouldn't be.

theandrewbailey 13y ago
I really hope that's sarcasm. Otherwise we will have people ripping out CSS, like how some people don't optimize because premature optimization is evil. I also don't want to go back to font tags.
- andrewguenther 13y ago
  Did we even read the same post? I'm joking that people shouldn't write Turing complete code in CSS. Add style properties for days, more power to you, but if someone posts an implementation of Git in CSS next week I will promptly jump off a bridge, laughing all the way down.
  - baddox 13y ago
    Your phrasing of the proposed law isn't quite right. According to it, red text should not be implemented in CSS since it can be implemented in CSS.
    - theandrewbailey 13y ago
      Bingo!

deleted 13y ago

[deleted]

rectangletangle 13y ago

So who's going to be the first to write a full blown web-framework in CSS? I'm mean who really wants the unnecessary bloat of a dependency like JavaScript?

Grue3 13y ago

The easiest way to prove that CSS is not Turing complete is to demonstrate that every CSS "program" terminates, therefore halting problem is solvable for CSS. Indeed, a proper CSS engine will process a set of CSS rules in finite time, or display an error. Therefore CSS cannot be Turing complete.

muyuu 13y ago
Where's this proof?

catkin 13y ago

This is called a Turing tarpit (https://en.wikipedia.org/wiki/Turing_tar_pit https://en.wikipedia.org/wiki/Turing_tar_pit): where a system is technically Turing-complete, but in reality is too awkward to do anything useful with.