Introduction to Complexity Theory: Church-Turing Thesis and Turing Machines
Explore the Church-Turing Thesis and the power of Turing machines in Complexity Theory. Discuss objections, responses, and left-right-stationary Turing machines challenging the thesis, with implications and theorems examined.
Uploaded on | 2 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
The Church-Turing Thesis Let ? be a language Church-Turing Thesis: There exists an algorithm / procedure for figuring Intuitive notion out whether a given string is in ? if and only if there Mathematically precise notion exists a Turing machine that decides ?. 2
Are Turing machines too powerful? OBJECTION: The Turing machine s infinite tape is unrealistic! RESPONSE 1: If ? decides some language, then on any particular input ?, ? only uses a finite amount of space RESPONSE 2: We are studying idealized computation RESPONSE 3: We re especially focused on impossibility results, so it s better to err on the side of making the model extra powerful 3
Are Turing machines powerful enough? OBJECTION: To encompass all possible algorithms, we should add various bells and whistles to the Turing machine model. Example: Let s define a left-right-stationary Turing machine just like an ordinary Turing machine, except now the transition function has the form ?:? ? {L,R,S} S means the head does not move in this step (prohibited if we see ) (Exercise: Rigorously define NEXT, accepting, rejecting, etc.) 4
Left-right-stationary Turing machines The left-right-stationary Turing machine model poses a challenge to the Church-Turing thesis, because the model is still realistic, even though we added an extra feature Does the Church-Turing thesis survive this challenge? Yes, because the left-right-stationary Turing machine model is equivalent to the original Turing machine model, in the following sense: 5
Left-right-stationary Turing machines Let ? be a language Theorem: There exists a left-right-stationary TM that decides ? if and only if there exists a TM that decides ? Proof: The direction is trivial, because a TM can be considered a left-right-stationary TM that just happens to never use S 6
Left-right-stationary Turing machines Idea of the proof of : Simulate S by doing L followed by R Details: Let ? = ?, , , , ,?,?0,?accept,?reject be a left-right-stationary TM that decides ? New TM: ? = ? , , , , ,? ,?0,?accept,?reject New set of states: ? = ? ? ? ? , i.e., two disjoint copies of ? 7
Left-right-stationary Turing machines New transition function ? :? ? L,R given by: If ? ?,? = ? ,? ,L , then ? ?,? = ?(?,?) If ? ?,? = ? ,? ,R , then ? ?,? = ?(?,?) If ? ?,? = ? ,? ,S , then ? ?,? = ? ,? ,L For every ? and ?, we let ? ?,? = ?,?,R Exercise: Rigorously prove that ? decides ? 8
The Church-Turing Thesis Let ? be a language Church-Turing Thesis: There exists an algorithm / procedure for figuring Intuitive notion out whether a given string is in ? if and only if there Mathematically precise notion exists a Turing machine that decides ?. 9
In each step, what determines the actions of head 1? Multi-tape Turing machines A:Head 1 s state and the symbol observed by head 1 B:The machine s state and the symbols observed by all heads Another TM variant: ?-tape TM C:Head 1 s state and the symbols observed by all heads D:The machine s state and the symbol observed by head 1 Transition function: Respond at PollEv.com/whoza or text whoza to 22333 1 1 0 ?:? ? ? ? {L,R, S}? (Exercise: Rigorously define acceptance, rejection, etc.) # 1 0 $ ? 10
How should we keep track of the locations of the simulated heads? Multi-tape Turing machines A: Store the location data in the machine s state B: Ensure that the real/simulated heads locations are always equal C: Use special symbols to mark the cells containing simulated heads D: Store the location data in a single dedicated tape cell Let ? be any positive integer and let ? be a language Respond at PollEv.com/whoza or text whoza to 22333 Theorem: There exists a ?-tape TM that decides ? if and only if there exists a 1-tape TM that decides ? 11
Simulating ? tapes with 1 tape Idea: Pack a bunch of data into each cell 1 1 0 Store simulated heads on the tape, along with ? simulated symbols in each cell # 1 0 $ ? 12
Simulating ? tapes with 1 tape Idea: Pack a bunch of data into each cell 1 0 1 0 Store simulated heads on the # 1 0 $ tape, along with ? simulated symbols in each cell The one real head will scan back and forth, updating the simulated heads locations and the simulated tape contents. (Details on the next slides) 13
Simulating ? tapes with 1 tape Let ? = ?, , , , ,?,?0,?accept,?reject be a ?-tape Turing machine that decides ? We will define a 1-tape Turing machine ,?accept,?reject ? = ? , , , , ,? ,?0 that also decides ? 14
Simulating ? tapes with 1 tape: Alphabet Let = ? ? , i.e., two disjoint copies of Interpretation: An underline indicates the presence of a simulated head ?1 ?? New alphabet: = , ?1, ,?? Interpretation: One symbol in is one simulated column of ? ? , so Identify each input symbol ? with the new symbol 15
Simulating ? tapes with 1 tape: Head statuses At each moment, each simulated head will have one of the following statuses: ?,? where ? and ? L,R,S Interpretation: The simulated head needs to write ? and move in direction ? Interpretation: The simulated head is not currently depicted on the real tape; the simulated head s location is currently the same as the real head s location ? where ? Interpretation: In the next simulated step, the simulated head will read ? 16
Simulating ? tapes with 1 tape: Head statuses Let be the set of all possible statuses for a single simulated head: = ?,? ? ,? L,R,S ? ? 17
Simulating ? tapes with 1 tape: States New state set: ?1 ?? ? = ?accept,?reject ?1, ,?? ; ? ?; ? L,R ?,? Interpretation: Simulated head ? has status ?? The simulated machine is in state ? The one real head is making a pass over the tape in direction ? 18
Simulating ? tapes with 1 tape: Start state New start state: = ?0 ?0,R 19
Simulating ? tapes with 1 tape: Transitions The new transition function will have the form ? :? ? L,R 20
Simulating ? tapes with 1 tape: Transitions ?1 ?? ?1 ?? ?1 ?? ?1 ?? ,?? are defined by: Let ? , = , ,? where ?? ?,? ?,? = ?? = ?? If ??= Let ?? and ?? : = ?? = ?? If ??= ??,S and ?? has an underline: Let ?? and ?? = ?? = If ??= ??,? and ?? has an underline: Let ?? and ?? = ?? = ?? In all other cases: Let ?? and ?? 21
Simulating ? tapes with 1 tape: Transitions ?1 ?? ?1 ?? ?1 ?? ,?? are defined by: Let ? , = , ,L where ?? ?,R ?,L = = If ??= Let ?? and ?? : = = ?? In all other cases: Let ?? and ?? 22
Simulating ? tapes with 1 tape: Transitions What do we do when we see ? Let ?1, ,?? (head statuses) and let ? ? Assume that ?, either ??= ?? or ??= . In the latter case, let ??= Let ? ,?1, ,??,?1, ,?? = ? ?,?1, ,?? = ??,?? . If ??= = If ??= ?? , let ?? , let ?? ?1 ?? ?1 ?? Let ? = ? if ? is a halting state and , , ,R otherwise ?,L ? ,R 23
