loading...
Cover image for What makes a programming language Turing complete?

What makes a programming language Turing complete?

gruhn profile image Niklas Gruhn Updated on ・3 min read

Turing completeness is a concept from theoretical computer science. It tells you how powerful a programming language is. Not in terms of performance or maintainability or how rich its ecosystem is. A programming language is Turing complete if you can implement any possible algorithm with it.

Think for example of pure HTML. You simply can not implement merge sort with HTML (add CSS and you can, haha!). Thus, HTML is not Turing complete.

Now you might think you have to get clever to design a programming language capable of running any possible algorithm. Especially because most introductions to Turing completeness will throw a hole bunch of mathematics at you. However, most programming languages out there are Turing complete and if you were to create your own programming language you would probably make it Turing complete by accident.

In fact a lot of stuff that's not even a programming language later on turned out to be Turing complete. For example Minecrafts redstone blocks, Conways game of life, the animation feature in PowerPoint and more.

Yes, that means you can entirely implement Googles search algorithm with PowerPoint animations.

That sounds crazy, right? How am I supposed to even... you know... make HTTP requests and so on. But that misses the point. Turing completeness is about something much deeper. Whether or not you can make HTTP requests or access the file system is not a property of the programming language itself. It's a question about the APIs that are provided with it.

Think of JavaScript. In the browser you don't have direct access to the file system. In Node.js you have. Same programming language. Different APIs.

Let's dive a little bit deeper into what really distinguishes Turing complete and non-Turing complete programming languages.

Consider the following programming language with only these syntax features:

n = 1 + 1

loop n:
    # ...

We can use addition, variable assignment and a loop. That's it! Note that no matter what's happening inside the loop, for n = 10 it will run exactly 10 times. Not more, not less.

With this programming language we can already implement nearly everything.
We literally don't need anything else. Not even the other arithmetic operators (-, *, /). We can emulate them all with just loops and addition.

Here is how you could emulate an if-else-block:

if n > 0:
    # ...   
else:
    # ...
n_if = 0
n_else = 1

loop n:
    n_if = 1
    n_else = 0

loop n_if:
    # ...

loop n_else:
    # ...

And here is how you could implement subtraction:

x = x - 1
y = 0

loop x:
    x = y
    y = y + 1

Of course it's ridiculous to program like this but remember that we don't care about performance or readability. We are just interested in what's possible in principle.

Our programming language is very capable but notice that it's impossible to make infinite loops. We can use multiple loops, we can use nested loops but each loop will always have a fixed and finite number of iterations. Thus, it's completely impossible to make an infinite loop.

That's why this language is not Turing complete.

Let's introduce a new kind of loop to our programming language:

for i until n:
    # ...

i is incremented after each iteration and the loop continues as long as i < n.

Now, we can make infinite loops. Just keep reseting i so it never reaches n:

i = 0

for i until 2:
    i = 0

Our programming language just became Turing complete! Even if we are restricted to only use the for-loop once in an entire program, the language is still Turing complete.

Infinite loops are not very impressive. Most of the time we probably want to avoid them. What really makes the for-loop powerful is that we can control how long a loop runs from within the loop itself.

A program somewhat controlling it's own flow. That's the key feature that makes a programming language Turing complete. By the way, we don't necessarily need loops for that. The same thing can be achieved with recursion, GOTO-statements or a crazy thing called the Y combinator.

Discussion

pic
Editor guide