Turing Machine ExtensionsProblem Encoding, TM Encoding, and the Universal TMExample: 101/1/10/10/11/1/100/10/101Turing Machine ExtensionsRead K & S 4.3.1, 4.4.Do Homework 19.Turing Machine DefinitionsAn alternative definition of a Turing machine:(K, , , , s, H): is a finite set of allowable tape symbols. One of these is . is a subset of not including , the input symbols. is a function from: K to K ( - {}) {, } state, tape symbol, L or R a b b a Example transition: ((s, a), (s, b, ))Do these Differences Matter?Remember the goal:Define a device that is: powerful enough to describe all computable things, simple enough that we can reason formally about itBoth definitions are simple enough to work with, although details may make specific arguments easier or harder.But, do they differ in their power?Answer: No.Consider the differences: One way or two way infinite tape: we're about to show that we can simulate two way infinite with ours. Rewrite and move at the same time: just affects (linearly) the number of moves it takes to solve a problem.Turing Machine ExtensionsIn fact, there are lots of extensions we can make to our basic Turing machine model. They may make it easier to write Turing machine programs, but none of them increase the power of the Turing machine because:We can show that every extended machine has an equivalent basic machine.We can also place a bound on any change in the complexity of a solution when we go from an extended machine to a basic machine.Some possible extensions: Multiple tapes Two-way infinite tape Multiple read heads Two dimensional “sheet” instead of a tape Random access machine Nondeterministic machineLecture Notes 23 Turing Machine Extensions 1Multiple Tapes a b b a b a b b a 1 2 2 1 The transition function for a k-tape Turing machine:((K-H) , 1 to (K, 1' {, }, 2 , 2' {, }, . , ., . , ., k) , k' {, })Input: input as before on tape 1, others blankOutput: output as before on tape 1, others ignoredAn Example of a Two Tape MachineCopying a string a b b a a b b a a b b a a b b a a b b a Lecture Notes 23 Turing Machine Extensions 2Another Two Tape Example - Addition 1 0 1 ; 1 1 0 0 0 0 0 1 1 0 1 0 1 Adding Tapes Adds No PowerTheorem: Let M be a k-tape Turing machine for some k 1. Then there is a standard Turing machine M' where ', and such that: For any input string x, M on input x halts with output y on the first tape iff M' on input x halts at the same halting state and with the same output on its tape. If, on input x, M halts after t steps, then M' halts after a number of steps which is O(t (|x| + t)).Proof: By construction a b a 0 0 1 0 0 0 0 a b b a b a0 1 0 0 0 0 0Alphabet (') of M' = ( {0, 1})ke.g., , (, 0, , 0), (, 0, a, 1)The Operation of M' a b a 0 0 1 0 0 0 0 a b b a b a0 1 0 0 0 0 01. Set up the multitrack tape:1) Shift input one square to right, then set up each square appropriately.2. Simulate the computation of M until (if) M would halt: (start each step to the right of the divided tape)1) Scan left and store in the state the k-tuple of characters under the read heads. Move back right.2) Scan left and update each track as required by the transitions of M. Move back right.i) If necessary, subdivide a new square into tracks.3. When M would halt, reformat the tape to throw away all but track 1, position the head correctly, then go to M's halt state.How Many Steps Does M' Take?Let: x be the input string, and t be the number of steps it takes M to execute.Step 1 (initialization) O(|x|)Step 2 ( computation)Number of passes = tWork at each pass: 2.1 = 2 (length of tape) = 2 (|x| + 2 + t)2.2 = 2 (|x| + 2 + t)Total = O(t (|x| + t))Step 3 (clean up) O(length of tape)Total = O(t (|x| + t))Lecture Notes 23 Turing Machine Extensions 3Two-Way Infinite TapeOur current definition: a b c d Proposed definition: g f e a b c d Simulation:Track 1 a b c d Track 2 e f g Simulating a PDAThe components of a PDA: Finite state controller Input tape StackThe simulation: Finite state controller: Input tape: Stack:Track 1 a a a b b (Input)Track 2 a a Corresponding toaaSimulating a Turing Machine with a PDA with Two Stacks a b a a # a a b a a # a a b a a b a Lecture Notes 23 Turing Machine Extensions 4Random Access Turing MachinesA random access Turing machine has: a fixed number of registers a finite length program, composed of instructions with operators such as read, write, load, store, add, sub, jump a tape a program counterTheorem: Standard Turing machines and random access Turing machines compute the same things. Furthermore, the numberof steps it takes a standard machine is bounded by a polynomial in the number of steps it takes a random access machine.Nondeterministic Turing MachinesA nondeterministic Turing machine is a quintuple (K, , , s, H)where K, , s, and H are as for standard Turing machines, and is a subset of((K - H) ) (K ( {, }))abababab abababab bbabWhat does it mean for a nondeterministic Turing machine to compute something? Semidecides - at least one halts. Decides - ? Computes - ?Nondeterministic SemidecidingLet M = (K, , , s, H) be a nondeterministic Turing machine. We say that M accepts an input w ( - {, })* iff (s, w) yields a least one accepting configuration.We say that M semidecides a language L ( - {, })* ifffor all w ( - {, })*: w L iff (s, w) yields a least one halting configuration.An ExampleL = {w {a, b, c, d}* : there are two of at least
View Full Document
Unlocking...