Share
Explore BrainMass

Turing machine with input in unary notation

Devise a Turing machine with input given in unary notation (i.e., a string of n 1's denotes the integer n, and numbers are delimited by 0's) such that the machine produces the following output:

0 if x is divisible by 4

1 if x is congruent to 1 modulo 4

2 if x is congruent to 2 modulo 4

3 if x is congruent to 3 modulo 4

Show the state table for the machine.

Solution Preview

When the machine starts, there are two 0's on the tape (one at each end) as delimiters, n 1's between the two 0's, and blanks ad infinitum to the left of the first (leftmost) 0, and blanks ad infinitum to the right of the second (rightmost) 0.

What we are going to do is devise a Turing machine that will read 1's in groups of four, and then wipe out the existing group of four 1's before it reads the next group of four 1's.

After reading a group of four 1's, it will replace the rightmost 1 in the group with a 0; then it will move to the left and place a blank in the cell that contains the leftmost 0; finally, it will move to the right and place a blank in each of the cells that originally contained one of the first three 1's in the group of four (counting from left to right), and it will then proceed to read a new group of four 1's (if any).

If there are fewer than four 1's to be read at any point (when the machine is ready to start reading 1's again, after taking the steps already indicated, to deal with the previous group of four 1's), the machine will read the remaining 1's (if any), and then halt. The output will be the then-current contents of the tape:

If n is divisible by 4, there will be no 1's left to be read, so the contents of the tape will be 00, which is the code for "0".

If n is congruent to 1 mod 4, there will be just one 1 left to be read, so the contents of the tape will be 010, which is the code for "1".

If n is congruent to 2 mod 4, there will be just two 1's left to be read, so the contents of the tape will be 0110, which is the code for "2".

If n is congruent to 3 mod 4, there will be just three 1's left to be read, so the contents of the tape will be ...

Solution Summary

The Turing machine is defined, and a detailed explanation of what happens at each step of the computation is provided.

$2.19