O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required