T Naughton, NUIM
Back to CS355 home

Lab sheet 6 - Turing machine programming

In this lab you will develop some basic Turing machine (TM) programming skills. First, you should try to understand the examples that I've given you, and then attempt the sample problems. If you don't finish today you should complete the lab sheet in your own time.

We will use Paul Ming's Perl Virtual Turing Machine (VTM) because it gives us a trace of every step in 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. For a definition of symbols (for example, '#' means the beginning of a comment) see the VTM introduction page.

Example Machine 6.A This TM takes a single word on its input tape, and writes a `T' on the tape if the input word is "a" followed by a blank, and does not write `T' otherwise. Assume that our tape head is automatically positioned at the beginning of the input initially.

Solution. One valid table of behaviour corresponding to such a machine would be as follows. The start state is 00.

#Si,R, Sf, W, M
#--------------
00, a, 01, a, R # state 01 means we have found at least one `a'
01, _, 99, T, R # there was only one `a' so accept

Copy and paste this machine into the VTM with the following sample inputs (without quotes):
Tape: "___a___"
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 "___aa___", "___b___", and "_____".

NOTE: Make sure to put two or three blank symbols "_" on either side of input to simulate an infinite tape. 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.

Example Machine 6.B In this example, we'll write a `T' if the single word on our input tape contains one or more copies of the symbol `a' (and no other symbols). As always, assume that the tape head is positioned at the beginning of the input initially.

Solution. One valid table of behaviour is (the start state is 00):

#Si,R, Sf, W, M
#--------------
00, a, 01, a, R # we have found our first `a'
01, a, 01, a, R # we have found another `a'
01, _, 99, T, R # there were only copies of `a' so accept

Use the trace to follow the evolution of the computation. Inputs such as "___aaa___" and "___a___" should be successful, and "______" and "___aaaba___" should not.

Example Machine 6.C An even simpler machine is one that checks if the single input word contains zero or more copies of `a' (and no other symbols).

Solution. One valid table of behaviour is (the start state is 00):

#Si,R, Sf, W, M
#--------------
00, a, 00, a, R # we have found another `a'
00, _, 99, T, R # no non-`a's so accept

Inputs such as "______" and "___aaaa___" should be successful, and "___x___" and "___aaaba___" should not.

Example Machine 6.D Same as Machine 6.B, except we must also ensure that we write an `F' if our input word contains any non-`a' characters or is blank. Assume that the only possible characters in the input are `a' and `b'. For example, input words "aaa" and "a" should result in a `T'. Input words "aaab" and "abaaaa" should result in an `F'. (Don't forget to remove the quotes and put blanks on either side of these sample inputs!)

Solution. One valid table of behaviour corresponding to such a machine would be as follows. The start state is 00.

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

Example Machine 6.E Next, we'll construct a TM that deletes its input. Assume that the input word contains only `a' and `b' symbols (or is blank) and contains no other symbols. As always, assume that the tape head is positioned at the beginning of the input.

Solution. One valid table of behaviour is (the start state is 00):

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

As always, try a few inputs of your own, such as "__aaa__", "__abb__", and "___".

Example Machine 6.F Construct a TM that changes all of the symbols in its input word to `a's. Assume that the input word contains only `a's and `b's (or no symbols at all). For the initial state of the computation, 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. (The start state is 00.)

Note: if the comments in the TM below do not fit on a single line when you paste them into the VTM, then you should shorten or delete them.

#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

Try a few inputs of your own, including "____abab____", "____b____", and "______".

Example Machine 6.G Construct a TM to increment a unary number. (Here, unary numbers are represented by words that contain zero or more `1' symbols.) Assume the tape head is positioned at the beginning of the input initially (for example, "111", where the underscore represents the position of the TM tape head). At the end of the computation, the tape head should have 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. (The start state is 00.)

#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

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. In all cases, assume that the tape head is at the beginning of the input initially. Unless otherwise stated, it does not matter where the TM tape head is when the computation finishes.

Machine 6.1 Construct a TM that changes all of the `a' symbols in its input word to `b', and all of its 'b' symbols to `a'. Assume that the input word contains only `a's and `b's (or no symbols at all). For example, an input "abaab" should be transformed into "babba".

Machine 6.2 Construct a TM that writes a `T' if the input word contains the substring "aa". Assume that the input word contains only `a's and `b's (or no symbols at all). For example, inputs "abaaba" and "aa" should cause the TM to write a `T'.

Machine 6.3 Construct a TM that writes a `T' if the input word contains the substring "aa", and writes `F' otherwise. Assume that the input word contains only `a's and `b's (or no symbols at all). For example, inputs "abaaba" and "aa" should cause the TM to write a `T', and inputs "ababa" and "______" should cause the TM to write an `F'.

Machine 6.4 Construct a TM to add 3 to a unary number. Assume the tape head is positioned at the beginning of the input initially (for example, "11"). At the end of the computation, the tape head should have positioned itself at the beginning of the output (in this case, "11111").

Machine 6.5 Construct a TM to increment a binary number. Assume that the input word contains only `0's and `1's. Assume that the input word is not blank. For example, input "1000" should be transformed into "1001", input "1001" should be transformed into "1010", and input "1111" should be transformed into "10000".