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

61–70 of 89 posts

Re: HTML + CSS3 is Turing complete

#61

Post by lukeschlather »

shasta wrote: post #60
lukeschlather wrote: post #44

Earlier quoted context omitted.

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…

"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 encodin…

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

Re: HTML + CSS3 is Turing complete

#62

Post by soamv »

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…

one atom would be sufficient to encode all possible states

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

Re: HTML + CSS3 is Turing complete

#63

Post by kcl »

sid0 wrote: post #55
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…

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.

Re: HTML + CSS3 is Turing complete

#64

Post by bzbarsky »

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…

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

Re: HTML + CSS3 is Turing complete

#65

Post by sid0 »

kcl wrote: post #63
sid0 wrote: post #55

Earlier quoted context omitted.

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.

Re: HTML + CSS3 is Turing complete

#66

Post by samuizo »

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…

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.

Re: HTML + CSS3 is Turing complete

#67

Post by scott_s »

pnathan wrote: post #13
setnorth wrote: post #7

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

Re: HTML + CSS3 is Turing complete

#68

Post by scott_s »

lukeschlather wrote: post #44
hasenj wrote: post #18

Earlier quoted context omitted.

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

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.

Re: HTML + CSS3 is Turing complete

#69

Post by scott_s »

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.

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.

Re: HTML + CSS3 is Turing complete

#70

Post by scott_s »

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…

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.

Post reply on HN