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 argumentsas 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~~