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.


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

Ask Question & Get Answers from Experts
Browse some more (Theory of Computation) Materials
If M is a DFA accepting language B, then exchangeing the accept and reject states gives a new DFA accepting the complement of B. Does this work for an NFA, why?
Construct a diagram to map the arguments about a moral claim that you have identified and write an essay, which maps closely to the diagram that you constructed in Step 1.
Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).
BIT203 Professional Practice and Ethics - During week 6 you will be required to give a brief 5-8 minute presentation to the class explaining either the analysis and conclusio
Create a standard 1-tape Turing machine M to calculate the function sub3. Specifically, calculate sub3 of a natural number represented in binary.
Which sentence has the logical mismatch between predicate and subject? Choose one of options below as your answer: A. Misunderstanding was as he lost directions.
Find a left-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression ab*aa + b
Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} U {x}, where the summation now is B+x. it is possible to split the numbers in A in