this post was submitted on 08 Apr 2025
7 points (100.0% liked)

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
 

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?

top 2 comments
sorted by: hot top controversial new old
[–] [email protected] 5 points 4 days ago

I guess something similar would be if a language can be used to convey any possible message. I'm reminded of the constructed language, Toki Pona, that only has 137 words. It's a bit of an exercise, but anything can be translated into Toki Pona. The idea behind it was to have a language that forces someone to describe things in the simplest terms while still allowing the person to express themselves fully.

If you wanted to stick with the mathematical definition of "can the language be used to describe any possible algorithm?" then I'd say every human language already is. How else would text books teach programming?

[–] [email protected] 3 points 4 days ago* (last edited 4 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