Complexity Theory: Understanding Turing Machines and Computation Models
Explore the concepts of Turing machines, the Church-Turing thesis, and the power of computation models like multi-tape Turing machines. Delve into the possibilities and limitations of algorithms in complexity theory.
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 2025 Instructor: William Hoza 1
Which problems Which problems can be solved can be solved through computation? through computation? 2
The Church-Turing Thesis Let ? 0,1 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 ?. 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: Left-Right-Stationary Turing Machine: Like an ordinary Turing machine, except it has a transition function ?:? ? {L,R,S} S means the head does not move in this step (Exercise: Rigorously define NEXT, accepting, rejecting, etc.) 4
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 ? 5
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 $ ? 6
Multi-tape Turing machines Let ? be any positive integer and let ? be a language Theorem: There exists a ?-tape TM that decides ? if and only if there exists a 1-tape TM that decides ? How should we keep track of the locations of the simulated heads? A: Store the location data in the machine s state B: Ensure that the real/simulated heads locations are always equal Proof on upcoming 14 slides C: Use special symbols to mark the cells containing simulated heads D: Store the location data in a single dedicated tape cell Respond at PollEv.com/whoza or text whoza to 22333 7
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 $ ? 8
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) 9
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 ? = ? ,?0 , , ,? ,?reject that also decides ? 10
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 ? 0 1 Technicality: Encode input over the alphabet , instead of 0,1 11
Simulating 2 tapes with 1 tape: States 1 0 1 # 0 # 1 $ 0 $ State of ? ? ? ? ? ? ? R R L L L ? ? 1 # # # # ? 0 0 R R ? ? ? ? ? ? Direction of ? motion State of ? ? 1 1 1 1 1 0,L 0,R ,L ,L ,L ,L #,R Head 1 instruction Head 1 symbol Head 2 instruction Head 2 symbol 12
Simulating ? tapes with 1 tape: States New state set: ? ? ? L,R ?1, ,?? ? ?1, ,?? L,R,S ? ?1 ?? ? ?1 ?? ? = {?} 13
Simulating ? tapes with 1 tape: Start state New start state: ?0 ? R ? = ?0 ? ? 14
Simulating ? tapes with 1 tape: Transitions ? ? ? ?1 ?? ? ?1 ?? ?1 ?1 ?? ?1 ?? ?1 ?? ? , = , ?? ,? = ?, = ?, = ? If ??= ?,? and ??= ??: Let ?? ?? ?? = ?, = ?, = ? If ??= ?,S and ??= ??: Let ?? ?? ?? = ??, = ?, = ?? If ??= ? and ??= ?: Let ?? ?? ?? = ??, = ??, = ?? In all other cases: Let ?? ?? ?? 15
Simulating ? tapes with 1 tape: Transitions ? R ? L ?1 ?1 ?? ?1 ?? ?1 ?? ?1 ?? ? , = , ?? ,L = , = ?, = If ??= ? and ??= ?: Let ?? ?? ?? = ??, = ??, = In all other cases: Let ?? ?? ?? 16
Simulating ? tapes with 1 tape: Transitions ? ? L R ?1 ?1 ?? ?1 ?? ?1 ?? ?1 ?? ? , = , ?? ,R Let ? ,?1, ,??,?1, ,?? = ? ?,?1, ,??, treating ??= ? as ??= = ?, = ?, = If ? is a halting state: Let ?? ?? ?? = , = ??,??, = If ??= ? and ??= ?: Let ?? ?? ?? = ??, = ??,??, = In all other cases: Let ?? ?? ?? 17
Simulating ? tapes with 1 tape: Halting states R R ?accept ? ? ?reject ? ? ? ? ? ? ?accept = ?reject = 18
Simulating ? tapes with 1 tape That completes the definition of ? Exercise: Rigorously prove that ? decides the language ? 19
TMs can simulate all reasonable machines We could add various other bells and whistles to the basic TM model The ability to observe the two neighboring cells The ability to teleport back to the initial cell in a single step A two-dimensional tape None of these changes has any effect on the power of the model 20
