Skip to content

Comment on HTML + CSS3 is Turing completeparent

Comments

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.