Overview of Turing Machines: Introduction, Tape, and Computation
Turing Machines are fundamental in the theory of computation, capable of recognizing all computable languages. They consist of a Finite State Machine combined with an infinite tape. The tape is initialized with input on the left end, and a TM's computation can either halt by entering special accept or reject states or continue indefinitely. A formal definition of a TM includes key components like the set of states, input and tape alphabets, start, accept, and reject states, and a transition function describing state transitions.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Turing Machines Chuck Cusack Based (very heavily) on notes by Edward Okie (Radford University) and Introduction to the Theory of Computation , 3rdedition, Michael Sipser. (Original version at http://www.radford.edu/~nokie/classes/420/)
Turing Machines: Introduction Turing Machines can recognize all computable languages We will leave the notion of computable language as intuitive We will see well-defined languages that are NOT computable with a TM (or in any other known way) We will see that all known ways of computing have the same power as the TM (or less) Implementation: TM = FSM + Tape!
A Turing Machine's Tape Tape is infinite (in one direction) Tape is initialized with input at left end Rest of tape has blanks Blank is not in the input alphabet Tape has R/W head: Reads and writes the symbol under the head at each transition Moves one symbol left or right at each transition Attempts to move past left end of tape leave tape at left end of tape Machine can NOT tell where the head is on the tape
Example Turing Machine State Diagram for TM recognizing {anbncn|n 0}
Halting a Computation Computation can do one of three things: End (immediately) by entering a special Accept state End (immediately) by entering a special Reject state Continue forever (i.e. never enter either an Accept or Reject state) For comparison, recall the halting conditions for these machines: DFA NFA PDA
Formal Definition of a TM Must define seven items: Q is the set of state is the input alphabet (does not include the blank symbol) is the tape alphabet, blank and : (state, tape symbol) (state, tape symbol, L/R) Start state Accept state Reject state (different from start state)
Transition Function (q,b) (r,c,D) If The machine is in state q, and The tape head is over a b. the machine: goes into state r, writes a c onto the tape (erasing the b), and moves direction D on the tape. Shorthand notation: a D means to read and write an a and to move direction D
Configuration of a TM Show tape head position by writing current state to left of symbol it is over: Example: 1011q701111 Tape contents are 101101111, tape head is over rightmost 0, and machine is in state q7 Accepting/Rejecting Configuration Machine halts when machine enters Accept or Reject State Tape head can be anywhere
Definition: Computation A computation is a sequence of configurations of machine M in which First configuration in the sequence has M in the start state with M's head at the left of the tape Each step in the sequence moves M to the next configuration with a single read, a single write, and a single move
Definition: Acceptinga string Machine M accepts string w iff there is a computation that Starts with the start configuration of w on M (i.e. w written on left end of tape and R/W head at left end) M takes each configuration in the computation to the next configuration The computation ends in an accepting configuration (i.e. in the accept state) No surprises here, but remember the head can be anywhere at the end of the computation
Definition: Recognizinga Language The language recognized by machine M is the collection of strings accepted by M A language that is recognized by a machine is called a Turing Recognizable language Later we'll see that there is some subtlety here For now, remember that language L is TR if there is a TM M for which all strings in L put M in its accept state How do we prove that a language is TR? What happens with strings that are not in L? We will consider that next
TMs and Infinite Loops Question: If a TM is given a string, what can happen to the computation? Answer: The machine can either Accept the string i.e. enter the Accept state and halt the computation Reject the string i.e. enter the Reject state and halt the computation Enter an infinite loop i.e. the computation never ends
Looping on a String We say that a machine loops on a string if the string puts the machine into an infinite loop When a machine loops, it never enters the Accept state or the Reject state it transitions forever among states that are neither the Accept state nor the Reject state Interesting question: Can the other machines we have discussed loop?
Looping on DFAs and NFAs Can a DFA loop? No: computation halts when the end of the input is reached Can an NFA loop? Yes: a computation can make epsilon transitions forever But, every NFA has an equivalent DFA that doesn't loop
Looping on PDAs Can a PDA loop? Yes: computation can make epsilon transitions forever Can every PDA be converted to one that doesn t loop? Create a grammar that accepts the same language as the PDA Create a PDA for that grammar This PDA can be made so that it will halt on all strings We ll have to take this statement on faith since we don t have time to prove it.
Looping on TMs Can an TM loop? Yes: computation can make epsilon transitions forever The TM is a recognizer and not a decider Can every recognizer be converted to one that doesn t loop? In other words: Let M be a TM that accept a language L and loops on some w LC Is it possible to make a TM M' that accepts a language L and halts on all w LC? As we will see soon, sometimes, but not always.
Accepting Complements Another interesting comparison between the models of computation: If a machine (e.g. DFA, NFA, PDA, TM) accepts language L, what can we say about LC (its complement)?
Complements and DFA/NFAs DFA M: L = L(M) = {w| M's unique computation on w reaches accept state} LC= {w| M's unique computation on w reaches non- accept state} NFA N: L = L(N) = {w| Some computation on w reaches an accept state} LC= {w| NO computation on w reaches an accept state} We can use the equivalent DFA to determine if w LC
Complements and PDAs PDA P: L = L(P) = {w| Some computation on w reaches an accept state} LC= {w| NO computation on w reaches an accept state} Can we determine if w LCusing the equivalent PDA that halts on all inputs? Earlier we way that CFLs were not closed under complement, so what do you think?
Complements and TMs TM: L = L(M) = {w| Some computation on w reaches the Accept state} LC= {w| NO computation on w reaches an accept state} A computation that doesn't reach the Accept state can either Reach the Reject state Loop Can we tell if w LC? We will see the answer shortly
Looping and Defining Languages The possibility of looping affects how we define the relationship between a machine and the language it defines TM M recognizes language L iff the strings in L put M into the Accept state the strings not in L EITHER put M into the Reject state OR cause M to loop TM M decides language L iff the strings in L put M into the Accept state the strings not in L put M into the Reject state
Recognizers and Deciders A recognizer for a language is a machine that recognizes that language A decider for a language is a machine that decides that language Both types of machine halt in the Accept state on strings that are in the language A Decider also halts if the string is not in the language A Recognizer MAY or MAY NOT halt on strings that are not in the language On all input: A Decider MUST halt (in Accept or Reject state) A Recognizer MAY or MAY NOT halt on some strings (Q: Which ones?)
Recognizers and Deciders: Equivalent? Is every Decider a Recognizer? Certainly: It halts on strings not in the language Thus it either halts or loops on strings not in the language So it accepts all strings in the language and either halts or loops on strings not in the language Is every Recognizer a Decider? If there is a recognizer that ever loops, then no. But is there such a TM? A better question: Can every Recognizer be converted to a Decider? We ll explore this and a related questions shortly.
More on Recognizers and Deciders Finish this statement: TM M decides language L if M recognizes L and it also_________
Recognizers that cant Decide? If L has a Decider D, can we find a machine R that recognizes L but that does not decide it? It's easy How can we modify one of the previous examples? Thus, if we can decide a language, we can recognize it. Can we find a language L that has a Recognizer but not a Decider? Yes, but we aren t quite ready to discuss this yet.
Turing Decidable and Recognizable Recall: A language is Turing-recognizable (or just recognizable) if some Turing machine recognizes it Also called Recursively Enumerable Language New definition: A language is Turing-decidable (or just decidable) if some Turing machine decides it Also called Recursive Language
Showing that a language is Decidable or Recognizable How do we show that a language L is TD? Build a decider for L How do we show that a language L is TR? Build a decider or a recognizer for L How do we show that a language L is TR but not TD? Build a Recognizer for L PROVE that there is no Decider for L We will see examples of this soon
Relationship among Language Classes What is the relationship between these classes of languages? Regular Context Free Turing Decidable Turing Recognizable All Turing-recognizable Decidable Context-free Regular
Relationship among Language Classes Give an example of a language in each class that is not in the smaller class. Regular? Easy CF but not Regular? Easy Decidable but not CF? Easy Recognizable but NOT Decidable? ? NOT recognizable? ? All All Turing-recognizable Decidable Context-free Turing-recognizable Decidable Context-free Regular Regular
