Skip to content

Comment on HTML + CSS3 is Turing completeparent

Comments

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.

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

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.