Hacker Newsnew | comments | show | ask | jobs | submit login

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.

-----




Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: