Explore BrainMass
Share

# Turing machine to compute the product of positive integers

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

https://brainmass.com/computer-science/theoretical-computer-science/turing-machine-compute-product-positive-integers-106759

#### 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