Turing-complete Languages

Turing-complete languages are languages that share some peculiar characteristics. They can express the full potential and the full power of Turing Machines, thus allowing us to implement any possible algorithm — namely, computable functions. In fact, any computable functions can be implemented as an algorithm: hence it can be implemented using any Turing-complete language. Let’s see what Turing-complete languages are in more detail.

This is part of a series about computability theory.

Characteristics

Turing-complete languages must have the following 5 characteristics:

1. nop/skip
2. x = 0
3. x++
4. while B { ... }
5. ; (composition)

Actually, these are the real-life implementation of the 5 characteristics. However, I find it more convenient to represent them this way: I think it’s easier to remember them. In the following, they are discussed a little more in detail.

1. Nop/Skip

A Turing-complete language must be able to represent an instruction that does… nothing. Microprocessors (CPUs) have indeed this special instruction; in the x86 ISA (Instruction Set Architecture), it is referred to as “nop”.

2. x = 0

This is the assignment. Even though any modern and rich programming language allows the developers to make any assignment/initialization, a Turing-complete language only needs an instruction that assigns value $0$ to a given variable (x, in the example).

3. x++

In order for the previous requirement to work, a Turing-complete language also needs an instruction to increment values. By combining requirements 2 and 3 is then possible to implement what modern languages do with instructions like x = 2, which corresponds to x = 0; x++; x++.

4. while B { ... }

While loops are necessary to allow Turing Machines to diverge. Since TMs implement both total functions and partial functions — and since the latter ones do not always halt —, a while loop instruction is needed to be able to represent them. Function $\lambda x.\uparrow$ is indeed represented as while true {x = 0}. This algorithm never halts and it wouldn’t be possible to implement it without using while loops.

Note that for loops are not enough — not in the strictest sense. For loops can iterate only a finite and definite (known a-priori) number of times, while while loops can diverge. In actual implementations (like those by the C, C++, Java languages etc.) they can diverge as well, since they can have arbitrary conditions.

5. ; (composition)

Turing-complete languages must be able to compose instructions — namely, they allow us to write more than one instruction. Composition is achieved in many different ways; one of the most common ones is by dividing instructions with semicolons (;).