Use the construction from class to give a diagram

Assignment Help Computer Engineering

Reference no: EM13323151

Give an offline TM which when started with x#y on its read only input tape outputs ?xy? on its output tape. Assume {0,1,#} is the input alphabet and numbers are in binary (lead zeros not allowed). On bad inputs your TM should halt, with # on the tape. If y is 0 output #. If x is 0 and y is a nonzero integer the output should be 0.
Given the offline TM above use the construction from class to give a diagram of a usual TM computing the same function.
Give the RAM that would result from applying the construction of class to the TM from Problem 2.
Give a nondeterministic Turing machine which recognizes the language of binary strings of integers nsuch that n is a product of integers x and y both of which are greater than 1. You can give a high level description of your NTM.

Reference no: EM13323151

Questions Cloud

Define the f by m ratio in context of biological treatment : Define the f/m ratio in the context of biological treatment of wastewater, and relate the f/m ratio to the exponetial growth and declinign growth phases of a bacterial culture.

What was the incident speed of the second mass : A mass of .5Kg is attached to a massless spring with spring constant k=600N/m, What was the incident speed of the second mass

What does that mean in terms of remaining and removal : Suppose you are told that a process must achieve a 2.7 log removal of Giardia cysts. What does that mean in terms of % remaining and % removal

Mechanism of evolution led him to atheism : Explain why Darwin's understanding of the mechanism of evolution led him to atheism?

Use the construction from class to give a diagram : Give a nondeterministic Turing machine which recognizes the language of binary strings of integers nsuch that n is a product of integers x and y both of which are greater than 1. You can give a high level description of your NTM.

Compute the criteical stress required for the propagation : If the specific surface energy for aluminum oxide is 0.90 J/m^2, using data contained, compute the criteical stress required for the propagation of an internal crack of length 0.40 mm.

Find the energy delivered by a photon : Find the energy delivered by a photon of the yellow- green light to which our eyes are most sensitive

Balance sheet preparation : Balance Sheet Preparation) Presented below are a number of balance sheet items for Montoya, Inc., for the current year, 2010.

Calculate the focal length of the mirror : A woman holds a tube of lipstick 9 cm from a spherical mirror and notices that the image of the tube is upright and one fourth its normal size. Calculate the focal length of the mirror

User Account

All Pages