Share
Explore BrainMass

Turing machine to compute the product of positive integers

Construct a turing machine to compute the product x*y of any two positive integers x and y. Assume that the inputs x and y are represented in unary and are separated by a single 0.

Attachments

Solution Preview

Notations used for denoting a turing machine transition :
-----------------------------------------------------------------

(StartState, SymbolRead) --> (EndState, SymbolWritten, MovementDirection)

* Movement Directions are denoted by R (right) and L (left).
* E is used to denote NULL symbol (or absense of symbol in a tape cell) - which is represented
by a little rhombus in 4ahelp.GIF attached with the problem posting.
* $ denotes a marker symbol.

* You can construct graphical representation of turing machine by representing each transition as below.
- ...

Solution Summary

Given turing machine halts with the tape read/write head pointing to the beginning of computed product, and leaves nothing else but this product on the tape.

Solution also guides, how you can construct a graphical representation of the turing machine from the given transition list.

$2.19