5. Study Figure 17.4 for this exercise. The tape depicts two numbers in unary notation that are to be added. You can envision unary as the manner in which a dog might count, “Ruff, Ruff would be a dog’s way to represent two and “Ruff, Ruff, Ruff” the number three. Hence this Turing machine is to add 2 and 3. A move can be represented as a 5-tuple:
qi: represents the present state Sj: the symbol scanned Sk: A symbol that is to be written on the same square upon which Sj appears (note Sk might equal Sj).
ql: the next state for the Turing machine {L, R, N}: the Turing machine might then move left or right one square, or not move at all.
Assume the computation begins with the read/write head positioned as shown and that when the computation is complete, the machine should be in a qh, directly underneath the blank to the right of the answer. Write a Turing machine program to perform addition of unary numbers. Trace your program for the problem given.