Explore BrainMass

Explore BrainMass

    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.

    © BrainMass Inc. brainmass.com May 20, 2020, 2:54 pm ad1c9bdddf


    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.