```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

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).

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
```