T Naughton, NUIM
Back to SE307 home

Lab 1 - Turing machine programming

In this lab you will develop your Turing machine (TM) programming skills. For some programming problems I have given you sample TMs, for others I have not. By next week's lab you would be expected to be able to write TM programs for any of these problems.

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

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 TMs to conform to the VTM's convention.

Machine 1.A Construct a TM that writes a `T' on the tape if the input word is exactly "a" and writes `F' otherwise. You may assume that the input word contains zero or more `a's and contains no other symbols. For the initial state of the computation, you may assume that the tape head is positioned at the beginning of the input (for example, "aaa"). When the machine halts, the tape head should be one tape cell to the right of the location where it has written `T' or `F'. One valid table of behaviour corresponding to such a machine would be as follows.

#Si,R, Sf, W, M
#--------------
00, _, 99, F, R # if the input is empty then reject
00, a, 01, _, R # state 01 means we have found at least one `a'
01, _, 99, T, R # there was only one `a' so accept
01, a, 99, F, R # there was more than one `a' so reject

Make sure you understand how this machine works. Copy and paste it into the VTM with the following sample inputs (without quotes):
Tape: "__aa__"
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 "__aaa__", "__a__", and "___".

FYI: A `feature' common to many TM simulators is their inability to dynamically generate blank symbols -- the TM halts unexpectedly if it runs off the tape. So, pad your input with a couple of blanks either side. Also, 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. The VTM automatically positions the TM head at the first non-blank symbol in the input, or at the centre of the input if it contains only blank symbols.

Machine 1.B Construct a TM that deletes its input. You may assume that the input word contains zero or more `a's and contains no other symbols. For the initial state of the computation, you may assume that the tape head is positioned at the beginning of the input (for example, "aaa"). One valid table of behaviour corresponding to such a machine would be as follows.

#Si,R, Sf, W, M
#--------------
00, _, 99, _, R # when we reach a blank we halt
00, a, 00, _, R # state 00 means we have found another `a'

Use the trace to follow the evolution of the computation. Try a few inputs of your own, including "__aaa__", "__a__", and "___".

Machine 1.C Construct a TM that changes all of the symbols in its input word to `a's. You may assume that the input word contains only `a's and `b's (or no symbols at all). For the initial state of the computation, you may assume that the tape head is positioned at the beginning of the input (for example, "abb"). When the TM halts, the tape head should be positioned at the beginning of the input word. One valid table of behaviour corresponding to such a machine would be as follows.

#Si,R, Sf, W, M
#--------------
00, _, 01, _, L # when we reach a blank, we're at the end of the word so step left
00, a, 00, a, R # if we encounter an `a', just step right
00, b, 00, a, R # if we encounter a `b', replace it and step right
01, a, 01, a, L # if we're in state 01 we're in the process of returning to the beginning of the word
01, _, 99, _, R # when we reach the blank to the left of the word, just step right

Use the trace to follow the evolution of the computation. Try a few inputs of your own, including "__abab__", "__b__", and "___".

Machine 1.D Construct a TM to increment a unary number. (Here, unary numbers are represented by words that contain zero or more `1' symbols.) Initial state: the tape head is positioned at the beginning of the input (for example, "111"). Halting state: the tape head has positioned itself at the beginning of the output (in this case, "1111"). One valid table of behaviour corresponding to such a machine would be as follows.

#Si,R, Sf, W, M
#--------------
00, _, 01, 1, L # when we reach the end of the word, write a `1' and step left
00, 1, 00, 1, R # while looking for the end of the word, keep stepping right
01, _, 99, _, R # when we reach the beginning of the word, step right and halt
01, 1, 01, 1, L # while looking for the beginning of the word, keep stepping left

Use the trace to follow the evolution of the computation. Try a few inputs of your own, including "__1111__", "__1__", and "___".

Next, construct your own tables of behaviour for the following Turing machines. Write them on paper first. Use the VTM to test your tables.

Machine 1.1 Construct a TM to add 3 to a unary number. Initial state: the tape head is positioned at the beginning of the input (for example, "11"). Halting state: the tape head has positioned itself at the beginning of the output (in this case, "11111").

Machine 1.2 Construct a TM that writes `T' on the tape if its input consists of two unary numbers separated by exactly one blank symbol. Initial state: the tape head is positioned at the beginning of the input (for example, "111 11"). Halting state: a `T' or `F' has been written at the end of the input (in this case, "111 11T ").

Machine 1.3 Construct a TM to add two unary natural (in {0,1,...}) 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 1.4 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.

Machine 1.5 (For advanced students) 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").