Purchase Solution

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

Not what you're looking for?

Ask Custom Question

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

Purchase this Solution
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.

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 provided by:
Georgia Martin, PhD
Education
  • AB, Hood College
  • PhD, The Catholic University of America
  • PhD, The University of Maryland at College Park
Recent Feedback
  • "Thanks for your assistance. "
  • "Thank you. I understand now."
  • "Super - Thank You"
  • "Very clear. I appreciate your help. Thank you."
  • "Great. thank you so much!"
Purchase this Solution
Free BrainMass Quizzes
C++ Operators

This quiz tests a student's knowledge about C++ operators.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Javscript Basics

Quiz on basics of javascript programming language.

C# variables and classes

This quiz contains questions about C# classes and variables.

View More Free Quizzes
Related BrainMass Solutions

  • Logic : Turing Machines

    (i) Wnte down the values of f(l),f(2),f(3),f(4),f(5). [2.5] (ii) What, in general. is the value off(n) for vs Є p Describe briefly how the machine computesJ(n), including an indication of each possible halting state and the circumstances under

  • Turing machine for unary decrement

    In unary representation, any unsigned whole number n is encoded by a sequence of n+1 1s. Following Turing machine instructions will perform the unary decrement in constant time irrespective of the input size, leaving a 0 on the tape, in case n is 0.

  • Problems in calculus and trigonometry

    (2) Show that cot(pi/3) = 1/[sqrt(3)], where "sqrt" stands for "square root." (3) Obtain the Maclaurin series for the function f(x) = sin x. (4) Obtain the Maclaurin series for the function f(x) = sin(2*x).

  • Turing machine to accept the language "A^n B^n C^n"

    107765 Give the transitions for a turing machine to accept the given language. Give the transitions for a turing machine that accepts the language given below.

  • Numerical integration using Simpson and Gaussian quadrature

    the integral of the function f from a to b.

  • Periodic function proof

    This is impossible since n and k are positive integers. So the assumption that f is periodical function is false. Therefore f is not periodical. This proves a function is not periodic.

  • Calculus : Partitions and Riemann Integral

    7927 Calculus : Partitions and Riemann Integral Let f be the function: F(x) 1/4 x=o, x 03/4 x=1 Using standard partition Pn (0,1) where n greater or equal to 4 L(f, Pn) = 2n(squared) -3n+4 all divided by 4n(squared) U(f,Pn) = 2n(squared

  • Setting up a Riemann Sum

    +n)/n)=1/n*(2n+n*(n+1)/2n) =2+(n+1)/2n When n->inf, then the area approaches 2+1/2=2.5 Choice #3: We select the value of the middle point (i/n+(i+1)/n)/2=(2i+1)/2n. The height of the strip is f((2i+1)/2n)=(2i+1)/2n+2.

  • Turing machine configurations and outputs

    193075 Draw Turing machine configurations and find the output as asked in the questions below. For questions 3 to 5, remember that a Turing machine starts in state 1, reading the leftmost nonblank cell. 1.

View More Related Solutions