<p>Martin Davis's book <a href="http://books.google.si/books?id=TMLgEIOGhBMC&amp;lpg=PP1&amp;ots=d5szSTrlaY&amp;dq=martin%20davis%20computability%20and%20unsolvability&amp;hl=en&amp;pg=PP1#v=onepage&amp;q&amp;f=false">"Computability and Unsolvability"</a> 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.</p>

CC BY-SA 2.5
2010-09-13T15:50:45.907Z
Thanks. This question has been answered to my satisfaction. Someone please close this question.
Edwin Earl Ross
CC BY-SA 2.5
2010-09-13T22:10:25.100Z
You could always accept any of the given answers as "satisfactory" by clicking on the check mark next to it...
Andrej Bauer
CC BY-SA 2.5
2010-09-12T18:50:11.173Z
2010-09-12T18:50:11.173Z
Andrej Bauer
<p>I have been reading Wikipedia as an introduction to Turing machines. I found a reference to John Hopcroft and Jeffrey Ullman, (1979). <em>Introduction to Automata Theory, Languages and Computation</em> (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. </p>

<p>I am curious about how a Turing machine simulates a subroutine. If I understand <a href="http://en.wikipedia.org/wiki/Post%E2%80%93Turing_machine">http://en.wikipedia.org/wiki/Post%E2%80%93Turing_machine</a> 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?</p>

<p>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). </p>

CC BY-SA 2.5
2010-09-10T15:12:58.953Z
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.
Robin Kothari
CC BY-SA 2.5
2010-09-10T15:43:31.907Z
The symbols of a Turing machine are more like values you can have in memory (e.g., true, false, 0, 1, 2, 'a', 'b', ...) rather than like opcodes (e.g., JMP, CALL, MOV, ...)
Radu GRIGore
CC BY-SA 2.5
2010-09-10T16:44:24.340Z
Um... Opcodes are just values you can have in memory!
Jeffε
CC BY-SA 2.5
2010-09-10T18:17:46.437Z
@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.
Ryan Williams
CC BY-SA 2.5
2010-09-10T18:26:52.103Z
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.
Noam
CC BY-SA 2.5
2010-09-10T18:51:12.287Z
@Noam: It looks like the linked Wikipedia page discusses universal Turing machines (rather than Turing machines). (So the symbols-as-opcodes make "more" sense.)
Radu GRIGore
CC BY-SA 2.5
2010-09-11T05:41:57.713Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-09-11T15:19:46.347Z
@Noam I now know that I should have said *Universal* Turing Machine.
Edwin Earl Ross
<turing-machines>
Turing Machines and Subroutine Simulation
Edwin Earl Ross
# Turing Machines and Subroutine Simulation

(Asked by: username_0 on 2010-09-10)

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

**Tags:** turing-machines
> **Comments:**
> **username_1**: 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.  
> **username_2**: The symbols of a Turing machine are more like values you can have in memory (e.g., true, false, 0, 1, 2, 'a', 'b', ...) rather than like opcodes (e.g., JMP, CALL, MOV, ...)  
> **username_3**: Um... Opcodes are just values you can have in memory!  
> **username_4**: @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.  
> **username_5**: 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.  
> **username_2**: @Noam: It looks like the linked Wikipedia page discusses universal Turing machines (rather than Turing machines). (So the symbols-as-opcodes make "more" sense.)  
> **username_6**: 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.  
> **username_0**: @Noam I now know that I should have said *Universal* Turing Machine.  

---

## 1 answers

### Answer by username_7 on 2010-09-12. Score: 8

Martin Davis's book ["Computability and Unsolvability"](http://books.google.si/books?id=TMLgEIOGhBMC&lpg=PP1&ots=d5szSTrlaY&dq=martin%20davis%20computability%20and%20unsolvability&hl=en&pg=PP1#v=onepage&q&f=false) 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.

> **Comments:**
> **username_0**: Thanks. This question has been answered to my satisfaction. Someone please close this question.  
> **username_7**: You could always accept any of the given answers as "satisfactory" by clicking on the check mark next to it...  

---

