DOC

2-Tape Turing Machine

By Bertha Kennedy,2014-10-31 22:17
15 views 0
2-Tape Turing Machine

    2-Tape Turing Machine

    by

    Josue Vazquez & Richard Millán

    Theory of Computation - Computer Science 334

    Dr. Joan Krone

    December 10, 2001

    1

    TWO TAPE TURING MACHINE

    We have picked the 2-tape-turing machine for our project since we know that there is no machine more powerful than the Turing Machine. The advantage of a 2-tape-turing machine is that it is simpler to design certain complex machines. It is also more efficient (time wise) than a single tape TM (Turing Machine), as we will show further in our paper. We will begin by giving a description of our machine. Our machine consists of a quintuple (K,,,s, H), where K, , s and H are the same as in the definition of a

    ksingle tape TM, and , the transition function, is a function from (K-H)x () to K x

    k(U {,}) , where in the case of our 2 tape TM k=2 . That is, for each state q, and each 2-tuple of tape symbols (a,a), (q, (a,a))=(p,(b,b)), where p is as in the case of a 121212

    TM, the new state, and bj (where j=1 or j=2) is the action taken by M at tape j. Again, we insist that is aj= ; for some j<=k, then bj=.

     Since computations take place in both tapes off our machine, accordingly a

    configuration for it must include

    information about all tapes. It will be of Tape 1:

    2the form K x (;; * (((-{U})U{e}) * )

    Tape 2:

    where U represents a space. This means

    the configuration identifies the state, the

    tape controls of each tape, and the head q 0

    position for each state. For example if we h q Finite Control 1

     have (q, (w,a,u, w,a,u)) as a 111222q q 23

    configuration for our 2-tape TM and if

    2

    ,a2))= (q(b,b2), then in one move the machine would move to configuration d(p,(a11

    111111111(p(w,a,u, w,a,u)) . Then w,a,u (where j=1 or j=2) is w,a,u modified by 111222j j jiii

    action b, where b U {,}, and can make basically the same actions as b would do jj

    in a single-tape TM.

    We adopt the convention that the input for our machine will be given a standard input string (UwU) where w is a string that does not contain any blanks. The input and output of our machine are entered and displayed on the first tape. All the other tapes are just used for computations but they are blank at the beginning and at the end there content is ignored.

     A 2-tape TM can be depicted the same way as a single-tape TM. We only need to attach a superscript to each to indicate the tape-number of the machine that we want to

    1operate on. For example, the machine R will go right until it finds the blank symbol. U

    1,2R will look for a blank symbol as in the previous machine but in both tapes. Therefore, U

    2we avoid using the shorthand M for MM as we did for a single tape TM. A label like a 1

    on an arrow denotes an action taken if the symbol scanned from the first tape is a symbol “a”. On the next page there are examples that illustrate the notation for a two-tape Turing Machine.

    3

    Examples:

    1) Here in this example we compare two different copy machines. The two-tape

    machine is illustrated in 1-a, and the one-tape diagram is shown in 1-b.

    a)

    12a? U 1,2 a R

     1a= U

    2 a? U 1,2 1,2 1L Ra

    b)

    a?U 22R URaLa U L U

     U

    U

    R U

     U

    2) The next diagram is a 2-tape TM that decides if a string is a palindrome.

    122a? U 11Ra R L U 1= U a1 2 a= a? U 21,2 LRU

    1 21 a? a? U a= U

     No Yes

    4

    Now when asked if our machine can be thought of as an algorithm, we can discus that it may and may not, depending if it decides or only semi-decides a language. An algorithm according to its definition is "a well-ordered collection of unambiguous and effectively computable operations that when

    1executed produces a result and halts in a finite amount of time". According to this

    definition of an algorithm we say that a Two-tape Turing Machine that decides a language can be compared with an algorithm because it produces a result and halts. On the other hand a 2-tape TM that only semi-decides a language cannot be viewed as an algorithm since it is possible that it never halts, thus breaking one of the conditions for being an algorithm.

    We had said earlier that our 2-tape machine was not more powerful than a single tape TM. We claim that this is true because there exists a theorem in our text book that essentially says that given a 2-tape

    a) 2-tape Turing Machine TM call it M=(K,,,s, H) with all

    ; a a U b U the specifications we had defined

    Head 1

    earlier, then there is also a standard

    ; a b a U U 111 111TM call it M = (K,,,s, H)

    Head 2 1where such that the following ,b) Simulation of two-tape in one-tape Turing Machine

    holds: For any input string x *, M ; a a U b U

     1 0 0 0 0 0 ; U U halts on input x with output y on the

     ; a b a U U 1 first tape if and only if M halts on 0 0 1 0 0 0

    input x at the same halting state, and

     1 http://www.columbia.edu/~tah10/cs1001/algorithm.html

    5

    with the same output y on its tape. Furthermore, if M halts on input x after t steps, then 1 halts on input x after a number of steps which is O(t (|x| + t)). M*

     We will not give the whole proof of this theorem but instead we will only give a brief explanation of how a single tape TM would simulate a 2 tape TM. The basic idea is that it would split its single tape into 4 compartments. The 4 compartments will be paired in groups of two. Every simulated tape has another tape that will only contain 0’s and 1’s

    as input. This tape’s function is to keep track of where the head is on both tape. Since our

    1single tape machine M only has one head it needs this extra tape to simulate a second head. A picture of how this simulation would work as follows.

    Next we claim that non-determinism does not allow our machine to accept a greater range of languages. Recall the theorem from our text book that says that “if a nondeterministic TM M semi-decides or decides a language, or computes a function, then

    1 there is a standard TM Msemi-deciding or deciding the same language, or computing

    the same function.” (Text

    Book, 224) Since our

    Unsolvable Problems machine is basically 2

    Turing Machines: Both deterministic and non standard machines put deterministic. Accept programming lang

    together this same theorem

    Non-deterministic PDA, CF applies to our machine and languages

    we can say that non-

    Deterministic PDA can

    accept CF languages determinism does not

    Regular increase the computational Languages

    power of it.

    Chomsky

    Hierarchy

    6

Exercise Problems:

    1) Draw a diagram of a 2-tape TM that creates the string “www”, given “w” on the

    first tape.

    R2) Draw a diagram of a 2-tape TM that creates the string “www”, given “w” on the

    first tape.

    Solutions to Exercise Problems: 1) First we copy the contents of tape one into tape 2. Then we copy the string in tape 2 to

    the end of the string in tape 1 two times.

    12a? U 1,2 a R

     1 = a2a? U 211,2 1U LLRa U

    2 = a2a? U 211,2 1U LLRa U

    2) For this problem the basic idea is to leave the string “w” in the second tape. We use it

    Rto add the strings “w” and “w” to tape 1.

    12a? U 1,2 a R

     1 = a

    U 2a? U 1211LLR a

    2 = a2a? U 11,2 1U LRa

    7

Report this document

For any questions or suggestions please email
cust-service@docsford.com