T Naughton, NUIM
Back to CS370 home

Lab 1 - Turing machine programming - Selected solutions

Machine 1.4 Machines 1.3 and 1.4 illustrate that the simplest way for a TM to count, or to implement bounded loops, is to use individual states for each iteration. (A for loop is a bounded loop. Unbounded loops such as while loops are much easier with TMs -- for example, "00, 1, 00, 1, R" is an example of an unbounded loop coded as a TM rule.) One possible solution to Machine 1.4 is given below. Notice that we need to devote one new state for each increment that we have to count. Note also that the solution works for blank inputs (a blank is the number zero in unary).

Sample solution. The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 1, 00, 1, R # scanning to find rightmost digit
00, _, 01, 1, R # end found, counting first increment
01, _, 02, 1, R # counting second increment
02, _, 03, 1, L # counting third increment
03, 1, 03, 1, L # return to leftmost digit
03, _, 99, _, R # rightmost found, so halt

Machine 1.5 Although not part of the requirement for Machine 1.5, the solution below also just happens to take care of blank inputs also (a blank input is interpreted as a binary zero).

Sample solution. The start state is 00.

#Si,R, Sf, W, M
#--------------
00, 0, 00, 0, R # scan right looking for rightmost digit
00, 1, 00, 1, R # scan right looking for rightmost digit
00, _, 01, _, L # rightmost digit found
01, 0, 02, 1, L # if digit is zero, write a 1
01, 1, 01, 0, L # if digit is 1, write 0, move left, and repeat
01, _, 02, 1, L # if no more digits, write a 1
02, 0, 02, 0, L # have incremented, so scan left for leftmost digit
02, 1, 02, 1, L # have incremented, so scan left for leftmost digit
02, _, 99, _, R # leftmost digit found, so halt