T Naughton, NUIM
Back to SE307 home

Lab 2 - Turing machine programming

In this lab you will develop your Turing machine programming skills. Solve the introductory problems first. Then tackle one of the harder problems for lab credit.

There are many Turing machine simulation web sites. Here are a few that you may find interesting. First of all, some introductory information about Turing machines (with nonprogrammable TM applets) can be found at Andreas Ehrencrona's TM pages and Andrew Hodges' Alan Turing website. The Buena Vista University TM simulator is programmable, has some nice sound and graphics, but uses a slightly different table of behaviour convention to us. Visual Turing is a "graphical IDE that you may use to edit and play with Turing machines". Tril has a nice programmable TM applet with source code. There is also source for a Java TM simulator at SUNY Binghamton (I haven't tried this one).

FYI: A `feature' common to many TM simulators is their inability to generate blank symbols -- the TM halts unexpectedly if it runs off the tape. So, pad your input with a couple of blanks either side, and (if you have no control over where the tape head appears initially) make sure your table of behaviour is prepared for such initial blank symbols.

For SE307 we will use Paul Ming's Perl Virtual Turing Machine (VTM) because it allows us to trace the computation. Open it up in a separate browser to give yourself some comfort. I have written the following TM to conform to the VTM's convention.

Machine 2.A Construct a TM which writes a `T' on the tape if it recognises that the input is in the language a<sup>n</sup>b<sup>n</sup> (where n>=0), and writes an `F' otherwise. For the initial state of such a computation, you may assume that the tape head is positioned at the beginning of the input (for example, "aaabbb"). When the machine halts, the tape head will be one tape cell to the right of the location where it has written the appropriate symbol (in this case, "T "). One valid table of behaviour corresponding to such a machine would be as follows.

#Si,R, Sf, W, M
#--------------
00, _, 99, T, R # if the input is empty then accept
00, a, 01, _, R # state 01 means we are scanning through the `a's
00, b, 99, F, R # if there are more `b's than `a's then reject
01, a, 01, a, R
01, _, 99, F, R # if there are more `a's than 'b's then reject
01, b, 02, b, R # state 02 means we are scanning through the `b's
02, b, 02, b, R
02, a, 99, F, R # if an `a' appears to the right of a `b' then reject
02, _, 03, _, L # state 03 means we have reached the end of the input
03, b, 04, _, L # state 04 means go back to the beginning of the input
04, b, 04, b, L
04, a, 04, a, L
04, _, 00, _, R # scan through remaining input in an identical fashion

Make sure you understand how this machine works. Copy and paste it into the VTM with the following sample inputs (without quotes):
Tape: "__ab__"
Blank: "_"
Initial: "00"
Run it with the following options "one line per step", "show state before tape", and "show form after results".

Use the trace to follow the evolution of the computation (the angled brackets indicate the position of the tape head at each step). Try a few inputs of your own, including "__aaabbb__", "__b__", and "___".

Next, construct your own tables of behaviour for the following Turing machines. Use the VTM to test your tables.

Machine 2.B Construct a TM to recognise the language language aⁿb^m (where n,m>=0). That is, any word that consists of any natural number of `a's, followed by any natural number of `b's. Initial state: the tape head is positioned at the beginning of the input (for example, "aaaba"). Halting state: without overwriting any of the input, the tape head has positioned itself to the right of the input at the cell where it has written a `T' if the word is in the language, and written an `F' otherwise (in this case, "aaabaF").

Machine 2.C Construct a TM to add two unary natural numbers. Initial state: the tape head is positioned at the beginning of the input, which consists of two unary numbers separated by a single space (for example, "111 11"). Halting state: the tape head is positioned at the beginning of the output (in this case, "11111").

Machine 2.D Construct a TM to subtract two unary natural numbers. Initial state: the tape head is positioned at the beginning of the input, which consists of two unary numbers separated by a single space (for example, "111 11"). Halting state: the tape head is positioned at the beginning of the output (in this case, "1"). You may assume that the second number is never larger than the first.

When you are finished, try the following problems. To get full marks for this lab, show a demonstrator a working version of any of one of the following TMs.

Machine 2.E Construct a TM to calculate the modulus of two unary natural numbers. Initial state: the tape head is positioned at the beginning of the input, which consists of two unary numbers separated by a single space (for example, "11111 11"). Halting state: the tape head is positioned at the beginning of the output (in this case, "1"). You may assume that the second number is never larger than the first.

Machine 2.F Similar to Machine 2.A. However, when this machine halts, the original input symbols will have been restored and the tape head will have positioned itself one tape cell to the right of the input where it will have written the appropriate symbol (for example, "aaabbb" becomes "aaabbbT").

Machine 2.1 Construct a TM to multiply two unary natural numbers. Initial state: the tape head is positioned at the beginning of the input, which consists of two unary numbers separated by a single space (for example, "111 11"). Halting state: the tape head is positioned at the beginning of the output (in this case, "111111").