Proving Befunge-98 is Turing Complete
Befunge is an esoteric programming language based around a two dimensional playground. Rather than trying to describe it, let’s just look at an example:
v v . <
>"!ereht olleH" > : |
@If you put this program into a befunge interpreter and pressed run, it would output “Hello there!”.
To follow how this program works, all you do is (starting from the top left and moving right) look at one character at a time and follow it’s instruction. So, this program starts with the instruction v, meaning “instead of moving right, move down”. So, we move down and then see > (move right). Then we have a ", followed by some letters, followed by another ". The " just means everything up to the next " will be put onto the stack.
What is the stack? It’s a space where you can store values - but you can only ever access the top element. This is why we write “Hello there!” backwards - when we put stuff on the stack, we put it on top of everything else. So if we put our string on backwards, then the top of the stack will be H, underneath that is e, after that is l and so on.
Now we come to the interesting part of the program - the loop. Firstly, we have a > - since we’re already moving right, we don’t really need this right now, but we’ll use it later. Next is :, which means “duplicate the top element on the stack”, then | which means “take the top element off of the stack. If it was 0, go down, otherwise go up”. Since our top of the stack is H, which isn’t 0, we go up. Next is < (go left) followed by ,, which means “take the top element off of the stack and print it out (as a character)”. Since our top element is H (remember, we duplicated it earlier so we could use it twice), this will output H and remove it from the top of the stack. We then see the v instruction, which takes us back round the loop. So, we keep looping round and round, printing out characters until we run out of them. Once we’re out of letters, the top of the stack is 0, so when we encounter the | instruction, we’ll go down and hit @, which stops the program.
Turing
Befunge is a pretty interesting language - it’s quite limited and it can be quite challenging to write programs in it. But can you write all programs in it?
The notion that you can use a system to compute any program is known in mathematics as “Turing Completeness”. There are a variety of ways to prove that any particular language is Turing Complete, but today I’ll be using one specific method: µ-recursive functions.
µ-recursive functions are precisely the functions required in order to prove that a language is turing complete. So let’s get started!
But first, a notation issue - befunge doesn’t have official functions because there’s no way to pass arguments. For each of these definitions, I’ll be assuming that the stack consists of the number of arguments and then the actual arguments to the function, then nothing else.
Initial functions
1. Constant Function
The constant function takes any amount of input, and returns a particular number, ignoring all its inputs. This has to be defined for any natural number. Since we can’t give functions names in befunge, we’ll say that the version of the constant function has to be specified in the arguments.
$03pn03g