O'Reilly logo

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold

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

7  Also Known as Subroutines

Every programmer knows that certain types of tasks are frequently encountered in almost all programming jobs. Sometimes the tasks are identical; more often they turn up with some variations. Even within the square-root-of-2 machine, several m-configurations were rather similar. For example, look at these three:

images

These m-configurations all move the head left in a loop until the sentinel is encountered. Then the head is moved one place right (over the leftmost digit), and the machine switches to another m-configuration.

It might be advantageous to determine beforehand that certain similar m-configurations will be required in a machine, and to predefine special m-configurations just for those chores. Doing so might help clarify certain strategies used in programming a Turing Machine, and to make the final job easier.

Let's call the m-configuration that moves the head back to the sentinel goto-sentinel. Then, when we're writing the states for a particular machine, and we want the head to be positioned over the figure to the right of the sentinel, we just specify goto-sentinel and we don't have to figure out how to do it all over again. Not only would it make the machine description a bit smaller, but (in theory) it would help anyone who had to look at the machine understand it.

We might define goto-sentinel on its own like so:

and immediately we see a problem ...

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