0

This is Wikipedia's definition of Turing completeness. In simpler terms, a programming language is Turing complete if any program that could theoretically be executed by a computer can be programmed using that language. Nearly all programming languages you have heard of are Turing complete. Keep in mind that this is a theoretical concept, assuming infinite computational resources, which is not very realistic.

Defining Natural-Turing Completeness for Natural Languages

I am exploring the idea of a concept analogous to Turing completeness in natural languages, which I call Natural-Turing Completeness (I'm not great at naming things). My definition is as follows: A natural language is Natural-Turing complete if it can convey any information or meaning that could be communicated through words.

Core Question

What is the irreducible set of features necessary for a language to be Natural-Turing complete?

For example, features like grammatical gender might be redundant for our purpose since some languages without gender distinctions can still convey the same information as gendered languages by using additional words when necessary. Assuming infinite resources (e.g., conveying the word "apple" might take 10 million words, similar to the computational assumptions of infinite memory and time), what are the essential linguistic building blocks required? What is the bare minimum needed for a language to be considered Natural-Turing complete?

Improve this question
2

1 Answer 1

Reset to default
1

The core component needed is recursion.

This is actually pretty similar to Turing completeness in computer science, which requires (informally, for a somewhat "normal" programming language) some way of doing arithmetic, some way of doing comparisons, and some way of iterating without bound. Recursion is one way of satisfying that last component.

In linguistics, recursion is the key to expressing an unbounded number of things. Broadly, recursion involves combining a unit of some type with a unit of another type, to make a unit of the first type. For example, you could combine a noun phrase ("dog") with an adjective ("big") to make a larger noun phrase ("big dog").

As long as the output type matches one of the input types, this gives you an unbounded number of possible expressions. Once you have that, humans are very good at assigning meanings to things: look at the conlang (constructed language) toki pona, for example, which challenges people to express anything they want to say with approximately 120 base words. Turns out you don't need very many basic atoms; all you need is a sufficiently expressive way to combine them!

Notably, this would imply that you can express any possible meaning with a context-free language (Chomsky type 2). Natural human languages are generally context-sensitive (Chomsky type 1). But formal semantics tends to stick to context-free languages, so I'm not aware of any semantic proposition that can't be expressed in a context-free way.

Improve this answer
5
  • I agree with everything said in the literal sense in this question, but I disagree with the implicit conclusion / this given as an answer to the OP - that this means that Toki Pona (or any other language) is capable of expressing any meaning conveyed in any other language!
    – apropos
    Commented Oct 19 at 2:14
  • The meaning of a morpheme in one language is impossible to fully express in another, IMO. Take the OP's "apple" example: apple in Toki Pona would idiomatically translate as kili, with what sort of fruit it represents implicit in the context. You could add content words to it ad nauseum to approximate the meaning of an apple (kili loje, kili loje sike, ...) but one could always construct a counterexample: something satisfying all the expressed features of an "apple", yet that is not an apple.
    – apropos
    Commented Oct 19 at 2:15
  • 2
    @apropos Sure, but natural languages (as opposed to toki pona) develop new lexical items over time as needed, and people can agree on their definitions. Even in toki pona, using the language accurately means understanding that e.g. tomo tawa means "vehicle" even though that's not obvious from the meanings of tomo + tawa.
    – Draconis ♦
    Commented Oct 19 at 3:35
  • Oh, I see where you are coming from. It's less so about the literal meanings of tomo + tawa and more so about having a way to generate an infinite amount of lexical entries?
    – apropos
    Commented Oct 19 at 4:52
  • 1
    @apropos Exactly—given a way to compose those, people will. And then you can define your new lexemes using as many words as necessary to get them into the common ground.
    – Draconis ♦
    Commented Oct 19 at 5:30