Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yes it is:

http://news.ycombinator.com/item?id=2300836

https://github.com/elitheeli/oddities/blob/master/rule110-gr...

in combination with HTML at least...

(Although as others have stated this game is really just a state machine)



Important detail: only in combination with an arbitrarily large HTML file, and only with arbitrarily many user interactions (i.e. the user needs to manually increment the state).

As such it's a pretty meaningless type of turing completeness. So, whereas in general it's undecidable whether a program completes (the Halting problem) if it's written in a turing complete language, for the case of HTML+CSS it may well be decidable for several reasons. Firstly; because the HTML file will be of limited (and in practice small) size, and secondly, because the interesting question is whether you can reason about the state _now_; not whether the document might reach arbitrarily many states were the user to perform infinitely many interactions.

Turing completeness makes hard to reason about a program; and indeed the weaker a language the easier it can be to reason about it - or, more practically - the easier it can be for the browser to determine boundary conditions and to simplify interpretation of the page. Indeed, ironically, Tim Berners-Lee points out the advantages of using weak languages: http://en.wikipedia.org/wiki/Rule_of_least_power

Saying that HTML+CSS is turing complete is kindof like saying finite state automatons are because the number of states is unbounded. That's entirely beside the point however; the point is that I can evaluate a _given_ FSA without turing completeness, not that an arbitrarily large FSA might take arbitrarily many execution resources (I mean, well duh).

Any given HTML+CSS combo is thus bounded in two ways; both by its own size, and by the fact that I don't care about eventual possible states reachable after infinite user interaction but just about the current state (or states very close to the current state).




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: