Wikipedia’s first paragraph on Turing completeness is this.

In computability theory, a system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. The concept is named after English mathematician Alan Turing. A classic example is lambda calculus.

You know something is a jargon when people use jargon to explain said jargon. This is my attempt to break down these concepts in (relatively) simpler terms.

Turing Machines

In 1936, mathemathician Alan Turing came up with a very simple theoretical computing machine. Despite its simplicity, this machine is capable of any computation, no matter how complicated.

A Turing machine is a machine that runs on top of an infinitely-long tape, which acts like the memory of the computers you know or other forms of data storage. The tape is made up of a long series of little cells, which are uually blank at the start and can be written with symbols.

At any one time, the machine has a head positioned over one of the cells on the tape. With this head, the machine is capable of performing three basic operations:

1. Read the symbol on the cell under the head.
2. Edit the symbol by replacing it with a new symbol or erasing it.
3. Move the tape left or right by one cell to read/write the symbol on a neighboring square.

Note that just because a Turing machine can compute anything, doesn’t mean it can compute anything efficiently. Even simple algorithms you can now write in a few lines in C takes is quite more complex if expressed purely with a Turing machine. That “can compute anything” comes with a caveat: that it might be very hard to write the program, or that it might take a ridiculously long time and/or ridiculously large memory as to be utterly useless in many cases.

Despite those limitations, Turing machines are the very height of technology back in the day. Turing machines soon became very popular, and eventually a standard because they both provided a powerful mechanism to calculate anything and were easy to understand.

The initial version of the Turing machine had just a long single tape. Later on, people came up with the concept of “multiple” tape Turing machines to simplify calculations. Multi-tape Turing machines use two to five tapes with an independently-moving head for each. Since every multi-tape Turing machine has an equivalent single-tape Turing machine, multi-tape Turing machines were not any more powerful than single-tape ones, but they helped to simplify programs.

Turing Completeness

If a physical machine or a virtual machine can take any program and run it just like a Turing machine, then that machine is called Turing complete. Turing completeness is kind of a certification—if something can solve any (solvable) problem, that something is Turing complete.

A good example of a Turing incomplete machine is a calculator. A calculator, whether a cheap calculator your local store uses or that shiny $100 graphing calculator you inherited from your forefathers can only perform a pre-defined set of calculations.

However, the phone or PC or whatever you’re reading this article on is a Turing complete machine because it can do any calculation that a Turing machine can do if given enough time and memory, even though “enough” can mean anywhere from less than a blink of an eye to more than the time it takes to gather enough money from work, buy a new computer, set it up, and run the algorithm.

Turing Completeness and Programming Languages

A Turing machine is just a concept—anything (physical or virtual) that can take any program and run it is a Turing machine. And if that thing can run every program that a Turing machine can run, it’s Turing complete.

A programming language is Turing complete if it can simulate a single-taped Turing machine. In general, for a programming language to be Turing complete, it needs:

1. A form of conditional repetition or conditional jump (e.g. while, if + goto)
2. A way to read and write some form of storage (e.g. variables, tape)

This means that most programming languages you can think of are Turing complete. C, C++, Java, Python, Haskell, Prolog, etc. are Turing complete.

Besides programming languages, there are other systems that if used appropriately can be used to store and compute information. The card swapping and storing mechanic of Magic: the Gathering is another system that would allow you to compute anything given enough cards, enough time, and enough transactions. Other unintentionally Turing-complete systems include, but not limited to Minecraft, Minesweeper, Pokémon, PowerPoint, mov (and only mov) instruction in x86 Assembly, the rules used by the airline industry for determining flight availability, a series of buckets and stones, and the swarming behaviour of soldier crabs.

Turing Incomplete Languages

If a programming language is mainstream, it’s Turing complete. There are, however, several Turing incomplete domain-specific languages. ANSI SQL, regular expressions, data languages (JSON, etc.), and markup languages (HTML, CSS, etc.) are a few Turing incomplete languages you might know.

Like every other piece of software there is, programming languages are about trade-offs. There’s really no benefit for Turing incomplete programming languages that target several application domains, since the flexibility of Turing completeness is a lot more important than its complexity. On the other hand, if you’re not building the “one language to rule them all”, you’re free to implement only features that make sense to the very specific purpose of the language.

Turing Tarpits and Esoteric Languages

Just because a language is Turing complete doesn’t mean you want to use it. Turing tarpits are Turing-complete languages that can compute anything, but writing a program to do it is ungodly difficult. Examples of Turing tarpits and general esoteric languages with Hello world examples include:

• Brainfuck

  ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
  

• FRACTRAN

  5^205469705004861725972941750691144/2
  

• Grass

  wvwwWWwWWWwvWwwwwWWwWWWwWWWWwWWWWWwWWWWWWwWWWWWWWwWwwwwwwwwwwwwWWWWwWWWWWWWwWWWWWWWWWWWWWWwWWWWWWWWWWWwwWWWWWWWWWWwwWWWWWWWWWWWWwWWWWWWWWWWwwWWWWWWWWWWwwwwwwWWWWWWWWWWWWWWWwWWWWWWWWWWWWWWWWWWWWWwWWWWWWWWWWWWWWWWWWwwWWWWWWWWWWWWWWWWWwwWWWWWWWWWWWWWWWWWwwwwwWWWWWWWWWWWWWWWWWWWWwwWWWWWWWWWWWWWWWWWWWWWWwWWWWWWWWWWWWWWWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwwwWwwwwwwwwwwWWwwwwwwwWWWwwwwwwwWWWWwWWWWWwwwwwwwwWWWWWWwwwwwwwwwwwwwwwwWWWWWWWwwwwwwwwwwwwwwwwwwwwWWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwWWWWWWWWWwwwwWWWWWWWWWWwwwwwwwwwwwWWWWWWWWWWWwwwwwwwWWWWWWWWWWWWwwwwwwwwwwwwwwwwwwWWWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwww
  

• Piet (yes, this is code)
  
• Malbolge

  (=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc
  

In conclusion, just because something can calculate anything doesn’t mean you should ever actually try to program with it. Just because you can make crabs solve the Travelling Salesman Problem doesn’t mean you should.

Turing Equivalence

A term you might have also heard is Turing equivalence, which is not the same as Turing completeness. If a machine can compute every computable function that a Turing machine can compute, it’s Turing complete. If every algorithm a machine can compute is computable by a Turing machine, it’s Turing equivalent.

Confused? It’s the difference between “can” and “need”. Basically, a system is Turing equivalent if it’s exactly as powerful as a Turing machine; it can compute everything a Turing machine can and only everything a Turing machine can. Another definition is that a system is Turing equivalent if it can simulate a Turing machine and be simulated by a Turing machine.

Actually, we don’t know if Turing complete is equal to Turing equivalent. They’re equal if the Church-Turing thesis is true, which is another can of worm’s I’m not willing to explain without its own article. All known Turing complete systems are Turing equivalent though, which supports the thesis.

TL;DR

If something can run any algorithm, it’s Turing complete. Yes, even crabs.

---

References, in no particular order:

• Wikipedia, obviously
• freeCodeCamp’s much better attempt at explaining this
• University of Cambridge’s and ScienceBlogs’ explanation on Turing machines
• Redditors attempting to explain Turing completeness to a five-year old
• This StackExchange thread on minimum Turing completeness
• This Reddit thread and this article on accidental Turing completeness
• Esolang Wiki for all your esoteric language needs
• This StackOverflow answer on Turing completeness which sparked a debate on Turing completeness and Turing equivalence