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**:

- nop/skip
- x = 0
- x++
- while B
`{ ... }`

- ; (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 (`;`

).