+1-415-670-9189
info@expertsmind.com
Turing machine model
Course:- Theory of Computation
Reference No.:- EM1380767




Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Theory of Computation

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




Put your comment
 
Minimize


Ask Question & Get Answers from Experts
Browse some more (Theory of Computation) Materials
Create a standard 1-tape Turing machine M to calculate the function sub3. Specifically, calculate sub3 of a natural number represented in binary.
A javascript program to demonstrate computational complexity. Using the wikipedia article; a computer program that calculates the number of moves necessary to solve Tower of
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 o
If the interest rates drop then the housing market will improve. Either the federal discount rate will drop or construction will decrease. Interest rates will drop and utili
Consider the language L = L1 ∩ L2, where L1 = {ww^R : w ∈ {a, b}* and L2 = {a^n b*a^n: n ≥ 0}. Write the first four strings in the lexicographic enumeration of L?
Devise a local search heuristic for the service network design problem in which an individual move is to remove an existing arc or to add a new arc to the current solution.
Create a program that reads integers in range 0 .. 9999. The event stops reading if -99 is entered. Your event should use Stack to store those numbers then it used Priority Qu
There are four processes that are going to share nine tape drives. Their current and maximum number of allocation numbers. Is system in a safe state? Explain why or why not?