4

Is it possible to write a compiler in HTML+CSS? I know that they (together) are supposedly Turing complete, at least the HTML5/CSS3 combo. So it should be possible to write a compiler for, say, Java in it right? Or do I have some sort of fundamental misunderstanding of what Turing completeness means? Since HTML+CSS are not compiled languages themselves does this mean it is impossible to write a compiler in them? (Could you also write a compiler for HTML/CSS?)

user2258552
  • 824
  • 1
  • 11
  • 25

1 Answers1

3

While it is possible to implement some Turing-equivalent systems (such as Rule 110 - http://eli.fox-epste.in/rule110-full.html) in HTML and CSS alone, the resulting implementation cannot be used as a computer in any useful sense. It has an extremely high overhead, and would take an absolutely gigantic web page to perform even very simple computations (e.g, adding together small numbers) with. A Java compiler would be utterly impossible.

Take-home lesson here: Not all "Turing-complete" systems are equal. There are vast differences in how efficiently they can get work done.

  • 1
    I understand that. I might not have been clear, but I was wondering if it is even theoretically possible. – user2258552 Jul 30 '13 at 15:43
  • 2
    Theoretically possible? Yes - if you have a web browser that can handle a page with billions+ of elements. (Which doesn't exist.) –  Jul 30 '13 at 16:38
  • 1
    According to this comment, it's not: http://stackoverflow.com/questions/2497146/is-css-turing-complete#comment18671468_5239256. The comment seems to suggest that it's not truly turing complete which would suggest that it couldn't do things like build compilers, even in theory. – user2258552 Jul 31 '13 at 16:23
  • See the link I provided - the only user interaction required is to repeatedly press tab and space to "pump" the system. All the "computation" (such as it is) is still done by the HTML/CSS system. –  Jul 31 '13 at 18:00
  • 1
    Right, but how would you [theoretically] write a java compiler using that method? I did see the link, but the user still needs to pump the system manually, whereas any Turing Complete language that I know of does it programatically. Would it be possible to have the user enter the program in a textbox and then have to click a bunch of buttons? Or could you not even do that since every single computation requires a button press? – user2258552 Jul 31 '13 at 18:07
  • 1
    Turing completeness is a property of a **system**, not its user interface. Having to "turn the crank" on the web page by pressing keys is not at all a disqualification, no more than having to turn a literal crank would be on a mechanical computer. –  Jul 31 '13 at 18:59