44

Programming languages & programs are often said to be Turing complete when it's possible to simulate any Turing machine with it.

I'm now designing a constructed language for my game and I want everything to be possible to say in it. How can I know if the language is "Turing complete", that is possible to say/describe everything using it? What would be the requirements for it? What words does the language need to have to be able to speak in it?

For now, everything I thought about:

  • It's possible to describe the past, the present and the future (ex. "I bought a car", "I'm buying a car", "I will buy a car")
  • It's possible to describe something (words?) (ex. "The cat is red")
  • It's possible to describe nearby area/terrain (ex. "There is a tree")
  • It's possible to describe plans (ex. "I want to buy a car")
  • Any more ideas?
  • 1
    I don't thing a conlang can be comparable to "Turing complete" when existing languages are not. Every year there are new words added to English, and I'd guess the rest of the non-dead (Latin) languages. – Gypsy Spellweaver Feb 6 '18 at 21:14
  • 2
    I don't really understand your question: do you want how to prove Turing Completeness from grammatical feature like past or future? Or do you want to know how to make a Turing Complete language in general? For this latter case, it's trivially easy: just have an "if-then-else" condition and a mean to record information (e.g. your speaker in a conversation), or implement the SKI calculus, which is minimalist and so quasi cost-less – prosopopee Feb 9 '18 at 13:46
  • 1
    @prosopopee This site is not about programming languages and I'm not about asking how to check if a programming language is Turing complete – RedClover Feb 9 '18 at 13:47
  • It has been said that languages differ less in what they can say than in what they must say: some grammars require you to specify (e.g.) the sex of the speaker, or whether an assertion is based on experience or hearsay, while other grammars let these things go unmentioned. – Anton Sherwood Oct 7 '18 at 2:07
38

The best parallel for Turing completeness in human languages is the Natural Semantic Metalanguage. The NSM proposes that there is a limited set of basic semantic concepts which all human languages have, and which are not reducible to other concepts. They call these "semantic primes", because you combine them to get all other meanings, and because they can't be broken down. The list of primes, currently numbering 65, is a work in progress as new primes are proposed and evaluated, but after over 45 years of work on the theory the list has proven to be very reliable and new primes are only rarely proposed.

The NSM is a good guide therefore for judging whether a conlang is "complete" - whether it would be as capable for expressing human thought as any natural language. If a conlang has vocabulary items (they can be words, affixes, or phrases) for each of the semantic primes then I would judge it to be complete.

17

A language doesn't require grammatical structures specifically for expressing something to express it.

In Chinese, there aren't separate future and past tenses. At the same time, it's possible to describe the past, the present and the future. Auxiliary verbs like 要 yào "to want, to be going to" and many others can be used to describe what one would use the future tense for in English.

Grammatical constructs like "but" aren't necessary to convey meaning. We can use words like "caveat", "unfortunately" or "I'm afraid that" instead.

Languages reflect their culture. You should make your game's language reflect the culture that speaks it. If they value respect, add lots of ways of expressing deference, like Japanese.

If you went back in time to 1700s England and attempted to describe the different forms of RNA Polymerase, they would not have a robust understanding of what you meant.

A language is a shared context between the speaker and the listener. The common context allows them to communicate some subset of thoughts the human mind is capable of to each other. No language can communicate every thought- some languages have much less room for ambiguity than English, for example.

A good example is trying to communicate colors to a colorblind alien race. You can teach them about the human optical system all you want, but they will still not understand the sensation of color.

  • 3
    If you went back in time to 1700s England and attempted to describe the different forms of RNA Polymerase, they would not have a robust understanding of what you meant.: I don't think that's true. The language to describe and/or develop a concept of RNA existed back then: As we found it in the future, all materia is made of small discrete units of matter, each bound to .... While it's tough to find the point where to start, and even tougher to inject plausability, logically speaking, the tools existed. Even moreso, given we talk about it today, a path to this language must have existed – Sebastian Mach Mar 14 '18 at 7:53
4

Let's first take note that no actual Turing-complete machine has ever been built, nor can one ever be built. Modern computers are good enough approximations for most purposes, but they are in reality just very large finite state machines. A true Turing machine requires infinite storage space.

The infinite storage space of the Turing machine model is mirrored in the (computationally equivalent) lambda calculus by the capacity to define an infinite number of arbitrarily-named variables. This suggests a natural connection to human languages: the potentially-infinite set of variables in lambda calculus corresponds to the set of words in a human language, while human grammars correspond to the reduction rules of lambda calculus. Transferring that back to the Turing machine model, the infinite storage tape of a Turing machine corresponds to the potential vocabulary of a human language, while the state transition rules correspond to a grammar.

So, the first thing you need to make a human language "Turing complete"--capable of referring to or describing anything that can be referred to or described--is an infinite vocabulary! That's clearly impossible, but like real computers approximate Turing machines, we can approximate a "Turing complete conlang" simply by ensuring there is some way to create new lexical items--either strictly by as-needed de-novo coinage, or oligosynthesis, or whatever other word-formation techniques you like--and then abstract away from the vocabulary and looking at the rules for how that vocabulary is used.

Continuing the analogy, the fact that there are two such radically different formulations for computation that are nevertheless provably identical in expressive power (the lambda calculus and Turing machine--and, in fact, even more different formalisms than that, like the SKI combinator calculus, NAND machines and the One Instruction Set Computer, etc.) suggests that there may not be any single simplest set of grammar constructs that make an abstract language "complete".

Empirically, however, if you put stock in David Gil's work on so-called IMA (Isolating-Monocategorial-Associative) language, the only necessary and sufficient requirement for effective human communication (or as he puts it, enough grammar "to sail a boat") is the existence of a generic "association operator"--a way to say "the things represented by these two sub-phrases are related somehow"--and literally everything else can be handled by pragmatics.

So, you need the ability to introduce whatever words you find that you need in a given situation, and you need at least one operator that can specify arbitrary relations between things (e.g., the generic English preposition "of")--which could have a surface expression as simple as juxtaposition. Everything else is sugar, that just makes figuring out the pragmatic details easier.

  • I think the infinite memory of a Turing Machine is more like the ability to say infinite words. – MilkyWay90 May 31 at 11:33
3

A language communicates ideas. If the set of ideas communicable by your language is large enough that it is adequate for any situation in your game, then it's good enough. No language is able to communicate all possible human thoughts; some conlangs (e.g. Ithkuil) try to expand the set of ideas that it can convey, but it is still not totally encapsulating.

Another thing to think about is conflation. For example, Toki Pona may be effective at communicating a wide range of ideas, but it often conflates or simplifies concepts (the lack of words for specific numbers being an obvious example of this).

  • 4
    "No language is able to communicate all possible human thoughts" All human languages should be able to express all thoughts, just not necessarily well or efficiently. – curiousdannii Feb 7 '18 at 2:02
0

How would we define a Turing Complete language?

First, we would have to compare Turing Machines to languages.
The point of the Turing Machine is that it can do anything computable. Whether be it calculate the additive factorial of a number or calculate exponents, it should be able to do it.
In languages we could define a "Language Complete"1 language to define anything, be it the universe, paper, or the lack of anything.

The "Language Complete" language

Note that it is impossible to prove that a Turing Machine actually does everything computable, as the definition of "everything computable" is too broad, so this language won't have any proof of being "Language Complete".
In order to define everything, we would need a way to communicate arbitrary information to the human mind.
This is exactly what our receptors (senses) do. We can define an entire universe, which means we need a way to define every atom and it's position in the universe.
In order to define an atom, we would need 4 attributes of it: the number of protons, the number of neutrons, the number of the electrons, and it's position relative to a given point in the universe.
Once we have defined the universe, we would need to define the organism taking in input.
We can define the organism using the atom method (listed above). The output would be what the organism thinks.

However, this language would be not Language Complete if living organisms could not think about everything.

Conclusion

This language would be extremely hard, if not impossible, to speak in. However, you wouldn't program in a Turing Machine.

1. If this answer is actually significant, let's just call it MilkyWay90 Complete

-3

Think:

What features does a language you understand fluently have. Does your language contain that?

For example:

In English, we get plurals: apple , apples.

  • Does your language contain a way to use plurals?

In English, we have exceptions to cover things that feel incomplete, or "out of place": James's but James' We have leaves not leafs

  • Does your language contain exceptions to make your language feel "complete" and "tidy"?

it's up to you to think of other examples, but I think that these were some good guidelines to follow.

  • 4
    -1, this is a way of creating relexes, though: Chinese and Japanese get on just fine without marking for plurals, but English lacks the handy honorifics and topicalisation in Japanese. – Darkgamma Feb 6 '18 at 21:15
  • Wrong: Chinese uses them, just in a different form 你,你們 @Darkgamma – VortexYT Feb 6 '18 at 21:18
  • 2
    I am well aware of 我们, 你们, 朋友们, and furthermore the likes of 这些, but these are not a productive system. The same happens in Japanese with some irregulars like 人々, and with pronouns like 私たち; these do not really constitute a grammatical system of plurality marking. – Darkgamma Feb 6 '18 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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