Question

Problem 1:

Problem 2:
Assume that any number of 1s side-by-side represent a number, with the value of that number being

the number of 1s that appear. For example:

011111110

represents the number 7. (This style of representing numbers is referred to a unary notation – it’s generally not used anywhere but number theory / set theory.)

Write a Turing machine that computes the remainder of its input when that input is divided by 3. Given, for example, the following input tape:

running your program should produce the following result:

Problem 3 – Duplicating a number

Implement a Turing machine program that copies an input value on the tape, leaving two identical values separated by a single 0. For example, if the input tape is:

The result should be:

problem 4:

Below find the states for a 4-state Turing machine that, when starting with a blank tape, produces 13 1s. Your task in this extra credit problem is to write a 4-state Turing machine that produces at least eight but no more than twelve 1s before stopping.

It may be useful to look at the following 3-state Turing machine and use it for ideas on how to make your 4-state Turing machine. Note, though, that there are many solutions to this problem, and that only some of these solutions resemble the 3-state machine below.

Answer 1

problem 2: We will denote state transition using the triple (x,y,D) where x is the inout symbol we got , y is the change we did at that point in tape and D = L or R ie the direction left or right we moved in the tape. So the tape for 7 divided by 3 is given below

Now in algorithm the number of 1's in the dividend will be changed to X and the number of 1's left before the rightmost zero symbol will be the remainder and the number of 1's after the rightmost zero will be the quotient.

Now here is the state transition diagram for the algorithm.

The number of 1's left in the dividend in the figure above will be your remainder. Rest all ones dividend will be replaced by X.

Problem 3:

The steps for duplicating are given below

• Step-1. First convert all 0’s, 1’s into 0’s, 1’s and go right then B into C and go left
  
• Step-2. Then convert all 0’s, 1’s into 0’s, 1’s and go left then
  
• Step-3. If 1 convert it into X and go right convert all 0’s, 1’s into 0’s, 1’s and go right then convert C into C and go right then convert all 0’s, 1’s into 0’s, 1’s and go right then convert B into 1 and go left then convert all 0’s, 1’s into 0’s, 1’s and go left then convert C into C and go left then convert all 0’s, 1’s into 0’s, 1’s and go left then convert all X into X and go right and then repeat all the process from step-2 till end
  
• Step-4. If 0 then convert it into Y and go right then convert all 0’s, 1’s into 0’s, 1’s and go right then convert C into C and go right then convert all 0’s, 1’s into 0’s, 1’s and go right then convert B into 0 and go left then convert all 0’s, 1’s into 0’s, 1’s and go left then convert C into C and go left then convert all 0’s, 1’s into 0’s, 1’s and go left then convert all Y into Y and go right and then repeat all the process from step-2 till end
  
• Step-5. Otherwise if C found convert it into C and go left then convert all X into 1 and Y into 0 and go left then convert B into B and go right and stop the machine.