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

21–30 of 89 posts

Re: HTML + CSS3 is Turing complete

#21

Post by jerf »

elitheeli wrote: post #14
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…

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.

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

Re: HTML + CSS3 is Turing complete

#22

Post by kenjackson »

samdk wrote: post #12
CJefferson wrote: post #4

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.

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…

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?

Re: HTML + CSS3 is Turing complete

#23

Post by elitheeli »

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.

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.

Re: HTML + CSS3 is Turing complete

#24

Post by KeithMajhor »

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.

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

Re: HTML + CSS3 is Turing complete

#25

Post by elitheeli »

Xk wrote: post #17
elitheeli wrote: post #14

Earlier quoted context omitted.

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.

Sorry, you're totally right. My bad.

Re: HTML + CSS3 is Turing complete

#26

Post by elitheeli »

jerf wrote: post #21
elitheeli wrote: post #14

Earlier quoted context omitted.

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.

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

Re: HTML + CSS3 is Turing complete

#27

Post by sgentle »

elitheeli wrote: post #14
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…

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.

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

Re: HTML + CSS3 is Turing complete

#28

Post by JonnieCache »

KeithMajhor wrote: post #24
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.

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

Re: HTML + CSS3 is Turing complete

#29

Post by Tichy »

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 clicks (at least in this implementation), I don't consider it to be really proven to be touring complete.

Re: HTML + CSS3 is Turing complete

#30

Post by nkassis »

mrspeaker wrote: post #16
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…

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.
Post reply on HN