[Overview] [Previous] [Next]

Turing Subroutines

Subroutines are extremely useful in standard programming languages. They allow you to break a complex problem into simpler and simpler subproblems.

Standard Turing machines do not have subroutines, but it's easy to fake them. We do not need to add any new features. The basic idea is to use one state, or a small group of states, to perform a single task. For example, the following state can be used to find the left end of the input:

  q0     |    a     |     a     |      L      |   q0
  q0     |    b     |     b     |      L      |   q0
  q0     |    #     |     #     |      R      |   q1
This "subroutine" can be entered by going to state q0 (which isn't a problem) and it "exits" by going to state q1 (which is a problem). We would like to have the subroutine exit to different states, depending on where it was called from. The easy way to do this is to make multiple copies of the subroutine, using the same structure but different state names, e.g.,
  q41    |    a     |     a     |      L      |   q41
  q41    |    b     |     b     |      L      |   q41
  q41    |    #     |     #     |      R      |   q87
This approach is cumbersome but theoretically adequate, so long as only a finite number of copies are required.

Copyright © 1996 by David Matuszek
Last modified Mar 27, 1996