LanguagesandFiniteAutomata-ComputerScienceatRPI.ppt

Fall 2006 Costas Busch - RPI A Universal Turing Machine Countable Sets Uncountable Sets If for a set there is an enumerator, then the set is countable Observation: The enumerator describes the correspondence of to natural numbers Example: The set of strings is countable We will describe an enumerator for Approach: Naive enumerator: Produce the strings in lexicographic order: Doesn’t work: strings starting with will never be produced Better procedure: 1. Produce all strings of length 1 2. Produce all strings of length 2 3. Produce all strings of length 3 4. Produce all strings of length 4 .......... Proper Order (Canonical Order) Produce strings in Proper Order: length 2 length 3 length 1 Theorem: The set of all Turing Machines is countable Proof: Find an enumeration procedure for the set of Turing Machine strings Any Turing Machine can be encoded with a binary string of 0’s and 1’s 1. Generate the next binary string of 0’s and 1’s in proper order 2. Check if the string describes a Turing Machine if YES: print string on output tape if NO: ignore string Enumerator: Repeat Binary strings Turing Machines End of Proof We will prove that there is a language which is not accepted by any Turing machine Technique: Turing machines are countable Languages are uncountable (there are more languages than Turing Machines) A set is uncountable if it is not countable Definition: We will prove that there is a language which is not accepted by any Turing machine Theorem: If is an infinite countable set, then the powerset of is uncountable. (the powerset is the set whose elements are all possible sets made from the elements of ) * Turing Machines are “hardwired” they execute only one program A limitation of Turing Machines: Real Computers are re-programmable Solution: Universal Turing Machine Reprogrammable machine Simulates any other Turing Machine Attributes