Theory of Computation
Lab5

In this lab you will develop your Turing machine (TM) programming skills. For some programming problems sample TMs are provided.

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

For this lab use Paul Ming's Perl Virtual Turing Machine (VTM) because it allows a trace of computation. Open it up in a separate browser window for ease of use. The following TMs 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 is 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 "___".

NOTE: 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. Use the VTM to test your tables. NOTE: use at least two blanks to start and end the input tape if you want to move Right on a halting state (i.e. you just read a blank that represents the right edge of the input and are in an accept or reject state). The VTM will not generate a blank tape symbol.

Submit via e-mail - at least the table for Machine 1.1 by the end of the lab session. The table should be in text only format. The tables for the remaining machines should be submitted on moodle.

Machine 1.1 Construct a TM to add 3 to a unary number. You may assume that you have at least one 1 on the input tape. 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. You may assume that each unary number consists of at least one 1. Initial state: the tape head is positioned at the beginning of the input (for example, "111 11"). Halting state: a `T' has been written at the end of the input (in this case, "111 11T ") or an 'F' has been written at the point where the error occurs (for example, "111_F11").

Machine 1.3 Construct a TM to add two unary numbers. You may assume there is no error on the input tape. 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 numbers. You may assume there is no error on the input tape. 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 Construct a TM to multiply two unary numbers. You may assume there is no error on the input tape.

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