October 29

* Computing Functions with TMs

  We are interested here in computability, not efficiency

  We use unary or binary notation for input and output

  - i is represented by 0^i
  - i can also be represented in binary with 0s and 1s
  - M(i) = output of M when given input i
  - if i0^i |-*M k_halt 0^j then we say M(i) = j
  - Every TM computes some function IN -> OUT
    (which may not be defined on all arguments)
  - We can represent multiple arguments  as
    0^i1 1 0^i2 1 ... 1 0^in

* Example

  Addition of two unary numbers

  000001000   Add 5 to 3 to get 00000000 = 8

  The TM simply finds the separating "`", replaces it with a "0", then replaces
  each "0" with "0" while moving right until the blank is encountered.  It ehn
  backs up one cell and erases the last (rightmost) "0".


* Example

  Proper substruction (monus)

  m -. n = m-n   if m-n>=0
	    0    otherwise


  M "computes" function f if, for all w in Sigma*, M(w) = f(w).
  A function f is "recursive" if there is a Turing machine M that computes f.

* Extensions of TMs

  - Multiple Tracks
  - Two-Way Infinite Tape
  - Multiple Tapes
  - Nondeterministic TMs
  - Multidimensional TMs

  - Multiple Tracks

    Suppose we extend the definition of TM and allow "multiple tracks" - the
    tape is partitioned into some finite # of tracks, each individually
    readable/writeable.  The read/write head points to one column of all tracks.

    TM with 4 tracks
      +-------------------------------+
    1 |0|1|1|0| | | | | | | | | | | | | ...
      +-------------------------------+
    2 |$|1|0|0|1| | | | | | | | | | | | ...
      +-------------------------------+
    3 |a|b|b|c|a|a|a| | | | | | | | | | ...
      +-------------------------------+
    4 | | |2| | | | | | | | | | | | | | ...
      +-------------------------------+

    This TM is easily simulated by a single-track TM that has a funny alphabet
    containing symbols of the form

       +-+
       |0|
       +-+
       |1|
       +-+
       |a|
       +-+
       |b|
       +-+

    The transition function delta can be constructed to ignore portions of the
    symbol in which it is not interested,

    so to change the bottom track from b to c (and move L) would include
    transitions of the form

             +-+        +-+
             |x|        |x|
             +-+        +-+
    delta(k, |y|) = (k, |y|, L)   forall x, y, z
             +-+        +-+
             |z|        |z|
             +-+        +-+
             |b|        |c|
             +-+        +-+

    This extension does give us some flexibility.

    Example
       Add binary numbers (of same length)

               +---+---+---+---+---+---+---+---+---+
       Input:  | $ |a1 |a2 |...| # |b1 |b2 |...|bn |  ai, bi in {0,1}
               +---+---+---+---+---+---+---+---+---+

       Pre-processing stage
	  Go to last non-blank symbol bi, remember it (erase it) and return to
	     leftmost symbol ai and replace it with
	     +--+
	     |ai|
	     +--+
	     |bi|
	     +--+.  Repeat.
                                                  a1 a2 ... an
       At end of pre-processing stage, input is $ b1 b2     bn

       New addition is easy - start at right, and move left adding and using
       finite control for the carry bit.


		  +-------+<-------------+ +-+     +-+     +-+  
		  |Carry=0|              | |0|     |1|     |0|
		  +-------+--------------+ +-+/0,L +-+/1,L +-+/1,L
		  |       ^                |0|     |0|     |1|
		  |       |                +-+     +-+     +-+
		  |       |
		  |       |
        +-+       |       |   +-+
        |0|       |       |   |1|
        +-+ / 1, L|       |   +-+ / 0, L
        |0|       |       |   |1|
        +-+       |       |   +-+
		  v       |
		  +-------+<-------------+ +-+     +-+     +-+
		  |Carry=1|              | |1|     |0|     |1|
		  +-------+--------------+ +-+/0,L +-+/0,L +-+/1,L
					   |0|     |1|     |1|
					   +-+     +-+     +-+




       End
	  If in state Carry=1 and $ is encountered, replace $ with 1 and go
	  to k_halt.  Final configuration is k_halt w, where w is
	  n+1-bit pattern for the sum.

	  If in state Carry=0 and $ is encountered, shift left one cell.



   Example

      Check off symbols in 0^n 1^n
      Just use two tracks

	 +-+
	 |0|   One to store input
	 +-+
	 |X|   One to check off symbols
	 +-+


   Because we can simulate multitrack TM with a TM with one track, we have shown
   that adding tracks does not increase the power of a TM.


   - Two-Way Infinite Tape

        +--+--+--+--+--+---+--+--+--+--+
     ...|  |  |  |a1|a2|...|an|  |  |  |...
        +--+--+--+--+--+---+--+--+--+--+
		  ^
		  |
		  TM starts here at first cell of input word

     To simulate a TM with 2-way infinite tape using a
		   TM with 1-way infinite tape:


     1) Use two tracks

	   +--+--+--+--+--+--+
	   | 0| 1| 2| 3| 4| 5| ...
	   +--+--+--+--+--+--+
	   | 0|-1|-2|-3|-4|-5| ...
	   +--+--+--+--+--+--+

	OR

     2) Alternate cells

	   +--+--+--+--+--+--+--+
	   | 0|-1| 1|-2| 2|-3| 3| ...
	   +--+--+--+--+--+--+--+

	OR

     3) Whenever TM being simulated wants to move left (past $), we shift over
	by 1 to make more room

	+--+--+--+             +--+--+--+--+
	| $|a1|a2| ...    =>   | $|  |a1|a2| ...
	+--+--+--+             +--+--+--+--+


   - Multitape TMs

     These are much easier to program.  After showing that a single tape can
     simulate a multitape, TM, we may use this model at will.

     A k-tape M has k different 2-way-infinite tapes and k read/write heads.

     Input initially on Tape 1; Tapes 2, ..., k-1, k are blank

     Single move:  Read k symbols under read heads
		   Print k new symbols (possibly different) on tapes
		   Move k heads (possibly different directions)

     Transitions are of the form
	delta(k, a1, ..., ak) = (k', b1, .., bk, D1, ..., Dk)

	From state s with ai scanned on Tape i, change ai to bi and move
	in direction Di for each i = 1, 2, ,,, k.


     Theorem:

	L accepted by k-tape TM => L accepted by 1-tape TM

     Proof:
	If M is a k-tape TM, there exists M' with 1 tape that simulates M
	   using 2k tracks

	Track 2i contains contents of Tape i of M, 1<=i<=k.

	Track 2i + 1 contains marker under cell scanned on Tape i of M.

	If M has 2 tapes, configuration is

                            |
                            v
		-------+-+-+-+-+-+-------
		       |0|1|1|0|1|               Tape 1
		-------+-+-+-+-+-+-------

                          |
                          v
		-------+-+-+-+-+-+-------
		       |0|1|1|0|1|               Tape 2
		-------+-+-+-+-+-+-------


	Then M' with 1 tape (4 tracks) looks like

	-----+-+-+-+-+-+-+-+-------
	     |0|1|1|0|1| | |
	-----+-+-+-+-+-+-+-+-------
	     | | |X| | | | |
	-----+-+-+-+-+-+-+-+-------
	     |0|1|1|0|1| | |
	-----+-+-+-+-+-+-+-+-------
	     | |X| | | | | |
	-----+-+-+-+-+-+-+-+-------

	A single move of M is simulated by many moves of M'.

	1.  Sweep from leftmost symbol on tape that contains a checkmark across
	    to rightmost symbol that contains checkmark, recording in finite
	    control the k symbols scanned under different heads.

	    (must "count" up to k in finite control)

	    Implementation:  Start in state    (k "?" symbols)
	       indicating that we do not yet know what the k symbols scanned
	       by M are.


               When we see, for example,
	       +-+
	       | |
	       +-+
	       | |
	       +-+
	       |1|
	       +-+ we change from state  to 
	       |X|
	       +-+ because we know tape 2 contains a 1 under the read/write head
	       | |
	       +-+
	       | |
	       +-+

	2.  After all the "?" symbols are replaced with information about cells
	    scanned by M, state is something like .

	    Now sweep back to the left, making changes as dictated by
	    M's transition function.  This involves changing the scanned symbol
	    and possibly moving the head.

	    Note that a move of the head to the right will require more work.


   - Nondeterministic TMs

     For a deterministic TM |delta(s,a)| <= 1.

     For a nondeterministic TM delta(s,a) is a finite set of possibilities.
     NTM accepts with if there exists a sequence of moves leading to some
     accepting (halting) state.

     Note that extra tapes, two way tapes, etc. do not increase power of NTMs.

     L accepted by NTM M <=> there exists M' s.t. DTM accepts L.


   - Multidimensional TMs

     Multitrack TM with an infinite number of tracks

             ^
             |

     +-+-+-+-+-+-+-+   2 dimensional TM
     | | | | | | | |
     +-+-+-+-+-+-+-+
     | | | | | | | |
     +-+-+-+-+-+-+-+ ->
     | | | | | | | |
     +-+-+-+-+-+-+-+
     | | | | | | | |
     +-+-+-+-+-+-+-+
     | | | | | | | |
     +-+-+-+-+-+-+-+

     Operates on a grid of k dimensions

     The input is written along the first axis initially.

     The transition function delta specifies directions
	{L,R,U,D} for 2 dimensions
     for k dimensions, it specifies one of 2k directions.

     Theorem:  forall k, if L is accepted by k-dim TM, then L is accepted by
	       1-dim TM

     Proof:  Only finite amount of cells used at any point.  In x moves, the
	     head can not move outside of a k-dimensional hypercube of side
	     length x.

	     "Linearize" the cube by computing offsets similar to manner in
	     which arrays are stored in memory

	       +--+--+--+--+
	       | 1| 2| 3| 4|  The numbers in this 2-dimensional TM tape
	       +--+--+--+--+  indicate location in "linear" memory where
	       | 5| 6| 7| 8|  cell is stored.
	       +--+--+--+--+
	       | 9|10|11|12|
	       +--+--+--+--+
	       |13|14|15|16|
	       +--+--+--+--+

	     If the TM moves outside of the current cube, redo everything for a
	     larger cube (double cube size, recompute offsets, lay out contents
	     linearly based on new offsets).


   - Multihead TM

     No additional computability power.
     Can simulate with standard TM.
     Use tracks in a way similar to the k-tape TM argument.


   - Random-Access TM

     Read section in book



* Review Exam Topics