Purchase Solution

Turing machine to compute the product of positive integers

Not what you're looking for?

Ask Custom Question

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
Purchase this Solution
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.

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

Purchase this Solution
Free BrainMass Quizzes
Javscript Basics

Quiz on basics of javascript programming language.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

Basic Networking Questions

This quiz consists of some basic networking questions.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

View More Free Quizzes
Related BrainMass Solutions

  • Logic : Turing Machines

    (a) We wish to design a Turing machine which, using monadic notation, inputs a pair (in, n) of positive integers in standard starting position (on an otherwise blank tape), and which halts scanning the rightmost of a string of in is on an otherwise blank

  • Turing Machines and PDP Networks

    The Universal Turing machine is known to be computationally complete, in the sense that any computation that may be carried can be carried out by such a device (according to the Church /Turing).

  • Universal Turing Machine

    The programming description of a Universal Turing Machine (UTM) is a description of the program that the UTM is carrying out. Specifically, it is a description of the specific machine that the UTM is pretending to be.

  • Turing machine configurations and outputs

    Since initial configuration of turing machine starts in state 1 with tape read head placed at the leftmost non-blank symbol, to reach the given state turing machine will have to execute some instructions.

  • Turing Machine that Computes the Function f(n) = 2n + 3

    --------- Using this Turing-machine model, create a program for a Turing machine that computes the function f: N -> N defined by f(n) = 2n + 3, where N is the set of all natural numbers (i.e., N is the set of all nonnegative integers).

  • Turing Machine: Sequences with equal number of 1s and 0s

    Apart from the list of transitions for the turing machine, solution also provides stepwise guidance on how to construct a graphical representation for the same.

  • Validity of Turing Test

    The argument for its validity is that, for most humans, all of this information exists in the brain as well. The argument for its invalidity is that the machine was just able to compute faster given a larger number of possible combinations.

  • Turing Machine for even palindromes

    106757 Turing Machine for even palindromes Construct a turing machine that accepts the language {ww^R : w <- {a,b}+}, where w^R denotes w superscripted R - reverse of w.

  • Turing machine for unary decrement

    When writing Turing machine algorithm, include comments for each instruction or related group of instructions. The comments should convey information in terms of the algorithm the Turing machine is accomplishing.

View More Related Solutions