Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

HTML + CSS3 is Turing complete

github.com

Post reply on HN
Print view View original

41–50 of 89 posts

Re: HTML + CSS3 is Turing complete

#41

Post by jng »

hasenj wrote: post #37
jules wrote: post #19

Earlier quoted context omitted.

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.

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

Re: HTML + CSS3 is Turing complete

#42

Post by amalcon »

hasenj wrote: post #18
elitheeli wrote: post #6

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…

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

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.

Re: HTML + CSS3 is Turing complete

#43

Post by kcl »

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.

Re: HTML + CSS3 is Turing complete

#44

Post by lukeschlather »

hasenj wrote: post #18
elitheeli wrote: post #6

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…

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

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.

Re: HTML + CSS3 is Turing complete

#45

Post by hasenj »

jules wrote: post #38
hasenj wrote: post #37

Earlier quoted context omitted.

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

Re: HTML + CSS3 is Turing complete

#46

Post by lmkg »

Tichy wrote: post #29
elitheeli wrote: post #6

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…

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 cl…

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

Re: HTML + CSS3 is Turing complete

#47

Post by dmm »

kcl wrote: post #43

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…

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

Re: HTML + CSS3 is Turing complete

#48

Post by msarnoff »

elitheeli wrote: post #6

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…

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.

Re: HTML + CSS3 is Turing complete

#49

Post by timtadh »

jng wrote: post #41
hasenj wrote: post #37

Earlier quoted context omitted.

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.

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…

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

Re: HTML + CSS3 is Turing complete

#50

Post by doyoulikeworms »

nkassis wrote: post #30
mrspeaker wrote: post #16

Earlier quoted context omitted.

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.

It's Turing machines all the way down.
Post reply on HN