Turing machine model, Think about the following

Turing machine model

Assignment Help Theory of Computation

Reference no: EM1380767

Think about the following Turing-machine model (which is used in one of the standard textbooks in recursion theory, a branch of mathematical logic: Recursively Enumerable Sets and Degrees, by Robert I. Soare, Springer-Verlag, New York, 1987):

The Turing machine is equipped with the following:

(i) a tape that is infinitely long in both directions and is divided into cells; at any given step, each cell either is blank or contains a 1 (we will refer to the latter type of cell as a non-blank cell)

(ii) a read head (which reads one cell of the tape at each step)

(iii) a finite set Q of states (Q = {q_0, q_1, q_2, ..., q_k} for some nonnegative integer k)

At any given step of a Turing computation,

(a.) all but at most finitely many cells of the tape are blank (the rest, if any, contain a 1)

(b.) the machine can either remain in the current state or change to a different state

(c.) the contents of the cell being read can either change (from 1 to blank, if it currently contains a 1; from blank to 1, if it currently contains a blank) or remain as is

(d.) the read head must move by one unit, either to the right (R) or to the left (L), before the next step

The program for a Turing machine consists of a finite set of 5-tuples (q, s, q', s', m), where q and q' are the current and subsequent states of the machine, and s and s' indicate the current and subsequent contents of the cell being read; if m = L, the machine is to move one unit to the left of the current cell; if m = R, the machine is to move one unit to the right of the current cell.

The input to the machine, n, is represented on the tape by a string of n + 1 consecutive 1's, with all the other cells blank.

Examples:

If n = 0, only one cell of the tape contains a 1 (since n + 1 = 0 + 1 = 1).

If n = 1, there are two consecutive cells containing a 1 (since n + 1 = 1 + 1 = 2), and all the other cells are blank.

If n = 2, there is a string of three consecutive cells containing a 1 (since n + 1 = 2 + 1 = 3), and all the other cells are blank.

The machine begins in state q_1, with the read head positioned at the leftmost cell of the tape that contains a 1.

The halting state of the machine is q_0; if the machine ever reaches state q_0, the machine halts and outputs the total number of 1's on the tape, which is the value of the function being computed.

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

Reference no: EM1380767

Questions Cloud

Determines if benefits of free trade outweigh drawbacks : Determines if benefits of free trade outweigh drawbacks also illustrate what could be done to address drawbacks.

Issue facing many states is whether to legalize casino : A major issue facing many states is whether to legalize casino gambling. Suppose the governor of one state believes that more than 55% of the state's registered voters would favor some form of legal casino gambling

Illustrate what should a memo telling staff : Illustrate what should a memo telling staff illustrate what to do when they encounter problems, with business technology comprise.

Venue is the authority of a court to hear and determine : Venue is the authority of a court to hear and determine disputes. The losing party in arbitration cannot appeal the arbitrator's decision to a regular court on the basis that the decision was unwise.

Turing machine model : Think about the following Turing-machine model, A tape that is infinitely long in both directions and is divided into cells; at any given step, each cell either is blank or contains a 1.

Establish five key objectives for wal-mart encompassing : Establish five key objectives for Wal-Mart encompassing operational, financial also human resource aspects of business.

Should hg employ someone whose main function is liaison : should HG employ someone whose main function is that of liaison between its corporate cultures also culture of its host country. If so, is Martin right person for job.

Hospital medical staff office at the rural outreach : You are the assistant director of the hospital medical staff office at The Rural Outreach Community Hospital in a tiny town in Arkansas. It is your job to verify physician credentials for staff privileges

Evaluate employees individual work performance : Managers like Janis Blancero face a more complicated decision when evaluating personal requests of employees versus evaluating employees individual work performance. Explain.

User Account

All Pages