Turing Machines

 

    A Turing Machine Program has three components.

1.      Alphabet

This is the set of symbols used in instructions which may or

may not be the same as the alphabet of inputs/output strings.

2.      An infinite tape: 2-way infinite

3.      An unordered set of instructions.

There are different versions of instructions such as

      Quadruples (default) and

      Quintuples.

 

Quadruple Turing Machines have three quadruple instructions:

            Qi        Sj         Sk        Ql        // Rewrite the current tape square (Print Quad)

            Qi        Sj         R         Ql        // Move to Right

            Qi        Sj         L         Ql        // Move to Left

    

Turing Machine Programs operate based upon

            The Current state and

            The Current tape symbol.

 

EX:     

            A = {1}

            Quadruples:

                        Q1       B         R         Q2

                        Q2       1          R         Q2

                        Q2       B         1          Q3

                        Q3       1          R         Q3

                        Q3       B         1          Q1       // “Q1  1” is the terminating   

                                                                        // combination.

 

            This program computes f(x) = x+2, not strictly

 

            The following program computes the same function Strictly:

 

                        Q1       B         R         Q2

                        Q2       1          R         Q2

                        Q2       B         1          Q3

                        Q3       1          R         Q3

                        Q3       B         1          Q4

                        Q4       1          L         Q4

                        Q4       B         B         Q5       “Q5  B” is the terminating combination

 

THM:

Any TM (program) can be converted into an equivalent Quintuple TM (program)

 

            Quintuple TMs have the following two quintuple instructions:

            1.         Qi  Sj  Sk  R  Ql

            2.         Qi  Sj  Sk  L  Ql

 

            Quintuple-1: If the given current state and the given

current tape symbol together match, then a (possibly) new

symbol will be printed into the

            current tape square before moving to the right.   

            Quintuple-2: Similar except that the move is to the left.

 

 

            EX:

           

            Q1       B         R         Q2       // just one quintuple needed

            Q2       a          R         Q2       // just one quintuple needed

            Q2       b          R         Q2       // just one quintuple needed

            Q2       B         c          Q3       // many quintuples needed due to

                                                            // unwanted move, R-move.

            Q2       c          c          Q2       // many quintuples needed

 

            Equivalent Quintuple TM:

 

            Q1       B         B         R         Q2

            Q2       a          a          R         Q2

            Q2       b          b          R         Q2

            Q2       B         c          R         Q6       // unwanted R-move

            Q6       B         B         L         Q3       // Undo R-move

            Q6       a          a          L         Q3       // Undo R-move

            Q6       b          b          L         Q3       // Undo R-move

            Q6       c          c          L         Q3       // Undo R-move

            Q2       c          c          R         Q5       // unwanted R-move

            Q5       B         B         L         Q2

            Q5       a          a          L         Q2

            Q5       b          b          L         Q2

            Q5       c          c          L         Q2

 

 

A Universal Turing Machine                                  

 

Just as we had a Universal function and a Universal program, it is rather straightforward

to think of a Universal Turing Machine as a TM that is equivalent to a Universal program,

as an immediate consequence of above Corollary that equivalences all

Turing machines and all PC functions and all Programs in L

(The numeric-processing SIMPLE Language)

 

TM as an acceptor of a language

 

In addition to computing PC functions, another capacity of TM’s is in accepting

a certain language which is a (possibly infinite) set of strings on a certain alphabet.

 

            1. An alphabet, A,  out of which strings are to be formed.

                This same alphabet can be considered as that of a TM.

            2. We say that a string x (in A^* ) is accepted by a TM if and only if this

                TM stops after starting with the initial tape configuration with the

    string x included as the input string.

3. Given a TM, M, the language accepted by this TM, denoted by,         

     L(M).

                 L(M) = {x | x is accepted by this TM}                            

 

            EX:     A = {a,b}

Q1       B         R         Q2

                        Q2       a          a          Q3

                        Q2       B         B         Q2       // infinite loop not to accept

// the l.

                        Q2       b          b          Q2       // infinite loop not to accept a

                                                                        // string

                                                                        // starting with a ‘b’

Q3       a          R         Q3

                        Q3       B         B         Q3       // infinite loop not to accept a

// string

                                                                        // consisting only of ‘a’’s

                        Q3       b          b          Q4

                        Q4       b          R         Q4

                        Q4       a          a          Q4       // “Q4 B” is the terminating

// combination           

           

                        NOTE: L(M) = a⁺ b⁺

 

                        The computation of this TM is given below when the

 input string is “aabbb”:

 

                        ...BBB Q₁ BaabbbBBB...                  ->

                        ...BBBB Q₂ aabbbBBB...                  ->

                        ...BBBBa Q₃ abbbBBB...                  ->

                        ...BBBBaa Q₃ bbbBBB...                  ->

                        ...BBBBaab Q₄ bbBBB...                  ->

                        ...BBBBaabb Q₄ bBBB...                  ->

                        ...BBBBaabbb Q₄ BBB...                  ->

           

Each above is called an I.D., instantaneous description that clearly

describes the computation so far done up to a certain point in time..

           

Equivalence of TM’s and RE sets

 

THM 3.1

A language is accepted by a TM if and only if it is RE.

            Proof:

            1. Suppose that a language L is accepted by a TM, M.

                Let f(x) be the PC function computed by this TM.

                L = L(M) = { x | f(x) is defined }

                So, L is RE.

            2. Suppose that a language L is RE.

                Then, there is a PC function f(x) such that L = { x | f(x) is defined }  

                This PC function must be computed by a TM say M.

                Then L = L(M). So, it is accepted by a TM.

            QED.

 

NOTE:                      

Any language L consisting only of strings of ‘1’’s can be considered as a

set of numbers and it is RE if and only if it is accepted by a TM.                       

 

TM Halting problem

 

Just as the Halting problem (for programs) is unsolvable, TM Halting problem

is unsolvable as programs and TM’s are equivalent.

THM4.1 says just a little bit more than that.

    

There is a TM with alphabet {1} that has an unsolvable halting problem.

 

     Proof:

     Let S be an RE language on {1} that is not recursive.

     And, let a TM M be such that  L(M) = S.

     Then, the halting problem of this TM is unsolvable as if it were solvable

     then S would be recursive.

 

Reduction of a problem to another problem.

 

Often, we can use an unsolvable problem in showing that another problem is

also unsolvable. In this case we can use a reduction method.

           

Definition of Problem Reduction

Given two problems A and B, we say that A is reduced to B if and only

if every possible instance of problem A is transformed into an instance of problem B

so that by solving the latter instance ( of B) we can solve the former instance (of A).

 

NOTE:

1. When A is reduced to B, all possible instances of A are covered but not all

     instances of problem B.

2. The problem B is at least as hard as problem A.

    So, if problem A is unsolvable then so is problem B as if B were solvable

    then A would be solvable.

 

EX: TM State Problem                                                                    

  

Given a TM and an input string and a state of this TM, the problem of deciding

whether this TM ever enters the given state on taking the given input string.

 

Given a TM, M1, on alphabet {1}, we can construct another TM M2

on the same alphabet as follows:

Assume that the last state of M1 is Q_k        

1. M2 will have all the quadruples of M1 and in addition it will have

            2. a quadruple of the form:  Qi Sj Sj Q_k+1 

                for every combination of Qi and Sj that M1 does not have

                where Qi is one of the states of M1,

               Sj is either B or ‘1’ and

                           Q_k+1   is a state that M1 does not have.

           

Now, we have just reduced the M1 halting problem to the M2 State problem

for the state Q_k+1  of M2.

That is, if we can solve the problem of deciding whether or not TM M2 ever

enters the state  Q_k+1  then we would be solvable the Halting problem of M1.

 

Since the Halting problem of arbitrary TM is unsolvable, the State Problem of

arbitrary TM is unsolvable as this particular TM’s State Problem is unsolvable.

 

Nondeterministic TM (NDTM) and deterministic TM (DTM)

 

A Deterministic TM is a TM that does not have two quadruples with the same

combination of the current state and the current tape symbol.

And, a nonterministic TM is any TM with no such restriction.

That is, a nondeterministic TM may or may not have two quadruples starting

with the same two components (of the current state and the current tape symbol).   

So, A DTM is just a special case of a NDTM.

 

            EX:     A = {a,b}

Q1  B  R  Q2  // this quad and the next one make

// the TM truly nondet.

                        Q1  B  R  Q3 

                        Q2  a   B  Q3

                        Q3  B  R  Q3

                        Q3  a    B  Q4 // Q4 = at least one ‘a’ erased.

                        Q4   B  R  Q4

                        Q4   a   R  Q4

                        Q4   b   R  Q5 // Q5 = at least one ‘b’ found

                        Q4   c   c   Q4  // input string has a ‘c’

                        Q5   b   R  Q5

                        Q5   B  L   Q6 // Q6 = rightend of remaining input substring.

                        Q6   b   B  Q7 // Q7 = one ‘b’ erased (rightmost one)

                        Q7  B  L   Q8  // Q8 = remaining substring must be empty or right

                        Q8  b   L  Q9  // Q9 = remaining substring has at least one ‘b’

                        Q9  b  L   Q9

                        Q9  a   a   Q3  // Leftmost remaining ‘a’ found.

                        Q9  B  B  Q9   // input string has more ‘b’’s than ‘a’’s

                        Q8  a   a   Q8  // input string has more ‘a’’s than ‘b’’s

                        Q3  b   b   Q3  // input string starts with a ‘b’ or has more ‘b’’s

                        Q2  b   b   Q2 // input string starts with a ‘b’

                        Q2  B  B  Q2   // input string empty

                        Q5  a   a   Q5  // input string has ‘a’ after ‘b’’s

 

                        “Q8 B” is the accepting terminating condition.                 

                        L is supposed to be: L =  {a^m b^m   +  a^m+1 b^m | m>=1}                   

  

 

Equivalence among many versions of TM

 

  1.  Quadruple TM’s

  2.  Quintuple TM’s

  3.  One-Way infinite tape TM’s

  4.  Nondeterministic TM’s

 

  The equivalence of the first two has already been established.

  The equivalence between DTM’s and NDTM’s is involved:

            1. Conversion from DTM to NDTM is trivial.

            2. Conversion from NDTM to DTM is involved.

                We will examine this in the next chapter.

 

  The equivalence between TM’s with one-way infinite tape and those

  with two-way infinite tape.

            1. Conversion from the former to latter is trivial.

            2. Conversion from the latter to the former is involved a little bit.

 

Major steps involved in simulating a two-way infinite tape TM M1 by

a one-way infinite tape TM M2.

 

Key idea:

Regard a two-way  infinite tape as being “hinged” so it can be folded to become

a one-way infinite tape  with two tracks, an upper track and a lower track.

1. Let the alphabet of M1 be A = {S1,S2, ..., Sn} and its states be {Q1,Q2, ...,  

    Qk} and we assume that it computes a unary function f(x).

2. Just as M1 starts with the initial I.D. of: 

             ...BBBB Q1 B X BBB...       where X is the input string.

                M2 will start with the initial I.D. of:

                 # Q1 B X BBB...   where ‘#’ is a special symbol to mark the

                                       leftend of one-way infinite tape for most of the computation.

3. The alphabet of M2 will be:  

            A + {#} + {b ⁱ _j    | 0 <= i,j <= n} where  b ⁱ _j  represents two symbols

                        S_i on the upper track and  S_j  on the lower track.

4. The states of M2 will be:

            {Q1, Q2, Q3, Q4, Q5} + {P_i  , R_i    | 1<=i<=K}

and some additional states.

5. M2 quadruples are made up of three sections:

                        BEGINNING

                        MIDDLE

                        ENDING       

6. BEGINNING

    To copy the input of M1 on the upper track putting blanks on the correspondng

     lower track of each square occupied by the input string.

    This section will have the following quadruples:

                        Q1  B  R  Q2

                        Q2  Si  R  Q2  // for 1 <= i <= n

                        Q2  B  L  Q3

                        Q3  Si   Sⁱ ₀  Q3           // for 0 <= i <= n

                        Q3  Sⁱ ₀  L  Q3 // for 0 <= i <= n

                        Q3  #   R  P1

     This section turns the initial I.D. from

                        ...BBB # Q1 B S2 S1 S3 BBB...    to

                        # P1  b²₀    b¹₀  b³₀  BBB ...

 

7.  MIDDLE

     This section will have quadruples corresponding to those of M1 plus some

      more for switchover between the upper and the lower tracks and also for

      turning the original blanks into modified blanks when necessary.

                 a.    Qi  Sj  Sk  Ql              Pi b^j _m   b^k _m   Pl                      // 0<=m<=n

                                                            Ri b^m _j   b^m _k   Rl                     // 0<=m<=n

                 b.    Qi  Sj   R  Ql               Pi  b^j _m   R   Pl                        // 0<=m<=n

                                                            Ri  b^m _j    L   Rl                       // 0<=m<=n

                 c.    Qi  Sj   L  Ql               Pi  b^j _m   L   Pl             // 0<=m<=n

                                                            Ri  b^m _j    R   Rl                       // 0<=m<=n

                 d.     Additions                  Pi  B    b⁰₀    Pi                         // 1 <= i <= K

                                                            Ri  B    b⁰₀    Ri                        // 1 <= i <= K

                                                            Pi  #     R    Ri                         // 1 <= i <= K

                                                            Ri  #     R     Pi                         // 1 <= i <= K

8.  ENDING

     This section will have quadruples needed for converting the output strings

     in the modified alphabet into equivalent strings in the original alphabet of M1.

     To begin with, it has the following quadruples:

     a.     For each combination, Qi Sj, which no quadruple of M1 contains:

                        Pi  b^j _m   b^j_m   Q4                     // 0 <= m <= n

                        Ri  b^m_j   b^m_j   Q4                     // 0 <= m <= n

     b.                Q4   b^m_k   L   Q4                     // 0 <= m,k <= n

                        Q4   #      B   Q5                     // 0 <= m,k <= n

 

     c.     Above parts of this section is to produce the following I.D.:

 

                        B  Q5   bⁱ¹_j1  bⁱ²_j2  ... b ^ik_jk  BBB ...

 

     The remaining task of this section is to convert above I.D. into

      a tape contents of:

                        S_jk S_jk-1 S_{jk -2  ,...,} S_j1  S _i1 S _i2  ,..., S _ik