5
$\begingroup$

I have been reading Wikipedia as an introduction to Turing machines. I found a reference to John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation (1st ed.), with a note that it is difficult to read. I am working hard with Wikipedia, and fear I will be unable to understand Hopcort and Ullman.

I am curious about how a Turing machine simulates a subroutine. If I understand http://en.wikipedia.org/wiki/Post%E2%80%93Turing_machine correctly, a Turing machine stores the return address and jumps to the subroutine, and jumps back to exit the subroutine, as an IBM360, IBM3* series machine did using BL (branch and link). Of course, modern machines store the return address on a stack and call the subroutine, but the two are similar. Is my assumption about storing the return address and jumping to simulate a subroutine correct?

Furthermore, has anyone simulated a subroutine by adding a symbol to the Turing machine alphabet for each subroutine? Symbols not defined within the machine would merely default to calling/jumping to the address of the subroutine. This technique is not much different from the one described in the paragraph above. I ask, because a machine I once worked on, and SDS 930 had some undefined op-codes that could be used to call subroutines. (Scientific Data Systems (SDS) was purchased by Xerox and renamed XDS).

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ There's a newer edition of that book by Hopcroft, Motwani and Ullman, which is much easier to read than the original 1979 book. I still like the original though, due to the high density of non-trivial ideas. $\endgroup$
    – Robin Kothari
    Sep 10, 2010 at 15:12
  • 3
    $\begingroup$ Um... Opcodes are just values you can have in memory! $\endgroup$
    – Jeffε
    Sep 10, 2010 at 16:44
  • 2
    $\begingroup$ @Edwin: There are many possible ways to implement subroutines in Turing machines -- no right or wrong way to do it. Your suggestion sounds natural, and given the years people have played with Turing machines, it has probably been done. You can always represent each subroutine with some subcollection of states in the Turing machine, which you can jump into by reaching a certain state in that collection, and jump out of by reaching another. It might be instructive to try coming up with Turing machines (from scratch) that simulate extremely simple programs with subroutines. $\endgroup$
    – Ryan Williams
    Sep 10, 2010 at 18:17
  • 3
    $\begingroup$ The jump from TM to subroutines is a bit too large for one mental bite. Better to first think of how a TM simulates a simple machine language (with only GOTOs, no subroutines), and separately consider simulating subroutines with that machine language. The latter is indeed most naturally done with a stack that keeps the return addresses. $\endgroup$
    – Noam
    Sep 10, 2010 at 18:26
  • 1
    $\begingroup$ A simple mental trick: First assume that you have a 2-tape Turing machine. Then you can easily use the 2nd tape as a "stack" for subroutines (return address, "local variables"). Finally, use the standard conversion from 2-tape machines to 1-tape machines. $\endgroup$
    – Jukka Suomela
    Sep 11, 2010 at 5:41

1 Answer 1

Reset to default
8
$\begingroup$

Martin Davis's book "Computability and Unsolvability" contains a very detailed account of Turing machines. In gory detail. In your particular case Corollary 2.2 on page 37 shows that composition of Turing-computable functions is again Turing-computable. This is just another way of saying that subroutines can be done.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. This question has been answered to my satisfaction. Someone please close this question. $\endgroup$
    – Edwin Earl Ross
    Sep 13, 2010 at 15:50
  • 4
    $\begingroup$ You could always accept any of the given answers as "satisfactory" by clicking on the check mark next to it... $\endgroup$
    – Andrej Bauer
    Sep 13, 2010 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.