Share
Explore BrainMass

Turing Machine that Computes the Function f(n) = 2n + 3

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

Solution Preview

We list a set of instructions (5-tuples, as described in the statement of the problem) for a Turing machine that computes the function f(n) = 2n + 3, and explain what is happening when each of these instructions is executed.

The basic strategy is as follows:

On input n, the machine begins with a string of n + 1 cells containing a 1 (and all the other cells blank). Since f(n) = 2n + 3, the machine is to have a total of 2n + 3 cells containing a 1 when it halts. Note that 2n + 3 = (2n + 2) + 1 = 2(n+ 1) + 1. When the machine executes the first part of our program, it will alternately replace the 1 in the (then-leftmost) non-blank cell with a blank and write 1's in a pair of consecutive blank cells. Thus the first part will start with n + 1 non-blank cells and end with 2(n + 1) = 2n + 2 non-blank cells. In the second part, it will write a 1 in one additional blank cell, for a total of 2n + 3 non-blank cells.

Let c_0, c_1, ..., c_n denote the cells that originally contain a 1 (on input n). (When the machine halts, the 1's will be located in cells c_(n + 1), c_(n + 2), ..., c_(3n + 3).)

The first cell in which a 1 is replaced with a blank will be c_0; the first pair of new 1's will be written in cells c_(n + 2) and c_(n + 3).

The second cell in which a 1 is replaced with a blank will be c_1; the second ...

Solution Summary

The Turing-machine model is described in detail, the program for computing the given function is given in its entirety, and an explanation of what happens at each step of the computation is presented.

$2.19