HTML + CSS3 is Turing complete

Re:HTML + CSS3 is Turing complete by setnorth on Tuesday March 08, 2011 @10:21AM (#2301149)

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)

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by elitheeli on Tuesday March 08, 2011 @10:33AM (#2301201)

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.

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by sgentle on Tuesday March 08, 2011 @11:35AM (#2301478)

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

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by Xk on Tuesday March 08, 2011 @10:52AM (#2301294)

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.

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by mchouza on Tuesday March 08, 2011 @11:08AM (#2301358)

Link: http://www.ioccc.org/2001/ (herrmann1 files)

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by elitheeli on Tuesday March 08, 2011 @11:15AM (#2301390)

Sorry, you're totally right. My bad.

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by jerf on Tuesday March 08, 2011 @11:11AM (#2301370)

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

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by elitheeli on Tuesday March 08, 2011 @11:18AM (#2301405)

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.

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by jerf on Tuesday March 08, 2011 @12:29PM (#2301736)

"But what's in that string? That still counts."

Sure, but it counts regardless of what you're talking about. We don't generally talk about charging data against the TM because they all need data of some sort to do anything interesting. "eval" still gets you there. (Pedantic.)

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by elitheeli on Wednesday March 09, 2011 @11:58PM (#2308121)

I should have phrased as "what is the minimum number of characters that need to be seen by a Ruby parser in order to have something Turing equivalent to Ruby without a limited character set?"

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by pnathan on Tuesday March 08, 2011 @10:30AM (#2301190)

Turing. Not 'touring'. Please, it was right up there in the headline.

[ Parent | on HN ]

Re:HTML + CSS3 is Turing complete by scott_s on Tuesday March 08, 2011 @04:26PM (#2302657)

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.

[ Parent | on HN ]