A Universal Turing Machine Prof. Busch - LSU 1 A limitation of Turing Machines: Turing Machines are “hardwired” they execute only one program Real Computers are re-programmable Prof. Busch - LSU 2 Solution: Universal Turing Machine Attributes: • Reprogrammable machine • Simulates any other Turing Machine Prof. Busch - LSU 3 Universal Turing Machine simulates any Turing Machine M Input of Universal Turing Machine: Description of transitions of M Input string of M Prof. Busch - LSU 4 Tape 1 Three tapes Description of M Universal Turing Machine Tape 2 Tape Contents of M Tape 3 Prof. Busch - LSU State of M 5 Tape 1 Description of M We describe Turing machine M as a string of symbols: We encode M as a string of symbols Prof. Busch - LSU 6 Alphabet Encoding Symbols: a b c d Encoding: 1 11 111 1111 Prof. Busch - LSU 7 State Encoding States: q1 Encoding: 1 q2 11 q3 q4 111 1111 Head Move Encoding Move: L R Encoding: 1 11 Prof. Busch - LSU 8 Transition Encoding Transition: ( q1 , a ) ( q 2 , b , L ) Encoding: 1 0 1 0 11 0 11 0 1 separator Prof. Busch - LSU 9 Turing Machine Encoding Transitions: ( q1 , a ) ( q 2 , b , L ) ( q 2 , b ) ( q3 , c , R ) Encoding: 1 0 1 0 11 0 11 0 1 00 11 0 1 10 111 0 111 0 11 separator Prof. Busch - LSU 10 Tape 1 contents of Universal Turing Machine: binary encoding of the simulated machine M Tape 1 1 0 1 0 11 0 11 0 10011 0 1 10 111 0 111 0 1100 Prof. Busch - LSU 11 A Turing Machine is described with a binary string of 0’s and 1’s Therefore: The set of Turing machines forms a language: each string of this language is the binary encoding of a Turing Machine Prof. Busch - LSU 12 Language of Turing Machines (Turing Machine 1) L = { 010100101, 00100100101111, 111010011110010101, (Turing Machine 2) …… …… } Prof. Busch - LSU 13 Countable Sets Prof. Busch - LSU 14 Infinite sets are either: Countable or Uncountable Prof. Busch - LSU 15 Countable set: There is a one to one correspondence of elements of the set to Natural numbers (Positive Integers) (every element of the set is mapped to a number such that no two elements are mapped to same number) Prof. Busch - LSU 16 Example: The set of even integers is countable Even integers: (positive) 0, 2, 4, 6, Correspondence: Positive integers: 1, 2 , 3, 4 , 2 n corresponds to n 1 Prof. Busch - LSU 17 Example: The set of rational numbers is countable Rational numbers: 1 , 2 Prof. Busch - LSU 3 4 , 7 , 8 18 Naïve Approach Rational numbers: Nominator 1 1 1 1 , , , 1 2 3 Correspondence: Positive integers: 1, 2 , 3, Doesn’t work: we will never count numbers with nominator 2: Prof. Busch - LSU 2 1 , 2 2 , 2 , 3 19 Better Approach 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 20 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 21 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 22 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 23 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 24 1 1 1 1 1 2 3 4 2 2 2 1 2 3 3 3 1 2 4 1 Prof. Busch - LSU 25 Rational Numbers: 1 1 , 1 2 , 2 1 , 1 3 , 2 , 2 Correspondence: Positive Integers: 1, 2 , 3 , 4 , 5 , Prof. Busch - LSU 26 We proved: the set of rational numbers is countable by describing an enumeration procedure (enumerator) for the correspondence to natural numbers Prof. Busch - LSU 27 Definition Let S be a set of strings (Language) An enumerator for S is a Turing Machine that generates (prints on tape) all the strings of S one by one and each string is generated in finite time Prof. Busch - LSU 28 strings s1 , s 2 , s 3 , S Enumerator Machine for S output s1 , s 2 , s 3 , (on tape) Finite time: Prof. Busch - LSU t1 , t 2 , t 3 , 29 Enumerator Machine Time 0 Configuration q0 prints s1 Time t1 x1 # s1 qs Prof. Busch - LSU 30 Time t 2 prints s 2 x2 # s2 qs Time t 3 prints s 3 x3 # s 3 qs Prof. Busch - LSU 31 Observation: If for a set S there is an enumerator, then the set is countable The enumerator describes the correspondence of S to natural numbers Prof. Busch - LSU 32 Example: The set of strings S { a , b , c } is countable Approach: We will describe an enumerator for S Prof. Busch - LSU 33 Naive enumerator: Produce the strings in lexicographic order: s1 s2 a aa aaa aaaa ...... Doesn’t work: strings starting with b will never be produced Prof. Busch - LSU 34 Better procedure: Proper Order (Canonical Order) 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 .......... Prof. Busch - LSU 35 s1 s2 a b c length 1 aa Produce strings in Proper Order: ab ac ba bb bc ca length 2 cb cc aaa aab aac ...... Prof. Busch - LSU length 3 36 Theorem: The set of all Turing Machines is countable Proof: Any Turing Machine can be encoded with a binary string of 0’s and 1’s Find an enumeration procedure for the set of Turing Machine strings Prof. Busch - LSU 37 Enumerator: Repeat 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 Prof. Busch - LSU 38 Binary strings Turing Machines 0 1 00 01 1 0 1 0 11 0 11 0 0 1 0 1 0 11 0 11 0 1 s1 s2 1 0 11 0 1010010101 101 1 0 1 0 11 0 11 0 1 1 0 11 0 1010010101 101 End of Proof Prof. Busch - LSU 39 Uncountable Sets Prof. Busch - LSU 40 We will prove that there is a language L which is not accepted by any Turing machine Technique: Turing machines are countable Languages are uncountable (there are more languages than Turing Machines) Prof. Busch - LSU 41 Definition: A set is uncountable if it is not countable We will prove that there is a language which is not accepted by any Turing machine Prof. Busch - LSU 42 Theorem: If S is an infinite countable set, then the powerset 2 S of S is uncountable. (the powerset 2 S is the set whose elements are all possible sets made from the elements of S ) Prof. Busch - LSU 43 Proof: Since S is countable, we can write S { s1 , s 2 , s 3 , } Elements of S Prof. Busch - LSU 44 Elements of the powerset 2 S have the form: { s1 , s 3 } { s 5 , s 7 , s 9 , s10 } …… Prof. Busch - LSU 45 We encode each element of the powerset with a binary string of 0’s and 1’s Powerset element Binary encoding s1 s2 s3 s4 { s1 } 1 0 0 0 {s2 ,s 3 } 0 1 1 0 { s1 , s 3 , s 4 } 1 0 1 1 (in arbitrary order) Prof. Busch - LSU 46 Observation: Every infinite binary string corresponds to an element of the powerset: Example: 10 0 111 0 Corresponds to: { s1 , s 4 , s 5 , s 6 , } 2 Prof. Busch - LSU S 47 Let’s assume (for contradiction) S that the powerset 2 is countable Then: we can enumerate the elements of the powerset 2 S {t1 , t 2 , t 3 , } Prof. Busch - LSU 48 suppose that this is the respective Powerset element Binary encoding t1 1 0 0 0 0 t2 1 1 0 0 0 t3 1 1 0 1 0 t4 1 1 0 0 1 Prof. Busch - LSU 49 Take the binary string whose bits are the complement of the diagonal t1 1 0 0 0 0 t2 1 1 0 0 0 t3 1 1 0 1 0 t4 1 1 0 0 1 Binary string: t 0011 (birary complement of diagonal) Prof. Busch - LSU 50 The binary string corresponds to an element of S the powerset 2 : t 0011 t {s 3 , s 4 , } 2 Prof. Busch - LSU S 51 Thus, t must be equal to some t i t ti However, the i-th bit in the encoding of t is the complement of the i-th bit of t i , thus: t ti Contradiction!!! Prof. Busch - LSU 52 Since we have a contradiction: The powerset 2 S of S is uncountable End of proof Prof. Busch - LSU 53 An Application: Languages Consider Alphabet : A { a , b } The set of all Strings: * S { a , b } { , a , b , aa , ab , ba , bb , aaa , aab , } infinite and countable (we can enumerate the strings in proper order) Prof. Busch - LSU 54 Consider Alphabet : A { a , b } The set of all Strings: * S { a , b } { , a , b , aa , ab , ba , bb , aaa , aab , } infinite and countable Any language is a subset of S : L { aa , ab , aab } Prof. Busch - LSU 55 Consider Alphabet : A { a , b } The set of all Strings: * * S A { a , b } { , a , b , aa , ab , ba , bb , aaa , aab , } infinite and countable The powerset of S contains all languages: 2 S { , { }, { a }, { a , b }, { aa , b },..., { aa , ab , aab }, } uncountable Prof. Busch - LSU 56 Consider Alphabet : A { a , b } countable Turing machines: M1 M2 M3 L2 L3 accepts Languages accepted By Turing Machines: L1 Denote: X { L1 , L 2 , L3 , } countable Prof. Busch - LSU countable Note: X 2 S {a , b } * S 57 Languages accepted by Turing machines: X countable All possible languages: 2 S Therefore: since S uncountable X 2 X 2 , we have X 2 Prof. Busch - LSU S S 58 Conclusion: There is a language L not accepted by any Turing Machine: X 2 S L 2 S and L X (Language L cannot be described by any algorithm) Prof. Busch - LSU 59 Non Turing-Acceptable Languages L Turing-Acceptable Languages Prof. Busch - LSU 60 Note that: X { L1 , L 2 , L3 , } is a multi-set (elements may repeat) since a language may be accepted by more than one Turing machine However, if we remove the repeated elements, the resulting set is again countable since every element still corresponds to a positive integer Prof. Busch - LSU 61

Descargar
# Languages and Finite Automata