Question

How can I create Turing Machine which will calculate sum of two binary digits separated by #, eg. 111#101B, where B is for blank? Result can be written at the end of the tape.

Was it helpful?

Solution

  1. Write a turing machine to convert both binary numbers to unary (maintaining the blank between them).
  2. Write a turing machine to replace the blank with a 1, and chop a digit off the end.
  3. Write a turing machine to convert a unary number to binary.
  4. Chain those three machines together.

OTHER TIPS

assuming input a#(1)b convert to a#(1)b#(2)c#(3)BLANK

Blank will be filled with sum. Make 2 cases for LSB of 'a'. Further divide 2 cases for LSB of 'b'. 'c' is the carry bit that is initially 0. Make seperate 2 cases for each of the four cases and update the carry bit on the way. Path is chosen based on if 'c' was 0 or 1.

Picture shows a rough sketch.

enter image description here

Final result will be reversed value of original sum. You reverse this again. Take the pic with a grain of salt. It is just a rough sketch. Nomenclature is not followed.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top