17 ms·

HTML + CSS3 is Turing complete

152 points by bgruber 16y ago

hasenj 16y ago
I don't understand .. explain? EDIT: part of not understanding is I ran it in firefox 3.5 -- not good. works better in chrome.
- jameskilton 16y ago
  http://lmgtfy.com/?q=Rule+110 http://lmgtfy.com/?q=Rule+110 Personally, mind == blown. That is awesome.
- scotth 16y ago
  http://en.wikipedia.org/wiki/Rule_110 http://en.wikipedia.org/wiki/Rule_110
- elitheeli 16y ago
  I tried to do a little bit better of a job explaining it above. I was caught off guard... I intended to post this in a few days with a proper explanation.
CJefferson 16y ago
I'd like a more complete description of this. My first thought is "no it's not", because you are encoding a fixed-sized grid in the HTML, which is then the total extent of the program. While no real machine has an "infinite tape", I think requiring the tape be embedded in the program itself is strengthing things a little far.
- elitheeli 16y ago
  Is my MacBook Pro any more Turing complete? All of the memory came with it. There's no way to expand the memory as it's running.
- metageek 16y ago
  But the HTML is not the program; it's the machine that runs the program. In that view, the tape being finite is just like the tape (RAM, disk, mercury delay lines) of a physical machine being finite.
- samdk 16y ago
  Why is it stretching things a little far? Non-infinite tape is, as you noted, a limit on everything we consider turing complete: this is just running at a much higher level of abstraction than your computer. You could (if you were so inclined) create a physical machine with a grid of memory that behaved according to rules defined by CSS selectors. Just because this doesn't do direct memory access and behave like the computer or a traditional TM doesn't make it not a TM. (Or, at least, any less of a TM than the computer you're using.)
  - kenjackson 16y ago
    The real question is if this can deal with arbitrary amounts of finite memory. That is, could I express an instance of a program that requires a trillion "units" of memory w/o constructing a new "machine" that explicitly laid it out?
elitheeli 16y ago
Way to steal my karma.... :) As the original author of this, I was going to put it into a much more presentable state before showing it off here. For those confused, here's a proper explanation. No real-world thing can actually be Turing complete (able to express basically any computation that we might want to perform of any size). That's because there are finitely many atoms in the universe, so we can only construct machines of finite size. It's well known that Rule 110 (Google it) is Turing Compete. What I've done is made an implementation of Rule 110 in HTML and CSS. Since CSS can't actually really manipulate state, some user interaction is required to "drive" it. In the one that bgruber linked to, it's clicking. Here's a bigger version that doesn't require the user to know where to put his mouse. The tab-space combo is just as legitimate as requiring that you plug a computer into a wall to power it in order to run a Java program. http://elilies.com/rule110-full.html http://elilies.com/rule110-full.html Also, I haven't tested it on anything besides the latest Chrome on Mac.
- Skalman 16y ago
  It works fine on Firefox 4.0b12 on Linux too. :-) That version works much better than the one I tried on github! It's also much cooler.
- mrspeaker 16y ago
  That's what happens when you put something on github! In fact, I bet you any money that someone has already taken the code and created a 16-bit logic unit INSIDE minecraft INSIDE your turing machine.
  - nkassis 16y ago
    you forgot to mention that the turing machine runs in a browser that runs in another turing machine which is inside a huge machine called the universe.
    - riledhel 16y ago
      inside a dream, inside another dream!
setnorth 16y ago
As far as I remember is LaTeX (or TeX itself) touring complete, too. In the end, if you can simulate a turing machine (or another "equivalent" calculating "device") the language is itself turing complete. While not being a html/css wizard, by the amount of complex examples i saw you could do with only HTML/CSS3, I am not surprised that you can write a cellular automaton in it. edit: typo (personal hangup with touring/turing)
- pnathan 16y ago
  Turing. Not 'touring'. Please, it was right up there in the headline.
  - scott_s 16y ago
    True story: I met a guy at PLDI from the University of Texas. Dijkstra was a professor at UT during this guy's first few years. Dijkstra and his wife had a van they went around the country in they called their Touring Machine.
- elitheeli 16y ago
  TeX is very Turing complete. As is Java sans semicolons, C macros, and many other things that probably shouldn't be. Right now, I'm trying to figure out what the minimum number of characters you need in Ruby is to make it Turing complete. I'm pretty sure that if you restrict yourself to under 12 characters, it's still possible.
  - Xk 16y ago
    C macros are not Turing complete, they're a pushdown automaton. C++ templates are. Check out this IOCCC entry which does simulate a Turing machine, but only by having another script repeatedly run it. Edit: Yes, I meant to copy the link, see mchouza's comment for the link.
    - mchouza 16y ago
      Link: http://www.ioccc.org/2001/ http://www.ioccc.org/2001/ (herrmann1 files)
taylorbuley 16y ago
http://jsbin.com/owehi4/ http://jsbin.com/owehi4/
kcl 16y ago
There are two competing definitions of Turing complete here. 1. The mathematical definition of Turing completeness: models which can simulate the computation of a hypothetical Turing machine. Idealized circuits are an example of this. Turing machines are an example of this. Programs with infinite memory are an example of this. 2. The colloquial definition of Turing completeness: this is naturally ill-defined, but it roughly means an automated, finite model that performs arbitrary computation. I would say that a robotic Lego Turing machine is Turing complete. C is certainly Turing complete in this sense. Basic HTML isn't. The set of regexes (e.g, unix wildcards) isn't. However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C? The answer is they are just as powerful in the finite case, unless we set reasonable limits on what we mean by 'finite' and 'automated.' This HTML+CSS is not Turing complete. The idealized version of this HTML+CSS is not Turing complete (unless you strangely accept the idealization of a "hand pressing tab space"). This HTML+CSS is also not Turing complete in the colloquial sense: it doesn't live up to the generally accepted notion of automation. It isn't executed by the machine.
- dmm 16y ago
  > However, if I can choose a large enough regex, I can construct a decider for a given finite language. What do you mean by this? What is a "decider"? What do you mean by a finite language?
  - anorwell 16y ago
    Language: http://en.wikipedia.org/wiki/Formal_language http://en.wikipedia.org/wiki/Formal_language Decision problem: http://en.wikipedia.org/wiki/Decision_problem http://en.wikipedia.org/wiki/Decision_problem Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts http://en.wikipedia.org/wiki/Machine_that_always_halts These are fairly foundational concepts when talking about computational complexity.
    - dmm 16y ago
      > However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C? Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine. So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do? Is that close?
ssp 16y ago
I'm probably tilting at windmills, but it's Turing Equivalent, not Turing Complete.
- sid0 16y ago
  It'll be a really big deal the day we find a model of computation more general than Turing machines. Till then, in most contexts they're interchangeable. Also, if you really want to tilt at windmills, Turing complete is a weaker statement than Turing equivalent, so he isn't wrong.
  - ssp 16y ago
    No, you are misunderstanding. A language L is complete for a complexity class C if it is in C and all languages in C can be reduced to L. "Turing" is not a complexity class, so "Turing Complete" is nonsense. And if it did mean something, it would probably refer to a recursive language to which all other recursive languages could be reduced. "Turing Equivalent" is something a programming language can be and doesn't have much to do with complexity theory.
    - sid0 16y ago
      "Turing" is not a complexity class, so "Turing Complete" is nonsense. Good thing that complexity theory isn't the only part of CS that uses the notion of completeness. Turing (aka recursively enumerable functions) is a computability class, and it makes sense to talk about models of computation complete for that class.

152 points by bgruber 16y ago

I don't understand .. explain? EDIT: part of not understanding is I ran it in firefox 3.5 -- not good. works better in chrome.

jameskilton 16y ago
http://lmgtfy.com/?q=Rule+110 http://lmgtfy.com/?q=Rule+110 Personally, mind == blown. That is awesome.
scotth 16y ago
http://en.wikipedia.org/wiki/Rule_110 http://en.wikipedia.org/wiki/Rule_110
elitheeli 16y ago
I tried to do a little bit better of a job explaining it above. I was caught off guard... I intended to post this in a few days with a proper explanation.

CJefferson 16y ago

I'd like a more complete description of this. My first thought is "no it's not", because you are encoding a fixed-sized grid in the HTML, which is then the total extent of the program. While no real machine has an "infinite tape", I think requiring the tape be embedded in the program itself is strengthing things a little far.

elitheeli 16y ago
Is my MacBook Pro any more Turing complete? All of the memory came with it. There's no way to expand the memory as it's running.
metageek 16y ago
But the HTML is not the program; it's the machine that runs the program. In that view, the tape being finite is just like the tape (RAM, disk, mercury delay lines) of a physical machine being finite.
samdk 16y ago
Why is it stretching things a little far? Non-infinite tape is, as you noted, a limit on everything we consider turing complete: this is just running at a much higher level of abstraction than your computer. You could (if you were so inclined) create a physical machine with a grid of memory that behaved according to rules defined by CSS selectors. Just because this doesn't do direct memory access and behave like the computer or a traditional TM doesn't make it not a TM. (Or, at least, any less of a TM than the computer you're using.)
- kenjackson 16y ago
  The real question is if this can deal with arbitrary amounts of finite memory. That is, could I express an instance of a program that requires a trillion "units" of memory w/o constructing a new "machine" that explicitly laid it out?

elitheeli 16y ago

Way to steal my karma.... :) As the original author of this, I was going to put it into a much more presentable state before showing it off here. For those confused, here's a proper explanation. No real-world thing can actually be Turing complete (able to express basically any computation that we might want to perform of any size). That's because there are finitely many atoms in the universe, so we can only construct machines of finite size. It's well known that Rule 110 (Google it) is Turing Compete. What I've done is made an implementation of Rule 110 in HTML and CSS. Since CSS can't actually really manipulate state, some user interaction is required to "drive" it. In the one that bgruber linked to, it's clicking. Here's a bigger version that doesn't require the user to know where to put his mouse. The tab-space combo is just as legitimate as requiring that you plug a computer into a wall to power it in order to run a Java program. http://elilies.com/rule110-full.html http://elilies.com/rule110-full.html Also, I haven't tested it on anything besides the latest Chrome on Mac.

Skalman 16y ago
It works fine on Firefox 4.0b12 on Linux too. :-) That version works much better than the one I tried on github! It's also much cooler.
mrspeaker 16y ago
That's what happens when you put something on github! In fact, I bet you any money that someone has already taken the code and created a 16-bit logic unit INSIDE minecraft INSIDE your turing machine.
- nkassis 16y ago
  you forgot to mention that the turing machine runs in a browser that runs in another turing machine which is inside a huge machine called the universe.
  - riledhel 16y ago
    inside a dream, inside another dream!

setnorth 16y ago

As far as I remember is LaTeX (or TeX itself) touring complete, too. In the end, if you can simulate a turing machine (or another "equivalent" calculating "device") the language is itself turing complete. While not being a html/css wizard, by the amount of complex examples i saw you could do with only HTML/CSS3, I am not surprised that you can write a cellular automaton in it. edit: typo (personal hangup with touring/turing)

pnathan 16y ago
Turing. Not 'touring'. Please, it was right up there in the headline.
- scott_s 16y ago
  True story: I met a guy at PLDI from the University of Texas. Dijkstra was a professor at UT during this guy's first few years. Dijkstra and his wife had a van they went around the country in they called their Touring Machine.
elitheeli 16y ago
TeX is very Turing complete. As is Java sans semicolons, C macros, and many other things that probably shouldn't be. Right now, I'm trying to figure out what the minimum number of characters you need in Ruby is to make it Turing complete. I'm pretty sure that if you restrict yourself to under 12 characters, it's still possible.
- Xk 16y ago
  C macros are not Turing complete, they're a pushdown automaton. C++ templates are. Check out this IOCCC entry which does simulate a Turing machine, but only by having another script repeatedly run it. Edit: Yes, I meant to copy the link, see mchouza's comment for the link.
  - mchouza 16y ago
    Link: http://www.ioccc.org/2001/ http://www.ioccc.org/2001/ (herrmann1 files)

taylorbuley 16y ago

http://jsbin.com/owehi4/ http://jsbin.com/owehi4/

kcl 16y ago

There are two competing definitions of Turing complete here. 1. The mathematical definition of Turing completeness: models which can simulate the computation of a hypothetical Turing machine. Idealized circuits are an example of this. Turing machines are an example of this. Programs with infinite memory are an example of this. 2. The colloquial definition of Turing completeness: this is naturally ill-defined, but it roughly means an automated, finite model that performs arbitrary computation. I would say that a robotic Lego Turing machine is Turing complete. C is certainly Turing complete in this sense. Basic HTML isn't. The set of regexes (e.g, unix wildcards) isn't. However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C? The answer is they are just as powerful in the finite case, unless we set reasonable limits on what we mean by 'finite' and 'automated.' This HTML+CSS is not Turing complete. The idealized version of this HTML+CSS is not Turing complete (unless you strangely accept the idealization of a "hand pressing tab space"). This HTML+CSS is also not Turing complete in the colloquial sense: it doesn't live up to the generally accepted notion of automation. It isn't executed by the machine.

dmm 16y ago
> However, if I can choose a large enough regex, I can construct a decider for a given finite language. What do you mean by this? What is a "decider"? What do you mean by a finite language?
- anorwell 16y ago
  Language: http://en.wikipedia.org/wiki/Formal_language http://en.wikipedia.org/wiki/Formal_language Decision problem: http://en.wikipedia.org/wiki/Decision_problem http://en.wikipedia.org/wiki/Decision_problem Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts http://en.wikipedia.org/wiki/Machine_that_always_halts These are fairly foundational concepts when talking about computational complexity.
  - dmm 16y ago
    > However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C? Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine. So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do? Is that close?

ssp 16y ago

I'm probably tilting at windmills, but it's Turing Equivalent, not Turing Complete.

sid0 16y ago
It'll be a really big deal the day we find a model of computation more general than Turing machines. Till then, in most contexts they're interchangeable. Also, if you really want to tilt at windmills, Turing complete is a weaker statement than Turing equivalent, so he isn't wrong.
- ssp 16y ago
  No, you are misunderstanding. A language L is complete for a complexity class C if it is in C and all languages in C can be reduced to L. "Turing" is not a complexity class, so "Turing Complete" is nonsense. And if it did mean something, it would probably refer to a recursive language to which all other recursive languages could be reduced. "Turing Equivalent" is something a programming language can be and doesn't have much to do with complexity theory.
  - sid0 16y ago
    "Turing" is not a complexity class, so "Turing Complete" is nonsense. Good thing that complexity theory isn't the only part of CS that uses the notion of completeness. Turing (aka recursively enumerable functions) is a computability class, and it makes sense to talk about models of computation complete for that class.