-1

Motivated by: Is there a linguistics equivalent to Turing completeness?

Can be natural languages be considered turing complete? Surely on the day to day basis there is a lot of ambiguity that mainly stems from assumptions and pre-build knowledge but given a full context of a language why can't we claim that it is turing complete? That is with a complex enough set of rules we can generate semantically and structurally valid sentences.

| improve this question | |
  • 3
    "That is with a complex enough set of rules we can generate semantically and structurally valid sentences." ← that's not my understanding of what Turing completeness means... – LjL Feb 20 at 23:59
  • 3
    This question is conflating some issues and terms, thereby accruing some terrible answers. Could you go through en.wikipedia.org/wiki/Chomsky_hierarchy to help formulate the question better? – prash♦ Feb 23 at 5:24
5

It is not known whether natural languages are Turing complete. This can only be determined by examining a formalized model for natural language, but there is none available. Chomsky proposed such a formalized model, Transformational Generative Grammar, and it was proven by Peters & Ritchie that this model is Turing complete, so if TGG were a correct theory, the answer to your question would be yes. But, so far as I know, no linguists currently believe that the Chomskian formalization of TGG is correct. But there might be another formalization of TGG that is relevant to this issue. So, even assuming TGG is a good theory, this doesn't really settle the issue.

There are competitor theories to TGG, but usually they are not formalized. An exception is GPSG (Generalized Phrase Structure Grammar), which proposes CFPSG (Context Free Phrase Structure Grammar) as a model, which is known not to be Turing complete. So, if we were to accept GPSG as an adequate model for natural language, the answer to your question would be No, natural language is not Turing complete.

| improve this answer | |
8

No, natural languages aren't Turing complete in the same way onions are not. Quoting Wikipedia:

A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful).

A natural language is, very loosely speaking, a system of interpersonal communication among a group of people. It is not a computational system. Just think about how much sense it makes to ask "Can the Spanish language compute the n'th digit of pi, given n?" Whoever does the computation is a Spanish-speaking person (or maybe a computer system with Spanish messages), but not the language.

| improve this answer | |
  • 1
    I would argue that Spanish language can compute the n'th digit of PI, given n", just the fact you formulated the problem and you can then formulate a solution using English or Spanish that would make it turing complete for that task. E.g. you can give instructions on how to do that in Spanish/English. – Iordanis Feb 20 at 22:29
  • 7
    The problem is that "Turing completeness" is a technical term with a precise meaning. English, being a natural language, doesn't even have a precise definition, so answering whether English is Turing complete requires making a lot of assumptions which are at best tangential to the nature of English as a natural language. – jick Feb 20 at 23:09
  • 3
    @jick Your view is very reminiscent of the argument made by C.F. Hockett in his little book State of the Art. He contrasts the game of professional baseball with an elaborate rule book to settle disputes with "sandlot" baseball, the pick-up game played by young people in a neighborhood, with informal rules and understandings that vary a lot from time to time and disputes are handled ad hoc. He says human language more closely resembles sandlot baseball. TGG is not an appropriate theory, because it takes language to be like professional baseball. – Greg Lee Feb 21 at 13:45
  • 1
    this answer is beating a strawman, loosely speaking, and committing a referential fallacy, like, A computer-network is a system of communication among a group of computers ...; Non-Sequitur: ...It is not a computational system? – vectory Feb 22 at 12:23
  • 1
    Following your logic, programming languages too can not be Turing-complete. The Python language does not do any computation, an interpreter does. – potestasity Feb 25 at 15:14
1

Natural languages are known to be (mildly) context sensitive at best. That being said, some formal models tend to overgenerate, such as TGG mentioned above. Note that constraint-based formalisms, even though they are based on context-free grammars, may be Turing complete. LFG is a case in point, its equational specifications make it formally much stronger than CFG (indicating that it's not a good model).

| improve this answer | |
-1

I think the question is not about Turing completeness but about completeness in another sense: using a human language we can express a lot of formal ideas and theories given enough space.

At the same time, the animals while having complicated signal systems, cannot use their language to express complicated ideas.

It is speculated that prehistoric human languages were in this sense like the languages of animals, people could signal threats, call attention, may be express some more complicated things but their languages were too weak to express general concepts.

Similarly, people who speak different languages can communicate to a certain degree but cannot express more complicated things. And learning language in this situation may require pointing at real things or pictures when articulating, i.e. to use the means of communication outside the languages.

I encountered some claims that there are some isolated human languages which are not complete in this sense, that is it is impossible to communicate general ideas using them, but I am not sure.

That said, even well developed human languages have their limitations. They can communicate only formal ideas and cannot communicate qualia like smells, and even to communicate color the other party has to have had phsysical experience with that color. You cannot communicate what is yellow color to a creature or person who is color-blind, even if they know English very well.

| improve this answer | |
  • 1
    The question already links to the earlier question about general completeness; this one is surely asking about actual Turing completeness. – curiousdannii Feb 23 at 3:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.