Question

What is the possible transition diagram of Turing Machine for the given expression? M (x, y) = x + y

where x and y are integers expressed in unary notation

to calculate f (2,3), then the input will be 110111

Answer 1

Input:

Here 2 + 3 given as 110111, the number 2 is represented with two 1"s and 3 is represented with three 1's.

and 0 inbetween 1's represented for addition or like a delimiter for the sepearting the operators for the given operation.

Output:

so output will be 11111 that is 2+3= 5 represented with five 1's.

Method:
Convert a 1 in the first number in to a symbol $ and then traverse entire input and convert the first blank encountered into 1. Then move towards left ignoring all 1’s and “0”. Come the position just next to $ and then repeat the same procedure till the time we get a “0” instead of $ on returning. Convert the 0 into blank and addition is completed.

Steps:

Step-1: Convert 1 into $ and goto step 2. If symbol is “0” then convert it into blank(B), move right and goto step-6.

Step-2: Keep ignoring 1’s and move towards right. Ignore “0”, move right and goto step-3.

Step-3: Keep ignoring 1’s and move towards right. Convert a blank(B) into 1, move left and goto step-4.

Step-4: Keep ignoring 1’s and move towards left. Ignore “0”, move left and goto step-3.

Step-5: Keep ignoring 1’s and move towards left. Ignore a $, move left and goto step-1.

Step-6: End.

Transition Diagram:

For more clarrifiaction of working: