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.


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

What is the complexity

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

Construct a table for this weighted code

It is possible to have negative weights in a weighted code for the decimal digits, e.g.,8,4, -2, and -1 can be used. Construct a table for this weighted code. Ifd is a dec

Devise a local search heuristic for service network design

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.

An atsp optimal solution which is a hamiltonian tour

Show that if the costs associated to the arcs of a complete directed graph G satisfy the triangle inequality property, then there exists in G' an ATSP optimal solution which

Modify the syntax of a programming language

Sometimes it is necessary to modify the syntax of a programming language. This is done by changing the CFG that the language uses. What changes would have to be made to ac's

Imply the conclusion

Use rules of inference to show that the hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on

Write negative binary numbers in sign and magnitude

The first part of this unit introduces the material to be studied later. In addition to getting an overview of the material in the first part of the course, you should be ab

Derive a state table for the circuit

A Mealy sequential circuit has one input (x) and one output (z).z can be 1when the fourth, eighth, twelfth, etc.inputs are present, and z = 1 if and only if the most recent


Write a Review

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd