No Stupid Questions

852 readers

2 users here now

There are no stupid questions.

Follow site rules.

Don't be a fascist.

founded 4 years ago

MODERATORS

[email protected]

Is there an equivalent to being "Turing complete" in human languages? (lemmy.ml)

submitted 5 days ago* (last edited 5 days ago) by [email protected] to c/[email protected]

2 comments fedilink hide all child comments

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?

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 3 points 5 days ago* (last edited 5 days ago)

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