Turing Machines: Answers
    1. The final configuration is: (q2,##abba#)
    2. The final configuration is: (q2,##baaaab#)
    3. For an arbitrary input string w in {a,b}*, starting in the initial configuration (q0,#w#), this Turing machine halts with configuration (q2,##wwR#)

    1. The sequence of configurations is as follows:

      (q0,abaa#)
      (q1,Abaa#)
      (q1,Abaa#)
      (q1,Abaa#)
      (q1,Abaa#)
      (q2,Abaa#)
      (q3,AbaA#)
      (q3,AbaA#)
      (q3,AbaA#)
      (q0,AbaA#)
      (q1,ABaA#)
      (q1,ABaA#)
      (q2,ABaA#)
      (q3,ABAA#)
      (q0,ABAA#)
      (q4,ABAA#)
      (q4,AbAA#)
      (q4,<abAA#)
      (q5,abAA#)
      (q7,AbAA#)
      (q7,AbAA#)
      (q8,Ab#A#)
      (q8,Ab#A#)
      (q5,Ab#A#)
      (q6,AB#A#)
      (q6,AB#A#)
      Crash

    2. The sequence of configurations is as follows:

      (q0,abab#)
      (q1,Abab#)
      (q1,Abab#)
      (q1,Abab#)
      (q1,Abab#)
      (q2,Abab#)
      (q3,AbaB#)
      (q3,AbaB#)
      (q3,AbaB#)
      (q0,AbaB#)
      (q1,ABaB#)
      (q1,ABaB#)
      (q2,ABaB#)
      (q3,ABAB#)
      (q0,ABAB#)
      (q4,ABAB#)
      (q4,AbAB#)
      (q4,<abAB#)
      (q5,abAB#)
      (q7,AbAB#)
      (q7,AbAB#)
      (q8,Ab#B#)
      (q8,Ab#B#)
      (q5,Ab#B#)
      (q6,AB#B#)
      (q6,AB#B#)
      (q8,AB###)
      (q8,AB###)
      (q5,AB###)
      Accept

    3. The language accepted by this Turing machine is {ww | w Î {a,b}*}

  3. A Turing machine to accept this language has the following transitions with start state q0

    State Symbol d(State,Symbol)
    q0 a (q1,#,R)
    q0 b (q2,b,R)
    q1 a (q1,a,R)
    q1 b (q1,b,R)
    q1 # (q3,#,L)
    q2 b (q2,b,R)
    q2 # (q2,#,Y)
    q3 b (q4,#,L)
    q4 a (q4,a,L)
    q4 b (q4,b,L)
    q4 # (q0,#,R)


  4. A Turing machine to accept this language has the following transitions with start state q0

    State Symbol d(State,Symbol)
    q0 a (q1,x,L)
    q0 b (q2,b,R)
    q0 x (q0,x,R)
    q0 # (q0,#,Y)
    q1 b (q1,b,L)
    q1 x (q1,x,L)
    q1 < (q3,<,R)
    q2 a (q1,x,L)
    q2 b (q2,b,R)
    q2 x (q2,x,R)
    q3 a (q3,a,R)
    q3 x (q3,x,R)
    q3 b (q4,x,L)
    q4 a (q4,a,L)
    q4 x (q4,x,L)
    q4 < (q0,<,R)


  5. A Turing machine to accept this language has the following transitions with start state q0

    State Symbol d(State,Symbol)
    q0 a (q1,#,R)
    q0 b (q4,#,R)
    q0 # (q0,#,Y)
    q1 a (q1,a,R)
    q1 b (q1,b,R)
    q1 # (q2,#,L)
    q2 a (q3,#,L)
    q2 # (q2,#,Y)
    q3 a (q3,a,L)
    q3 b (q3,b,L)
    q3 # (q0,#,R)
    q4 a (q4,a,R)
    q4 b (q4,b,R)
    q4 # (q5,#,L)
    q5 b (q3,#,L)
    q5 # (q5,#,Y)


    1. A Turing machine to compute this function has the following transitions with start state q0:

      State Symbol d(State,Symbol)
      q0 1 (q0,1,R)
      q0 # (q1,1,R)
      q1 # (q1,1,Y)


    2. A Turing machine to compute this function has the following transitions with start state q0:

      State Symbol d(State,Symbol)
      q0 1 (q1,#,R)
      q0 x (q0,1,R)
      q0 # (q0,#,Y)
      q1 1 (q1,1,R)
      q1 x (q1,x,R)
      q1 # (q2,x,L)
      q2 1 (q2,1,L)
      q2 x (q2,x,L)
      q2 # (q0,1,R)


    3. A Turing machine to compute this function has the following transitions with start state q0:

      State Symbol d(State,Symbol)
      q0 1 (q0,1,R)
      q0 # (q1,#,L)
      q1 1 (q2,#,L)
      q1 # (q1,#,Y)
      q2 1 (q1,#,L)
      q2 # (q1,1,Y)



  7. A Turing machine to compute this function has the following transitions with start state q0:

    State Symbol d(State,Symbol)
    q0 a (q1,#,L)
    q0 # (q0,#,Y)
    q1 # (q2,a,R)
    q2 # (q0,#,R)


  8. Let M be a linear bounded automaton with q states and s symbols. For an input string of length n, the maximum amount of tape which will be used will be of length n. There are therefore sn possible strings which can appear on the tape. As there are n possible positions for the tape head and q possible states, there are qnsn possible configurations. If M has not halted within qnsn steps, it must be in a repeating configuration, and therefore looping. We can therefore decide after this number of steps whether or not the input string will be accepted or rejected. As linear-bounded automata are recognisers for context-sensitive languages, every context-sensitive language must be recursive.

  9. A derivation of this sentence is as follows:

    S
    => ABCS
    => ABCABCS
    => ABCABCABCS
    => ABCABCABCZ
    => ABACBCABCZ
    => AABCBCABCZ
    => AABBCCABCZ
    => AABBCACBCZ
    => AABBACCBCZ
    => AABABCCBCZ
    => AAABBCCBCZ
    => AAABBCBCCZ
    => AAABBBCCCZ
    => AAABBBCCZc
    => AAABBBCZcc
    => AAABBBYccc
    => AAABBYbccc
    => AAABYbbccc
    => AAAXbbbccc
    => AAXabbbccc
    => AXaabbbccc
    => Xaaabbbccc
    => aaabbbccc

    The language generated by this grammar is: {anbncn | n > 0}

  10. Show that the following functions are primitive recursive:
    1. A primitive rescursive definition for this function is as follows:

      factorial(0) = succ(0)
      factorial(succ(n)) = mult(succ(n),factorial(n))

      As mult is primitive recursive, factorial is also primitive recursive.

    2. A primitive recursive definition for this function is as follows:

      gcd(m,0) = m
      gcd(m,succ(n)) = gcd(succ(n),mod(m,succ(n)))

      As mod is primitive recursive, gcd is primitive recursive.