This problem set is fully released. There is not a new problem on universality, but there is a question to think about that gives you some idea of what universality material might look like.

This problem set is due Tuesday 30 November at 5pm ON PAPER (1 copy is fine) in AC312; electronic backup is appreciated but paper turn-in is mandatory.

Fun with Turing Machines

1. Let M be the Turing machine with

   • states q₀, q₁, q₂, and h

   • alphabet a, _, +

   • start state q₀

   • final state h

   • and transition table:

     • ( in_state, read_symbol )	( to_state, write_symbol, move )
       ( q0 a )	( q1, a, L )
       ( q0 _ )	( q0, _, S )
       ( q0 + )	( q0, +, R )
       ( q1 a )	( q2, _, S )
       ( q1 _ )	( h, _, S )
       ( q1 + )	( q1, +, R )
       ( q2 a )	( q2, a, S )
       ( q2 _ )	( q0, _, L )
       ( q2 + )	( q2, +, R )

   Let n be an integer >= 0. Describe carefully what M does when started in the configuration

   • (q₀, +_aⁿa)

   i.e., start state q₀ and tape contents +_aⁿa. Note that this machine is not starting at the beginning of the tape; the start position is underlined on the tape contents. (Optional bonus: If you run this under JFLAP, you will need to add a little bit of TM code at the beginning to get the machine to the start configuration. Turn in this code, either as additions to the TM description above or by printing out your JFLAP machine. I happily accept electronic submission of .jff files in addition to, but not in place of, paper copies.)

Build Your Own TMs

1. Build a Turing Machine to recognize the set of strings with equal numbers of as, bs, and cs. (You should assume that there are no other characters in this language but may use designated start, end, and cross-out symbols to your tape.) Turn in either the transition table and formal TM description or a picture of the TM state machine. (The second is slightly preferred.)

2. Build a Turing Machine that takes as input a non-negative number N in binary representation -- base 2 -- and adds 1 to this number, in binary. Specifically, the tape initially contains a $ followed by N in binary. The tape head is initially scanning the $ in state q₀. Your TM should halt with the binary representation of the number N+1 on the tape, scanning the leftmost symbol of the binary representation for N+1, in some state q_f. You may destroy the $ in creating N+1 if necessary. For instance, if the tape starts with $10011 it should end with $10100 and if it starts with $11111 it may end with 100000 (destroying the $).

Universality/Computability

• There is nothing to turn in for this section. However, you should be familiar with these ideas:
  • universal turing machine
  • decision problem/decidability
  • semi-decidability, aka recognition
  • decidability proof by algorithmic reduction to a decidable problem
  • diagonalization
  You should also be familiar with the Halting Theorem and its proof. Pseudo-question: Prove that a decision problem D is decidable iff both D and D-complement are semi-decidable. (Specifically, show how to decide D given semi-deciders for D and D-complement; show how to semi-decide D and D complement given a decision procedure for D.)

These problems are drawn from the Theory Books used from this course.