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

51–60 of 89 posts

Re: HTML + CSS3 is Turing complete

#51

Post by anorwell »

dmm wrote: post #47
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?

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.

Re: HTML + CSS3 is Turing complete

#53

Post by sid0 »

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…

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.

Re: HTML + CSS3 is Turing complete

#54

Post by johnzabroski »

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…

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.

Re: HTML + CSS3 is Turing complete

#55

Post by sid0 »

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?

Re: HTML + CSS3 is Turing complete

#56

Post by sid0 »

ssp wrote: post #52

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.

Re: HTML + CSS3 is Turing complete

#57

Post by ssp »

sid0 wrote: post #56
ssp wrote: post #52

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.

Re: HTML + CSS3 is Turing complete

#58

Post by jgv »

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.

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

Re: HTML + CSS3 is Turing complete

#59

Post by sid0 »

ssp wrote: post #57
sid0 wrote: post #56

Earlier quoted context omitted.

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

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

Re: HTML + CSS3 is Turing complete

#60

Post by shasta »

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…

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

Post reply on HN