Good Math

Turing Complete, or Completely Pointless?

So how is the BF machine Turing complete? Let’s look at its features in terms of the four criteria for being Turing complete.

• Storage: BF has an unbounded tape. Each cell on that tape can hold an arbitrary integer value. So the storage is obviously unbounded. It’s tricky to work with, because you can’t reference a specific cell by name or by address: the program has to be written to keep track of where the tape head currently is and how to move it to get to the location of the value you want to look at. But when you think about it, that’s not really a restriction. In a program on a real computer, you need to keep track of where everything is—and in fact, most programs are written to use relative addresses ...