Simulating the turing machine

Assignment Help Computer Engineering

Reference no: EM1321865

Turing machine with the doubly in finite tape is one where the machine's read head can move left to the beginning of input string as well as right of end of the input string. All tape cells not part of the input string, in both the directions, initially comprises of the blank character ".

a) Turing machines with doubly infinite tapes are explained utilizing the same 7-tuple as Turing machines (with singly infi nite tapes) described in class and in Sipser; start configurations and accepting the configurations are also the same. Though, the rules for how a configuration C_i yields a configuration C_i+1 are different. Provide the rules for how C_iyields C_i+1 for the Turing machine with doubly infinite tape, involving the special-case rules which apply when the machine's read head is close to the either edge of area it has utilized so far on the tape.

b) Describe how to simulate the Turing machine along with singly infinite tape on the Turing machine with the doubly infinite tape. (Be sure to handle the can't move left" special case.)

c) Describe how to simulate the Turing machine with the doubly infinite tape on a Turing machine with singly infinite tape.

Reference no: EM1321865

Questions Cloud

Confidence interval for the population mean-selling homes : Find a 95% confidence interval for the population mean selling price of all homes in this neighborhood.

Computing roots of the function f : The best known iterative method in order compute the roots of the function f (that is, the x-values for which f(x) is 0) is Newton-Raphson approximation.

Appalachian coal mining should minimize net cost : Appalachian Coal Mining should minimize net cost by choosing that level of pollution

How technology will transform business in future : Anticipate how technology will transform business in the future. Give specific examples to support your response.

Simulating the turing machine : Describe how to simulate the Turing machine along with singly infinite tape on the Turing machine with the doubly infinite tape. (Be sure to handle the can't move left" special case.) Describe how to simulate the Turing machine with the doubly inf..

Demand curve or just move a point on the demand curve : If a company gets rid of a coupon does this shift the demand curve or just move a point on the demand curve.

Proportion of values from data set by chebyshev-s theorem : According to Chebyshev's theorem, proportion of values from data set that is further than 2 standard deviations from the mean is at most?

Foreign exchange traders : X and Y are foreign exchange traders in Germany. X agrees to sell 100 million Mexican pesos to Y for delivery within 1 week at an agreed price in German marks.

Find the minimum level of significance : The p-value for a test statistic is .085, what is the minimum level of significance required to reject the null hypothesis?

User Account

All Pages