HTML + CSS3 is Turing complete | Hacker News Reader

HTML + CSS3 is Turing complete

github.com

152 pointsbgruber87 comments

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

Also, I haven't tested it on anything besides the latest Chrome on Mac.

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.

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.

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.

inside a dream, inside another dream!

May be more true than one might think: http://www.simulation-argument.com/

It's Turing machines all the way down.

Well, really, it's what happen when you make an impression at Hack and Tell (http://hackandtell.org)! This was perhaps the highlight of last night's Meetup.

It's true. This was definitely the best presentation at last nights hack and tell. A pleasant surprise to see this on HN today.

Thats a cool premise for a meetup. Wish there was one in Seattle.

start one! and ping me if you do. i'll do ny best to help promote it.

If you start one, I'll attend.

All of this is running inside a VM inside another VM

> No real-world thing can actually be Turing complete

But when you say Turing-complete, I assume something along the lines of "a programming language can be built on top of it and you can create interactive applications using such a programming language instead of javascript".

It seems like that's not the case at all.

Then you assumed a falsehood. Turing completeness is a mathematical concept that has nothing to do with interactive applications.

No, mathematically nothing is "Turing Complete". The only usefulness of saying that something is "Turing Complete" is in knowing that you can treat it as if it was a normal computer for all intents and purposes.

So mathematically a laptop is not Turing Complete, but for all practical purposes, it is.

Also incorrect. Counterexample: Turing machines are Turing complete. You are correct that a laptop is not Turing complete, though.

Seriously? It's obvious I meant "nothing real is mathematically Turing complete".

I know, I answered (incorrect) nitpicking with (correct) nitpicking.

Nope. The common usefulness is to determine whether a given computation-describing system reaches the threshold of universal computability. Modulo finite size is assumed, else there is no usefulness of the concept given finite resources.

For example, SKI combinators are Turing-equivalent. Regular expressions aren't. The lambda-calculus is. Context-independent grammars probably are. Most data description languages are not.

This is worthy of an HN post because a style-description language would not normally be expected to be Turing-equivalent.

When it became widely known that the C++ template system was Turing-equivalent, it was a shock to many. These meant that the C++ compiler code itself could be exploited to compute arbitrary things such as factorials, or shortest-paths in graphs using A*.

Actually, as the SKI system demonstrates, the threshold is quite low. The core needed components are just "constant" or "if" (they are often equivalent), and "repeat" (equivalent to both "iterate" and "recurse").

>Context-independent grammars probably are.

No they are not. Recursively Enumerable grammars are however. A context free grammar can't be turning complete because it can be decided with only a PDA.

> because a style-description language would not normally be > expected to be Turing-equivalent.

Wouldn't it? XSLT, the only other style-description language in anything like common use on the web, has been Turing-complete for a while now (possibly since it started existing; I'm not familiar with the history)...

XSLT is the transformation part of XSL (hence the T), meant for transforming XML into other formats, including things like XSL-FO which is the formatting part of XSL. As it is a general purpose language (with iteration, recursion and conditionals) it's not that surprising that it is Turing-equivalent.

XSL-FO is the formatting part of XSL (i.e. the bit most like CSS) - I'd be pretty surprised if this was shown to be Turing-equivalent.

XSLT performs transformations (i.e., takes input and produces output). This sounds to me like a "program" so I wouldn't be surprised that a language like XSLT might be Turing complete.

HTML and CSS are much more "static" in flavor (hence the OP's use of the term "descriptive") and so it might be more unexpected that they can perform universal computation.

I could be mistaken, but I think there's a fundamental distinction between the computing power required to recognize a language and the kinds of functions a language can compute. AFAIK (which isn't much), usually the distinction between regular, context-free, context-sensitive and recursively-enumerable languages turns on the power of the recognizer rather than the power of the language to express functions. In other words, the languages are limited in their syntactic expressivity but not their semantic expressivity. I've always understood the latter to be the key to determining the computational power. Take lambda calculus as an example. It is Turing complete, but it is amenable to a context-free syntactic implementation (see http://www.soe.ucsc.edu/classes/cmps112/Spring03/readings/la...). For C++, I always thought it was that not only is it capable of expressing semantically any computable function, but that a [EDIT: Turing Complete] parser was required to parse C++ strings.

You are right that the power necessary to parse a language is completely different from the power of the language itself.

There is however a different correspondence between recognizing things and computing functions. If we encode a function as taking a bit string as input and generating a bit string as output, we can turn it into a series of recognition problems as follows: "recognize given S as input, whether bit i of f(S) is 1".

Given all these recognizers, we can compute the function, and given a method to compute the function, we can implement the recognizers.

That is, you can reformulate the question "is f computable" to a series of language recognition problems.

The concept of Turing Complete does not apply to a laptop because the laptop itself is not a means to express computation. It is a means to execute computations. There is a difference. Turing Complete is a statement about the computational generality of languages. (Or, even more general, formalized processes.)

What you mean to say is that a laptop is not an actual Turing machine, but for all intents and purposes, it is. On that point, I agree.

When I say "Turing complete", I mean Turing equivalent to a Turing machine. Since there are infinitely many Turing machines but I'm pretty sure humanity has access to a finite amount of state. I mean it strictly in the theoretical sense.

>I'm pretty sure humanity has access to a finite amount of state

There is at least one man out there who isn't:

http://en.wikipedia.org/wiki/Omega_point_(Tipler)#The_Omega_...

I doubt I'll be drinking that koolaid to be honest.

There's plenty of things that are Turing Complete but that shouldn't be used for interactive applications.

http://en.wikipedia.org/wiki/Brainfuck

http://en.wikipedia.org/wiki/Template_metaprogramming

http://en.wikipedia.org/wiki/Turing_machine

and now apparently HTML + CSS

Model railways are turing complete.

http://www.monochrom.at/turingtrainterminal/pictures_eng.htm

Is it not possible to write a C compiler that outputs Brainfuck code that can be executed inside a Brainfuck interpreter?

What people usually mean by "Turing complete" is "would be Turing complete if it were infinite." That does imply that a programming language can be built on top of it, and that programming language is fully capable of performing any given algorithm.

It says nothing about interactivity, which is a function of ability to (directly or indirectly) access I/O hardware.

Everyone's being a little cagey about what Turing Completeness really means, in layman's terms, because I think the assumption is that if you're here, you should already have a deep understanding of it.

So no, as others have said, you are completely off base as to what the significance of being Turing complete is. What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable. (I won't get into what computable means, for that you will need to read and reread the relevant Wikipedia articles, along with a good book on Theory of Computation and probably a good one on Abstract Algebra.)

But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I could write a piece of HTML + CSS that your program will be unable to say anything about.

However, this particular proof actually only shows HTML + CSS is equivalent to a Linear Bounded Automaton, which unlike a Turing Machine can be predicted. And strictly speaking, even if you have a Turing-machine-equivalent language like C++, you can theoretically make some predictions about programs provided you can bound its memory, i.e., on a machine with less than 4 GB of memory, it is equivalent to a Linear Bounded Automaton. Now, of course actually writing a second program to do this may be impossible to do before the heat death of the universe, because Linear Bounded Automatons are still very powerful computing objects.

"But the real significance of this is that you cannot write a program that can tell you meaningful facts about the behavior of an arbitrary Turing machine. For any program you write to determine the behavior of HTML + CSS, I can write a piece of HTML + CSS that your program will be unable to say anything about."

Sorry, but this is false and for similar reasons is not reasonably considered Turing complete. The encoding presented here produces, for any particular HTML + CSS, a finite number of cells of an automata (and not only that, the number of cells is linear in code size). That means that deciding any property about a given piece of code amounts to search over a finite space.

This is very different from true Turing completeness where a small set of rules might require unbounded space and computation to decide, and in general will not even be decidable. Now, the author of this code says in a parent post that we can't build a real Turing machine. That's true, but doesn't mean that we can't specify a real Turing complete process; it just means that for some executions we have to give up on running them.

In some cases, it makes sense to consider languages that are not actually Turing complete as approximately Turing complete. For example, if you take the C programming language, with a 64 bit memory space, then again there's technically only a finite space of possible program states. But in that case, you can have a 100 line C program that can generate 2^64 possible program states. Turing completeness is a reasonable approximation. If you had to allocate every bit of memory explicitly with a unique line of C code, it would no longer be very reasonable to consider C approximately Turing complete.

Yes, you're right, I've edited my post a bit to make it clearer that HTML+CSS is not Turing complete.

What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable.

Change "simulate" to "compute" and I agree fully. I don't think it's necessary to introduce the concept of simulation. If a language (or process, mechanism or whatever) is Turing Complete, then you can use it to express all things computable. Given sufficient resources, that expression could actually do the computation.

edit: I recalled in a sibling post why simulation comes up, and I think it's a source of confusion. The easiest way to prove a formalized process is Turing complete is to simulate a Turing machine. Since a Turing machine can compute all that is computable, and your process can simulate a Turing machine, your process can compute all that is computable. Hence, it is Turing complete.

Looking through the Wikipedia page for LBAs, they're a Turing machine where the tape is limited to a linear function of the size of the input. This is still beyond what realistic computers are since the tape would still need to be infinite to hold as big of an input as you want to feed into it.

Aren't practical computers just simply Finite State Machines?

Aren't you confusing computability with Godel's incompleteness theorem?

I always find the "finite number of atoms" argument a little misleading. Isn't it rather a question of how well we can measure things? If we could measure at infinite precision, one atom would be sufficient to encode all possible states we could dream of. I suppose quantum theory puts a lower limit on the attainable precision of measurements, but I don't know the details.

I must admit that since HTML+CSS3 requires clicks (at least in this implementation), I don't consider it to be really proven to be touring complete.

We simply do not have enough information on the nature of reality to decide who is right here.

If space-time does turn out the be physically discrete at the planck length, and the limits of our measurements are actually reflecting the universe's true discontinuous nature, then this would imply that there would be a limit to how much state you could push into an atom.

Any real physicists please feel free to shoot me down in flames here. This is just my (plainly) limited understanding of the situation.

There are actually physical laws somewhere in thermodynamics that place an upper bound on the existence of information within a space. Oddly enough, the maximum information in a space is proportional to the surface area, not the volume[1]. Black holes attain this maximum, although I'm not sure if non-black-holes are capable of attaining it as well.

In a related note, Bell's Theorem (along with a few experimental results) demonstrate that no theory of (local) hidden variables can account for quantum theory[2]. This means that the limit is not just on our ability to measure the information in an atom. It literally doesn't exist for us to measure. Quantum mechanics is confusing =P.

[1] Specifically, the information measured in binary bits is bounded by the surface area divided by four. I'm not 100% sure what the unit of surface area is, but I believe it's Plank units.

[2] http://en.wikipedia.org/wiki/Bells_Theorem

one atom would be sufficient to encode all possible states

http://en.wikipedia.org/wiki/Bekenstein_bound

You just need a very hot atom.

Haha :) It would still be finitely hot, though.

As I point out here (http://news.ycombinator.com/item?id=2302695), there is a difference between a formalized process for expressing computation being Turing complete, and implementing an actual Turing machine. The first is possible, and most general purpose programming languages are Turing complete. The second is impossible, for obvious reason.

Perhaps the confusion comes from the fact that the easiest way to prove a formalized process is Turing complete is to express a simulation of a Turing machine.

steal karma

Seriously, what the fuck? This is just too much exaggerated.

sorry eli, this was just too cool not to share.

I've never been happy with the hand-wavy, almost circular definition of Turing completeness. We all know the "simulating a Turing machine/computing any function" bit, but what does that really mean? From a practical standpoint, what does a language need to be Turing complete? What key concept separates things like HTML and regular expressions from "real" programming languages?

I believe Petzold said this concept was controlled repetition. Conditionals and loops/jumps/recursion. This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.

This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.

That's like saying that my computer isn't a Turing machine (modulo finiteness of memory) because I need to plug it into a socket to run it. Turing machines are a very abstract notion of computation (and one of the most general ones we know of), and a lot of things can be used to simulate one. Turns out HTML+CSS3 is yet another such thing.

If you don't like `Turing complete', use `Lambda-calculus isomorph', or `Post-correspondence-system isomorph'.

Turing completeness is not hand-wavy, or circular.

Or look up SKI-calculus (http://en.wikipedia.org/wiki/SKI_calculus), if you want to be gob-smacked.

Neat! I posted it to Lambda the Ultimate front page. Been awhile since a cool/wacky hacker project got a front page item. Used to happen all the time 5 years 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.

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.

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.

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.)

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?

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.

> 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?

Language: http://en.wikipedia.org/wiki/Formal_language

Decision problem: http://en.wikipedia.org/wiki/Decision_problem

Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts

These are fairly foundational concepts when talking about computational complexity.

> 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?

unless you strangely accept the idealization of a "hand pressing tab space"

Why is that stranger than my computer requiring electricity to run?

Our field is founded on the idea that mechanical computation is preferred to human computation.

Heh, you should look up what "computers" meant from the 17th century right until World War II. Our field is founded on the idea that machines have the same power as humans working like machines, and that that power's the most a machine (or a human working like a machine) can have.

So would HTML+CSS+two drinky birds tapping the keys a'la Homer Simpson count?

I'm still unsatisfied with your definitions because you're not separating the concept of the expression of a computation from the execution of that computation. A formalized process (read: language) is Turing complete if it can express the simulation of a Turing machine. Since we know a Turing machine can be used to compute anything that is computable, we then know our formalized process can compute all that is compute - it is Turing Complete.

Programs cannot be Turing complete. The concept does not apply, just as a basketball cannot be sad. Programming languages can be Turing complete. A robotic Lego "Turing machine" is not Turing complete, but not because it's not a realization of a Turing machine, but because it's not a formalized process. Robotic Legos, however, would be Turing complete, since that is the formal process used to simulate the Turing machine.

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)

Turing. Not 'touring'. Please, it was right up there in the headline.

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.

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.

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.

Link: http://www.ioccc.org/2001/ (herrmann1 files)

Sorry, you're totally right. My bad.

"eval", followed by whatever chars are required to get a string.

I think you mean "the minimum to get a Turing Machine", which is not the same. But I am being pedantic. Very, very pedantic. As befits the topic. :)

But what's in that string? That still counts. What I should have done was put an additional restriction on what IO is available. Otherwise, something like "eval `cat f`" or something could be all powerful.

My first attempt shows Ruby simulating a cyclic tag system with only 15 unique characters including newlines and spaces: https://github.com/elitheeli/oddities/raw/master/only_a_few_...

EDIT: down to 14 characters.

"But what's in that string? That still counts."

Sure, but it counts regardless of what you're talking about. We don't generally talk about charging data against the TM because they all need data of some sort to do anything interesting. "eval" still gets you there. (Pedantic.)

I should have phrased as "what is the minimum number of characters that need to be seen by a Ruby parser in order to have something Turing equivalent to Ruby without a limited character set?"

As in the minimum character set? As of 1.9.2, you can do lambdas with a = ->(x){do stuff} and call them with a[3]. So I think you could probably translate to SKI calculus using only: (){}->[]

Since SKI gives you lambda calculus, and the lambda calculus is turing complete, you might win that way. :)

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

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.

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.

"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.

http://jsbin.com/owehi4/

I don't understand .. explain?

EDIT: part of not understanding is I ran it in firefox 3.5 -- not good. works better in chrome.

http://lmgtfy.com/?q=Rule+110

Personally, mind == blown. That is awesome.

http://en.wikipedia.org/wiki/Rule_110

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.

Reply on news.ycombinator.com