Turing's Variations PDF

Turing’s Thesis 1 Turing’s thesis (1930): Any computation carried out by mechanical means can be performed by a Turing Machine 2 Algorithm: An algorithm for a problem is a Turing Machine which solves the problem The...

Turing’s Thesis 1 Turing’s thesis (1930): Any computation carried out by mechanical means can be performed by a Turing Machine 2 Algorithm: An algorithm for a problem is a Turing Machine which solves the problem The algorithm describes the steps of the mechanical means This is easily translated to computation steps of a Turing machine 3 When we say: There exists an algorithm We mean: There exists a Turing Machine that executes the algorithm 4  Variations of the Turing Machine 5  The Standard Model Infinite Tape ◊ ◊aababbcac a◊◊◊ Read-Write Head (Left or Right) Control Unit Deterministic 6  Variations of the Standard Model Turing machines with: Stay-Option Semi-Infinite Tape Off-Line Multitape Multidimensional Nondeterministic Different Turing Machine Classes 7 Same Power of two machine classes: both classes accept the same set of languages We will prove: each new class has the same power with Standard Turing Machine (accept Turing-Recognizable Languages) 8 Same Power of two classes means: for any machine M1 of first class there is a machine M 2 of second class such that: L( M1 ) = L( M 2 ) and vice-versa 9 Simulation: A technique to prove same power. Simulate the machine of one class with a machine of the other class Second Class First Class Simulation Machine Original Machine M2 M1 M1 simulates M1 10 Configurations in the Original Machine M1 have corresponding configurations in the Simulation Machine M 2 M1 Original Machine: d0  d1    d n ∗ ∗ ∗ Simulation Machine: d 0′  d1′    d n′ M2 11  Accepting Configuration Original Machine: df Simulation Machine: d ′f the Simulation Machine and the Original Machine accept the same strings L( M1 ) = L( M 2 ) 12  Turing Machines with Stay-Option The head can stay in the same position ◊ ◊aababbcac a◊◊◊ Left, Right, Stay L,R,S: possible head moves 13 Example: Time 1 ◊ ◊aababbcac a◊◊◊ q1 Time 2 ◊ ◊b ab abb c ac a◊◊◊ q2 q1 a → b, S q2 14 Theorem: Stay-Option machines have the same power with Standard Turing machines Proof: 1. Stay-Option Machines simulate Standard Turing machines 2. Standard Turing machines simulate Stay-Option machines 15 1. Stay-Option Machines simulate Standard Turing machines Trivial: any standard Turing machine is also a Stay-Option machine 16 2. Standard Turing machines simulate Stay-Option machines We need to simulate the stay head option with two head moves, one left and one right 17  Stay-Option Machine a → b, S q1 q2 Simulation in Standard Machine a → b, L x → x, R q1 q2 For every possible tape symbol x 18 For other transitions nothing changes Stay-Option Machine a → b, L q1 q2 Simulation in Standard Machine a → b, L q1 q2 Similar for Right moves 19  example of simulation Stay-Option Machine: q1 a → b , S q2 ◊aaba ◊ ◊baba ◊ 1 2 q1 q2 Simulation in Standard Machine: ◊aaba ◊ ◊baba ◊ ◊baba ◊ 1 2 3 q1 q2 q3 END OF PROOF 20  Multiple Track Tape A useful trick to perform more complicated simulations One Tape ◊ ◊ a b a b ◊ track 1 ◊ ◊ b a c d ◊ track 2 One head One symbol ( a, b) 21 ◊ ◊ a b a b ◊ track 1 ◊ ◊ b a c d ◊ track 2 q1 ◊ ◊ a c a b ◊ track 1 ◊ ◊ b d c d ◊ track 2 q2 (b, a ) → (c, d ), L q1 q2 22  Semi-Infinite Tape The head extends infinitely only to the right a b a c ◊ ◊......... Initial position is the leftmost cell When the head moves left from the border, it returns to the same position 23 Theorem: Semi-Infinite machines have the same power with Standard Turing machines Proof: 1. Standard Turing machines simulate Semi-Infinite machines 2. Semi-Infinite Machines simulate Standard Turing machines 24 1. Standard Turing machines simulate Semi-Infinite machines: ◊ ◊ # a b a c ◊ ◊ Standard Turing Machine a. insert special symbol # at left of input string b. Add a self-loop #→# , R to every state (except states with no outgoing transitions) 25 2. Semi-Infinite tape machines simulate Standard Turing machines: Standard machine.................. Semi-Infinite tape machine......... Squeeze infinity of both directions in one direction 26  Standard machine.................. ◊ a b c d e ◊ ◊ reference point Semi-Infinite tape machine with two tracks Right part # d e ◊ ◊ ◊......... Left part # c b a ◊ ◊ 27  Standard machine q2 q1 Semi-Infinite tape machine Left part Right part L R q2 R q2 L q1 q1 28  Standard machine a → g, R q1 q2 Semi-Infinite tape machine Right part R ( a, x ) → ( g , x ), R R q1 q2 L ( x, a ) → ( x, g ), L L Left part q1 q2 For all tape symbols x 29 Time 1 Standard machine.................. ◊ a b c d e ◊ ◊ q1 Semi-Infinite tape machine Right part # d e ◊ ◊ ◊......... Left part # c b a ◊ ◊ L q1 30 Time 2 Standard machine.................. ◊ g b c d e ◊ ◊ q2 Semi-Infinite tape machine Right part # d e ◊ ◊ ◊......... Left part # c b g ◊ ◊ L q2 31  At the border: Semi-Infinite tape machine Right part R (# , # ) → (# , # ), R L q1 q1 Left part L (# , # ) → (# , # ), R R q1 q1 32  Semi-Infinite tape machine Time 1 Right part # d e ◊ ◊ ◊......... Left part # c b g ◊ ◊ L q1 Time 2 Right part # d e ◊ ◊ ◊......... Left part # c b g ◊ ◊ R q1 END OF PROOF 33  The Off-Line Machine Input File read-only (once) a b c Input string Input string Appears on input file only Control Unit (state machine) Tape read-write ◊ ◊ g d e ◊ ◊ 34  Theorem: Off-Line machines have the same power with Standard Turing machines Proof: 1. Off-Line machines simulate Standard Turing machines 2. Standard Turing machines simulate Off-Line machines 35 1. Off-line machines simulate Standard Turing Machines Off-line machine: 1. Copy input file to tape 2. Continue computation as in Standard Turing machine 36  Standard machine ◊ a b c ◊ ◊ Off-line machine Input File Tape a b c ◊ ◊ a b c ◊ 1. Copy input file to tape 37  Standard machine ◊ a b c ◊ ◊ q1 Off-line machine Input File Tape a b c ◊ ◊ a b c ◊ q1 2. Do computations as in Turing machine 38 2. Standard Turing machines simulate Off-Line machines: Use a Standard machine with a four-track tape to keep track of the Off-line input file and tape contents 39  Off-line Machine Input File Tape a b c d ◊ ◊ e f g ◊ Standard Machine -- Four track tape # a b c d Input File # 0 0 1 0 head position e f g Tape 0 1 0 head position 40  Reference point (uses special symbol # ) # a b c d Input File # 0 0 1 0 head position # e f g Tape # 0 1 0 head position Repeat for each state transition: 1. Return to reference point 2. Find current input file symbol 3. Find current tape symbol 4. Make transition END OF PROOF 41  Multi-tape Turing Machines Control unit (state machine) Tape 1 Tape 2 ◊ a b c ◊ ◊ e f g ◊ Input string Input string appears on Tape 1 42 Tape 1 Time 1 Tape 2 ◊ a b c ◊ ◊ e f g ◊ q1 q1 Tape 1 Time 2 Tape 2 ◊ a g c ◊ ◊ e d g ◊ q2 q2 (b, f ) → ( g , d ), L, R q1 q2 43  Theorem: Multi-tape machines have the same power with Standard Turing machines Proof: 1. Multi-tape machines simulate Standard Turing machines 2. Standard Turing machines simulate Multi-tape machines 44 1. Multi-tape machines simulate Standard Turing Machines: Trivial: Use just one tape 45 2. Standard Turing machines simulate Multi-tape machines: Standard machine: Uses a multi-track tape to simulate the multiple tapes A tape of the Multi-tape machine corresponds to a pair of tracks 46  Multi-tape Machine Tape 1 Tape 2 ◊ a b c ◊ ◊ e f g h ◊ Standard machine with four track tape a b c Tape 1 0 1 0 head position e f g h Tape 2 0 0 1 0 head position 47 Reference point a b c Tape 1 # # 0 1 0 head position # e f g h Tape 2 # 0 0 1 0 head position Repeat for each state transition: 1. Return to reference point 2. Find current symbol in Tape 1 3. Find current symbol in Tape 2 4. Make transition END OF PROOF 48  Same power doesn’t imply same speed: n n L = {a b } 2 Standard Turing machine: O ( n ) time 2 Go back and forth O ( n ) times to match the a’s with the b’s 2-tape machine: O (n) time 1. Copy b n to tape 2 (O(n) steps) n 2. Compare a on tape 1 n and b tape 2 (O(n) steps) 49  Multidimensional Turing Machines 2-dimensional tape y ◊ ◊ c a x ◊ b ◊ MOVES: L,R,U,D HEAD U: up D: down Position: +2, -1 50  Theorem: Multidimensional machines have the same power with Standard Turing machines Proof: 1. Multidimensional machines simulate Standard Turing machines 2. Standard Turing machines simulate Multi-Dimensional machines 51 1. Multidimensional machines simulate Standard Turing machines Trivial: Use one dimension 52 2. Standard Turing machines simulate Multidimensional machines Standard machine: Use a two track tape Store symbols in track 1 Store coordinates in track 2 53  2-dimensional machine y ◊ ◊ c a x ◊ b ◊ Standard Machine q1 a b c symbols 1 # 1 # 2 # − 1 # − 1 coordinates q1 54 Standard machine: Repeat for each transition followed in the 2-dimensional machine: 1. Update current symbol 2. Compute coordinates of next position 3. Go to new position END OF PROOF 55 Nondeterministic Turing Machines q2 Choice 1 a → b, L q1 a → c, R q3 Choice 2 Allows Non Deterministic Choices 56  Time 0 ◊ a b c ◊ Time 1 q1 Choice 1 q2 ◊ b b c ◊ a → b, L q2 q1 Choice 2 a → c, R q3 ◊ c b c ◊ q3 57  Input string w is accepted if there is a computation: ∗ q0 w  x q f y Initial configuration Final Configuration Any accept state There is a computation: 58  Theorem: Nondeterministic machines have the same power with Standard Turing machines Proof: 1. Nondeterministic machines simulate Standard Turing machines 2. Standard Turing machines simulate Nondeterministic machines 59 1. Nondeterministic Machines simulate Standard (deterministic) Turing Machines Trivial: every deterministic machine is also nondeterministic 60 2. Standard (deterministic) Turing machines simulate Nondeterministic machines: Deterministic machine: Uses a 2-dimensional tape (which is equivalent to 1-dimensional tape) Stores all possible computations of the non-deterministic machine on the 2-dimensional tape 61 All possible computation paths Initial state Step 1 Step 2 Step i reject accept infinite Step i+1 path 62 The Deterministic Turing machine simulates all possible computation paths: simultaneously step-by-step in a breadth-first search fashion 63  NonDeterministic machine q2 Time 0 a → b, L ◊ a b c ◊ q1 q1 a → c, R q3 Deterministic machine # # # # # # # a b c current # # q1 # configuration # # # # # 64  NonDeterministic machine Time 1 q2 ◊ b b c ◊ Choice 1 a → b, L q2 q1 ◊ c b c ◊ Choice 2 a → c, R q3 q3 Deterministic machine # # # # # # # b b c # Computation 1 # q2 # # c b c # Computation 2 # q3 # 65 Deterministic Turing machine Repeat For each configuration in current step of non-deterministic machine, if there are two or more choices: 1. Replicate configuration 2. Change the state in the replicas Until either the input string is accepted or rejected in all configurations END OF PROOF 66 Remark: The simulation takes in the worst case exponential time compared to the shortest accepting path length of the nondeterministic machine 67