2w ago

Is there an equivalent to being "Turing complete" in human languages?

If a programming language is Turing complete, it means that you can write any algorithm in it and basically do everything that the computer is capable of doing, barring things like the process not having the privilege to access the APIs for doing something.

Is there an equivalent concept in language languages? Something like the ability to write down instructions for doing everything a human can do?

3 comments

Turing’s Turing completion and Chomsky’s recursive enumerability are equivalent to each other, and I think human languages are recursively enumerable, but I haven’t investigated to confirm this. Actually I know that they are capable of recursive enumeration, I just don’t know whether they’re somehow even more complex/powerful than that, in a way that might set them outside of the Chomsky hierarchy, but I highly doubt it. So as far as I know, Turing complete is a technically correct answer, but in the context of language, recursive enumerability is a more apt term. https://en.wikipedia.org/wiki/Chomsky_hierarchy