Question? Leave a message!




Theory of Computation

Theory of Computation 27
a Theory of Computation The Diagonalization Method Teodor Rus ruscs.uiowa.edu The University of Iowa, Department of Computer Science a Copyright Teodor Rus. These lecture notes have been developed by Teodor Rus using the book: Michael Sipser, Introduction to the Theory of Computation (second edition), published by Thomson Course Technology 2006. They are copyrighted materials and may not be used in other course settings outside of the University of Iowa in their current form or modified form without the express written permission of one of the copyright holders. During this course, students are prohibited from selling notes to or being paid for taking notes by any person or commercial firm without the express written permission of one of the copyright holders. Computation Theory. Copyrights Teodor Rus – p.1/54Decidability of TM Language Problem: ForM a Turing machine andw a string, doesM acceptw Language: A =hM,wiM is a TM that acceptsw TM Computation Theory. Copyrights Teodor Rus – p.2/54Solution Theorem 4.11: A is recognizable but not TM decidable. A recognizer ofA is the following TM called TM the Turing Universal MachineU: U = “On inputhM,wi, whereM is a TM andw is a string: 1. SimulatesM onw; 2. IfM ever enters its accept state, accept; ifM ever enters its reject state, reject ". Note: U is a universal TM because it simulates any other TM from its description. Computation Theory. Copyrights Teodor Rus – p.3/54Facts 1. So far we have tackled only solvable (decidable) problems; 2. Theorem 4.11 states thatA is unsolvable (undecidable); TM 3. SinceA is undecidable, to solve this problem we need to TM expand our problem solving methodology by a new method for proving undecidability. Computation Theory. Copyrights Teodor Rus – p.4/54Diagonalization • The proof of undecidability of the halting problem uses Georg Cantor (1873) technique called diagonalization; • Cantor’s problem was to measure the size of infinite sets; • The size of finite sets is measured by counting the number of their elements; Question: can we measure the size of an infinite set by counting the number of its elements Computation Theory. Copyrights Teodor Rus – p.5/54Fact The size of infinite sets cannot be measured by counting their elements because this procedure does not halt Computation Theory. Copyrights Teodor Rus – p.6/54Example Infinite Sets • The set of strings over0,1 is an infinite set; • The setN of natural number is an infinite set; • Both of them are larger than any finite set. How can we compare them ∗ Design a mappingf :N →0,1 by: 1. f(0) =ǫ; ∗ 2. f(n) =x∈0,1 x =n. Computation Theory. Copyrights Teodor Rus – p.7/54Fact ∗ f actually mapsN onP(0,1 ). Since x = y for any x,y ∈ f(n), is an equivalence relation on ∗ ∗ 0,1 and we can considerf :N →0,1 /. Computation Theory. Copyrights Teodor Rus – p.8/54Cantor’s Solution • Two finite sets have the same size if their elements can be paired; • Since this method do not rely on counting elements it can be used for both finite and infinite sets. Computation Theory. Copyrights Teodor Rus – p.9/546 6 The Correspondence Consider two sets,A andB andf :A→B a function. • f is onetoone if it never maps two different elements ofA into the same element ofB, i.e.,∀a,b∈A(a =b⇒f(a) =f(b)); • f is onto if it hits every element ofB, i.e.,∀b∈B,∃a∈A such thatf(a) =b; • f is called a correspondence if it is both onetoone and onto. Note: a correspondence is a mechanism that al lows us to pair elements of two sets. Computation Theory. Copyrights Teodor Rus – p.10/54Set Size Comparison Two setsA andB have the same size if there is a correspondenceF :A→B. Computation Theory. Copyrights Teodor Rus – p.11/54Example Correspondences • LetN be the set of natural numbers,N =1,2,3,... and letE be the set of even natural numbers,E =2,4,6,...; • Intuitively one may believe thatsize(N)size(E). However, using Cantor method we can show thatN andE have the same size by constructing a correspondencef :N →E; • The correspondencef is defined byf(n) = 2n, Figure 1. Computation Theory. Copyrights Teodor Rus – p.12/546 6 sizeof(N) =szeof(E) n f(n) 1 2 2 4 3 6 ... ... Figure 1: sizeof(N) =sizeof(E) Note: 1. ∀n ,n ∈N,n =n ,f(n ) = 2n ,f(n ) = 2n i.e., 1 2 1 2 1 1 2 2 f(n ) =f(n ); 1 2 2. ∀n∈E,n = 2m,m∈N , i.e.,n =f(m). Hence,f is a correspondence and thussizeof(N) =sizeof(E). Computation Theory. Copyrights Teodor Rus – p.13/54Definition 4.12 A set is countable if either it is finite or it has the same size asN . Computation Theory. Copyrights Teodor Rus – p.14/54A Complex Correspondence LetQ be the set of positive rational numbers, m Q = m,n∈N. n • Intuitively,Q seems to be much larger thanN ; • Yet we can show thatsizeof(Q) =sizeof(N) by constructing the correspondence c :N →Q shown in Figure 2. Computation Theory. Copyrights Teodor Rus – p.15/54Correspondencec :Q↔N 1. PutN on two axes; 2. Linei contains all rational numbers that have i numeratori, i.e. ∈Qi∈N fixed,∀j ∈N; j 3. Columnj contains all rational numbers that i have denominatorj, i.e. ∈Q∀i∈N,j ∈N fixed; j i 4. Number occurs inith line andjth column. j Computation Theory. Copyrights Teodor Rus – p.16/54i Turning i,j ∈N into a List j • Bad idea: list first elements of a line or a column. Lines and columns are labeled byN , hence this would never end • Good idea (Cantor’s idea): use the diagonals: 1 1 1. First diagonal contains , i.e, first element of the list is ; 1 1 2 1 2. Continue the list with the elements of the next diagonal: , ; 1 2 3. Continue this way skipping the elements that may generate i 1 repetitions, such that would generate a copy of . i 1 Computation Theory. Copyrights Teodor Rus – p.17/54The List of Rational Numbers ... 1 2 3 4 5      1 1 1 1 1 ... 1 2 3 4 5      1           2 2 2 2 2 ... 1 2 3 4 5      2        3 3 3 3 3 ... 1 2 3 4 5      3        4 4 4 4 4 ... 1 2 3 4 5      4       5 5 5 5 5 ... 1 2 3 4 5      5  ... ... ... ... ... ... ... Figure 2: A correspondence ofN andQ Computation Theory. Copyrights Teodor Rus – p.18/54Uncountable Sets A set for which no correspondence withN can be established is called uncountable. Example of uncountable set: The setR of real numbers is uncountable Proof: Cantor proved thatR is uncountable using the diagonalization method. Computation Theory. Copyrights Teodor Rus – p.19/54Example Uncountable Set Theorem 4.17;R is uncountable. Proof: by contradiction using diagonalization. We will show that no correspondence exist betweenN andR. • Suppose that such a correspondence f :N →R exits and deduce a contradiction showing thatf fail to work properly. • We construct anx∈R that cannot be the image of anyn∈N . Computation Theory. Copyrights Teodor Rus – p.20/54Construction • Sincef :N →R is a correspondenceR can be listed as seen in Figure 3 n f(n) 1 3.14159... 2 55.5555... 3 0.1234... 4 0.5000... ... ... Figure 3: ListingR Notation: forx∈R,d (x) is theith digit ofx. i Computation Theory. Copyrights Teodor Rus – p.21/546 6 Formal Construction ofx Constructx∈ (0,1) by the following procedure: • x = 0.d d d d ... where 1 2 3 4 ∀i∈Nd (x) =d (f(i)) i i Note: x has an infinite number of decimals constructed by the rule: ∀i∈N chosed a digit different from the ith digit of f(i) i • Consequence: ∀i∈N ,x =f(i). Hence,x does not belong to the listR; thusf is not a correspondence. Computation Theory. Copyrights Teodor Rus – p.22/54Application Theorem 4.17 shows that some languages are not decidable or even Turing recognizable. Reason: • There are uncountable many languages yet only countable many Turing machines. • Because each Turing machine can recognize a single language and there are more languages than Turing machines some languages are not recognized by any Turing Machine. • Such languages are not Turing recognizable Computation Theory. Copyrights Teodor Rus – p.23/54Corollary 4.18 Some languages are not Turingrecognizable. Proof: • First we show that the set of Turing machines is countable ∗ 1. The set of all strings Σ is countable, for any alphabet Σ. ∗ Proof: we may form a list Σ by writing down all strings of length 0, length 1, length 2, an so on. 2. Each Turing machineM has an encoding into a stringhMi; 3. If we omit those strings that are not Turing machines we can obtain a list of all Turing machines. Computation Theory. Copyrights Teodor Rus – p.24/54Fact 1 The set of all languages is uncountable. Proof idea: To show that the set of all languages is uncountable we show first that the set of all infinite binary sequences is uncountable. Computation Theory. Copyrights Teodor Rus – p.25/546 6 Infinite Binary Sequences LetB be the set of all infinite binary sequences. • Assuming thatB is countable we can set it into a listf :N →B. b • By the method of diagonalization we can construct an infinite binary stringy, such that y =f (i) for anyi∈N ; b Construction: y =d d ...d ... such that 1 2 j ∀i∀jd ∈0,1∧d =d (f (i) j j j b Computation Theory. Copyrights Teodor Rus – p.26/54Corollary The set of all languages is uncountable. Proof: by construction: LetL be the set of all languages over Σ. • We will show thatL is uncountable by constructing a correspondenceB→L. • SinceB is uncountable, and has the same size asL it result thatL is uncountable. Computation Theory. Copyrights Teodor Rus – p.27/546 6 Characteristic Sequences ∗ ∗ • Since Σ is an alphabet, Σ is countable. Let Σ =s ,s ,s ,... 1 2 3 be the set of all strings over Σ; • For each languageA∈L there is a unique infinite binary sequenceχ ∈B constructed by: A the ith bit ofχ ,χ (i) = 1 ifs ∈A andχ (i) = 0 ifs 6∈A. A A i A i ∗ • χ is the characteristic function ofA in Σ A • The functionf :L→B wheref(A) =χ is onetoone and onto A and hence it is a correspondence. Proof: 1. f is onetoone: ∀L ,L ∈L,L = L ⇒ χ = χ ; 1 2 1 2 L L 1 2 2. f is onto: ∀χ∈B there is a languageL ∈L withf(L) = χ. χ ∗ ∗ ForΣ =s ,s ,...,L =s s ∈ Σ ∧d (χ) = 1. 1 2 χ i i i Computation Theory. Copyrights Teodor Rus – p.28/54Conclusion SinceB is uncountable,L is uncountable. Computation Theory. Copyrights Teodor Rus – p.29/54Example characteristic function Let Σ =0,1 andA be the language of all strings starting with 0 over Σ. \Sigmaˆ =e,0,1,00,01,11,000,001,010,011,100,...; A = 0, ,00,01, ,000,001,010,011, , ...; \chiA =0 1 0 1 1 0 1 1 1 1 ... Computation Theory. Copyrights Teodor Rus – p.30/54Fact 2 ForM a TM, the languageL(M) is undecidable. We are ready to prove that the language A =hM,wiM isaTM andM acceptsw TM is undecidable. Computation Theory. Copyrights Teodor Rus – p.31/54Proof Proceeds by contradiction, assuming thatA is TM decidable. • Suppose thatH is a decider ofA . TM • On inputhM,wi whereM is a TM andw is a string,H halts and accepts ifM acceptsw. • Furthermore,H halts and reject ifM fails to acceptw. Computation Theory. Copyrights Teodor Rus – p.32/54Equational Expression ofH   accept, ifM acceptsw; H(hM,wi) =  reject, ifM does not acceptw. Computation Theory. Copyrights Teodor Rus – p.33/54Proof, Continuation Construct a new TMD that usesH as a subroutine. • D callsH to determine whatM does when its input ishMi • IfM acceptshMi thenD rejects; ifM rejectshMi thenD accepts. Computation Theory. Copyrights Teodor Rus – p.34/54The MachineD D = "On inputhMi, whereM is a TM: 1. RunH on inputhM,hMii 2. Output the opposite of whatH outputs: accepts ifH rejects and rejects ifH accepts". Computation Theory. Copyrights Teodor Rus – p.35/54Note • Running a machine on its own description is a common technique in computer sciences. • Example, running a compiler on its own description allows compiler implementation and optimization. Computation Theory. Copyrights Teodor Rus – p.36/54In Conclusion   accept, ifM does not accepthMi; D(hMi) =  reject, ifM acceptshMi. What happens when we ranD onhDi   accept, ifD does not accepthDi; D(hDi) =  reject, ifD does accepthDi. This is a contradiction and consequently neither TMD nor TMH do exist. Computation Theory. Copyrights Teodor Rus – p.37/54Summarizing • Assume thatH decidesA ; TM • UseH to buildD that acceptshMi whenM rejects it and rejectshMi whenM accepts it; • H andD performs as follows: • H acceptshM,wi exactly whenM acceptsw; • D rejectshMi exactly whenM acceptshMi; • D rejectshDi exactly whenD acceptshDi. This is a contradiction and neitherH norD can exist. Computation Theory. Copyrights Teodor Rus – p.38/54Where Is Diagonalization To make the use of diagonalization obvious we construct the list of all Turing machines running on Turing machines as input in Figures 4,5,6. ... hM i hM i hM i hM i 1 2 3 4 accept accept M 1 ... accept accept accept accept M 2 ... M 3 accept accept M 4 Figure 4: iEntry (i,j) is accept ifM acceptshM i i j Computation Theory. Copyrights Teodor Rus – p.39/54RunningH Figure 5 shows the result of runningH on the machine in Figure 4. ... hM i hM i hM i hM i 1 2 3 4 ... accept reject accept reject M 1 ... accept accept accept accept M 2 ... reject reject reject reject M 3 ... accept accept M rreejjeecctt reject 4 Figure 5: Entry (i,j) is the value ofH onhM ,hM ii i j Computation Theory. Copyrights Teodor Rus – p.40/54RunningD onhDi Figure 6 shows the result of runningH on the machine in Figure 4 whenD is present. ... ... hM i hM i hM i hM i hDi 1 2 3 4 ... ... accept accept accept M reject reject 1 ... ... accept accept accept accept accept M 2 ... ... M reject reject reject reject reject 3 ... ... accept accept reject reject accept M 4 ... ... reject reject accept accept D Figure 6: A contradiction occurs athD,hDii Computation Theory. Copyrights Teodor Rus – p.41/54Observation We can construct a Turingunrecognizable language. • A is an example of Turing undecidable language. But it is TM Turing recognizable; • Now we construct a language which is Turingunrecognizable; • This construction relies on the fact that if both a language and its complement are Turingrecognizable the language is decidable. That is: for any undecidable language, either the language or its complement is not Turingrecognizable. Computation Theory. Copyrights Teodor Rus – p.42/54A New Concept CoTuringrecognizable language. • Complement of a languageA is the language consisting of all strings that does not belong toA; • A language is coTuringrecognizable if it is the complement of a Turingrecognizable language. Computation Theory. Copyrights Teodor Rus – p.43/54An Important Result Theorem 4.22: A language is decidable iff it is both Turingrecognizable and coTuring recognizable. That is: A languageA is decidable iff bothA andC(A) are Turingrecognizable Computation Theory. Copyrights Teodor Rus – p.44/54Proof if: Assume thatA is decidable. Since complement of a decidable language is decidable it result that bothA andC(A) are Turingrecognizable. ForL decidable, decided byM, the TMM that decidesL is: M = “On any inputw: 1. RunM onw 2. IfM accepts reject; ifM rejects accept". Computation Theory. Copyrights Teodor Rus – p.45/54Proof, Continuation only if: Assume that bothA andC(A) are Turingrecognizable. LetM be a 1 recognizer forA andM a recognizer forC(A). Then the following TM 2 M is a decider forA: M = "On inputw: 1. Run bothM andM onw in parallel; 1 2 2. IfM acceptsw accept; ifM acceptsw reject." 1 2 Computation Theory. Copyrights Teodor Rus – p.46/54Observations • Running two machinesM andM by a machineM in parallel 1 2 means thatM has two tapes, one for simulatingM and other for 1 simulatingM ; 2 • M takes turns, simulating one step of each machine, which continues until one of the machines halts; • Becausew∈A orw∈C(A) eitherM orM must acceptsw; 1 2 • BecauseM halts wheneverM orM accepts,M always halts, 1 2 so it is a decider. Further, it accepts all strings fromA and rejects all strings not inA. Computation Theory. Copyrights Teodor Rus – p.47/54Conclusion M is a decider forA, thusA is decidable. Computation Theory. Copyrights Teodor Rus – p.48/54Corollary C(A ) is not Turingrecognizable. TM Proof: We know thatA is Turingrecognizable. TM 1. IfC(A ) also were Turingrecognizable then TM A would be decidable. TM 2. But we have proved (Theorem 4.11) thatA TM is not decidable. 3. Hence,C(A ) cannot be TM Turingrecognizable. Computation Theory. Copyrights Teodor Rus – p.49/54Application 1 LetA be a Turingrecognizable language consisting of descriptions of Turing machines: A =hM i,hM i,... 1 2 where everyM is a decider. i Prove that some decidable languageL is not de D cided by any decider M whose description ap i pears inA. Computation Theory. Copyrights Teodor Rus – p.50/54Solution Sketch Use the diagonalization method to construct a deciderD whose language is not among those decided byM ,i = 1,2,.... i SinceA is Turingrecognizable there is an enumeratorE that enumerates the elements ofA. LethM i,hM i,... be the output ofE. 1 2 Let Λ =s ,s ,... be a list of all strings over the alphabets ofA. 1 2 The decider forD is: D = “On inputw: 1. Leti be the index ofw on the list of stringsΛ, i.e.,s = w. i 2. RunhM i on inputw i 3. IfhM i accepts, reject; i ifhM i rejects, accept". i Note: D is a decider because eachM is a decider. ButD does not appear on the list i enumerated forA, because∀i,D differs fromM on inputs i i Computation Theory. Copyrights Teodor Rus – p.51/54Application 2 Let A and B be two disjoint languages. Say that a language C separates A and B if A ⊆ C and B ⊆ C. Show that any two disjoint coTuring recognizable languages are separable by some decidable language. Computation Theory. Copyrights Teodor Rus – p.52/54Solution Sketch LetA andB be two languages such thatA∩B =∅ andA andB are Turingrecognizable (by definition). LetJ be the TM that recognizesA andK be the TM that recognizes B. Then the languageC decided by the following TMT separatesA andB: T = “On inputw: 1. SimulateJ andK onw by alternating the steps of the two machines; 2. IfJ accepts first, reject. IfK accepts first, accept". Computation Theory. Copyrights Teodor Rus – p.53/54L(T) SeparatesA andB ∗ ∗ ∗ 1. A = Σ \A,B = Σ \B,A∪B = Σ \A∩B. SinceA∩B =∅ it ∗ results thatA∪B = Σ . ∗ ∗ 2. A∪B = Σ implies thatT is a decider because for anyw∈ Σ , w∈A orw∈B. Hence, eitherJ orK will acceptw. 3. A⊆L(T) because ifw∈A,w will not be recognized byJ and will be accepted byK first, i.e.,w∈L(T). 4. B ⊆L(T) because ifw∈B,w will not be recognized byK and will bed accepted byJ first, i.e.,w∈L(T). Conclusion: by the definition of separability, language C = L(T) sepa ratesA andB Computation Theory. Copyrights Teodor Rus – p.54/54
Website URL
Comment