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

71–80 of 89 posts

Re: HTML + CSS3 is Turing complete

#71

Post by scott_s »

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…

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.

Re: HTML + CSS3 is Turing complete

#72

Post by eru »

soamv wrote: post #62
Tichy wrote: post #29

Earlier quoted context omitted.

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

You just need a very hot atom.

Re: HTML + CSS3 is Turing complete

#73

Post by eru »

msarnoff wrote: post #48
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…

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.

Re: HTML + CSS3 is Turing complete

#74

Post by jules »

hasenj wrote: post #45
jules wrote: post #38

Earlier quoted context omitted.

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.

Re: HTML + CSS3 is Turing complete

#75

Post by jules »

samuizo wrote: post #66
jng wrote: post #41

Earlier quoted context omitted.

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…

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.

Re: HTML + CSS3 is Turing complete

#76

Post by kalleboo »

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.

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

Re: HTML + CSS3 is Turing complete

#77

Post by arethuza »

bzbarsky wrote: post #64
jng wrote: post #41

Earlier quoted context omitted.

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

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.

Re: HTML + CSS3 is Turing complete

#78

Post by chwahoo »

bzbarsky wrote: post #64
jng wrote: post #41

Earlier quoted context omitted.

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

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.

Re: HTML + CSS3 is Turing complete

#79

Post by pedrocr »

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…

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?

Re: HTML + CSS3 is Turing complete

#80

Post by ghempton »

apgwoz wrote: post #31
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.

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.

Thats a cool premise for a meetup. Wish there was one in Seattle.
Post reply on HN