T Naughton, NUIM
Back to SE307 home

Lab 3 - Turing machine programming

In this lab you will continue to develop your Turing machine programming skills.

Once again, use Paul Ming's Perl Virtual Turing Machine (VTM).

Construct tables of behaviour for the following Turing machines. Write them on paper first. Use the VTM to test your tables.

Machine 3.A Construct a TM to increment a unary number. 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").

Machine 3.B 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").

Now go back to last week's lab sheet and solve each of the problems 2.E, 2.F, and 2.1. As soon as you are finished a problem, show it to a demonstrator. You will receive full marks for solving all three problems.

The following problem is for bright students who finish early. Solve this in your own time if you cannot complete it during lab time.

Machine 3.E Construct a TM to syntax check a piece of code composed of C/Java increment statements. Assume that the only int variable is `a' and that each statement ends with a semicolon. For example, "a++;" and "a++;++a;++a;" are valid programs, but "a+;" and "" (no increment statements) are not valid programs. You may also assume that there are no blank symbols in the program. Initial state: the tape head is positioned at the beginning of the first increment statement. Halting state: without overwriting any of the input, the tape head has positioned itself to the right of the input where it has written a `T' if the word is in the language of valid programs, and written an `F' otherwise.