Question? Leave a message!




Theory of Computation

Theory of Computation 27
OscarTucker Profile Pic
OscarTucker,Singapore,Professional
Published Date:19-07-2017
Website URL
Comment
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 one-to-one 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 one-to-one 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 ini-th line andj-th 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/54