Theory of Computability
Theory of Computability CS 5000
Utah State University
Popular in Course
Popular in ComputerScienence
This 70 page Class Notes was uploaded by Reed Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CS 5000 at Utah State University taught by Vladimir Kulyukin in Fall. Since its upload, it has received 12 views. For similar materials see /class/230441/cs-5000-utah-state-university in ComputerScienence at Utah State University.
Reviews for Theory of Computability
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/28/15
CS 5000 Lecture 31 Vladimir Kulyukin Department of Computer Science Utah State University Outline Godel Numbers Coding Programs by Numbers A Mathematical Theory of Compilation Review Gc39jdel Numbers Let a1 an be a sequence of numbers a19 9an sz39cli39 i1 a H a is the nth G del number 19 9 n Review Lemma For each n a1 an is primitive recursive Proof p l is primitive recursive xy is primitive recursive so pf is primitive recursive 11 H pf is primitive recursive i1 Gc39jdel Numbers Examples 1 21 12 21 32 123 2 21 32 53 31546 23 3155 74 116 Godel Numbers The Godel number of the empty sequence of prime powers is defined to be 1 In other words 1 Also note that 1 O 20 0 O 2030 0 O O 203050 0 O O 20305070 etc Theorem 82 Ch 3 If a1an b1bn then all 219113139312 Proof Since a1an pf pfquot b1bn b b1 bn 6 1 an b1 n pl pn 9191 pn p1 pn By the Unique Factorization Theorem FTA the powers must be the same Equation 82 a1 an a1 6410 a1 an a1an00 Why Because 19 1 G del Numbers More Examples 23 22 33 108 230 22 33 50 108 023 20 32 53 1125 7 108 Access Function for G del Numbers Laxzkhm hlwewmnmd me a primitive recursive function x 2 at ISiSn Access Function for G del Numbers 122132 18 20 18Yes 2118Yes 22 18NO 30 18Yes 3118Yes 32 18Yes 33 18NO Access Function for G del Numbers To retrieve the ith prime power from a given G del number x Compute the ith prime p For t from O upto x if pitx is not true return t1 Access Function for G del Numbers x min p I x le x0 O O O for alli Example Let 1 8 12 x 11344191 I x Access Function for Gddel Numbers What is the purpose of the access func on The access function gives us a generic procedure to split any natural number into its Godel constituents ie other numbers For example 108 is split into two Godel constituents 2 and 3 because 1081 2 and 1082 3 How Long is a Natural Number LAX 7 O amp Vj x 3 iv xj 0 Lt0 Lt1 0 How Long is a Natural Number Lt20 2 x 20 223051201 Observation If x gt land Ltx n then pnpc but no prime gt p divides x Why Because Lta1an n iff an 7 0 Theorem 83 Ch 3 a flgiSn a1 an 0 Otherwise x1 x if Ltx S n Coding Programs by Numbers Coding Programs by Numbers Coding programs by numbers can be though of as a mathematical theory of compilation The gist of the theory is threefold 1 Any program P is associated with a unique number 2 Given a program P there is a computable function that maps Pto P this function is the compiler 3 Given P there must be a computable function that maps P to P this function is the reverse compiler Mapping P to P Mapping Pto P can be divided into two subtasks 1 Mapping of variables and labels into numbers 2 Mapping of L instructions into numbers SubTask 1 Mapping Variables and Labels The variables are arranged as follows YX Z1X222X3Z3 The labels are arranged as follows A1 B1 c D E1A232 CZDZE2A3 Let w be the position of a variable in the variable ordering Let L be the position of a label in the variable ordering SubTask 1 Mapping Variables and Labels The variables are arranged as follows YX Z1X222X3Z3 The labels are arranged as follows A1 B1 c D E1A232 CZDZE2A3 391 X12 X36 B12 A26 Cz8 SubTask 2 Mapping Instructions to Numbers There are four instruction types in L Each instruction can be labeled or unlabeled Four Instruction Types in L 1V lt Vb0 2Vlt V1b1 3Vlt V1b2 41FV 720 GOTOL39 Review Pairing Functions ltxygt 2x2y1 1 2x2y11120 ltxy gt1 2x2y1 SubTask 2 Mapping Instructions to Numbers I lt61 lt19 cgtgt 1 a is the labelnurnber 2 b is the instruction type number 3 c is the number of the variable used in the instruction SubTask 2 Mapping Instructions to Numbers I lt61 lt1 3 1 If I is unlabeled then a 0 2 If 1 is labeled with L then a L 3 If a variable V is used in I then c V l 4lfisV lt Vthenb0 5lf1isVlt Vlthenbl 6lf1is V lt Vl thenb 2 7 If 1 is F V 7i 0 GOTO Lthen b L 2 SubTask 2 Example What is the number ofX X1 SubTask 2 Example Since I X X1 I ltaltbcgtgt 1 I is unlabeled so a 0 2X 2 soc X 1 1 31 is addition so I 1 4 Thus 1 0 lt11gtgt 20211 1 1 20221211 11jl1 125111111110 Recommended Reading Section 41 CS 5000 Lecture 38 Vladimir Kulyukin Department of Computer Science Utah State University Outline Normal Form for Partially Computable Func ons Normal Form for Computable Functions Review Snapshots SNAPHx1 mxnO INIT x1Xn SNAP x1xnyi 1 SUCCSNAP x1xny fly Review Step Counter Predicate STP x1xnyt ltgt TEmSNAPquotx1xnyty The R Predicate Let y0 be the number of a program that computes a pc function f x1 x Consider the predicate R de ned as follows Rx1xn yo Z ltgt STP x1xny0rzamp 2 FSNAPHC1X y0I Z1 The R Predicate Rx1xnyozltgt STP x1xny0rzamp Z Z rSNAP x1xn yo rz1 We need to ShOW that Rx1xnyozistrueifflzfx1xn Proof Sketch Since f is pc let yo be the number of a program that computes f Suppose for some x1xnfx1xn Then fx1xn k e N Since f is pc we know that El 239 such that STP x1xn yoz39 1 Let Z ltkmgtm Z 239 Then 2 k and rz m Since rz m 2 Z39 STP x1xny0rz 1 Since 2 k fx1xn we have rSNAP x1xny0 rz1 k 2 Theorem 33 Ch 4 Normal Form Theorem Let f x1 x be a partially computable function Then there is a primitive recursive predicate Rx1 x y0 2 such that Let fx1 x mzin Rx1 x yo 2 Where y0 is the number of a program that computes f x1 x Theorem 34 Ch 4 A function is partially computable if and only if it can be obtained from the initial functions by a nite number of applications of composition recursion and minimalization Proof 34 1 Show that if f is pc then it is obtained from the initial functions by a finite number of applications of composition recursion and minimalization 2 Show that if f is obtained from the initial functions by a finite number of applications of composition recursion and minimalization f is pc Proof 34 Part 1 Let f be a pc function By the Normal Form Theorem Theorem 33 Ch 4 fx1xn mZinRx1 xny0z R is pr and therefore is obtained from the initial functions by a finite number of applications of compositio n and recursion R is composed with min and then with I Thus f is obtained from the initial functions by a finite number of applications of compositio n recursion and minimalization Proof 34 Part 2 Let f be obtained from the initial functions by a nite number of applications of composition recursion and minimalizetion Theoreml 1 Ch 3 takes care of composition Theorems 21 Ch 3 and 22 Ch 3take care of recursion Theorem31 Ch 3 takes care of a combination of composition and recursion Theorem 72 Ch 3 takes care of minimalizetion Proper Minimalization min Rx1 x yo 2 can be a total function When does this happen This happens when for each x1 x there is at least one 2 such that Rx1xny0z 1 If this is the case min Rx1 x yo zis proper minimalization Proper Minimalization min Rx1 xn 2 can be a total function for some program y When does this happen This happens When for each x1 xn there is at least one 2 such that Rx1 xn z 1 If this is the case min Rx1 xn z is proper minimalization Theorem 35 Ch 4 A function is computableif and only if it can be obtained by a nite number of applications of composition recursion and proper minimalization Proof 35 The statement follows directly from the definition of proper minimalization If the minimalization is proper the function is total If the function is computable the minimalization must be proper CS 5000 Lecture 29 Vladimir Kulyukin Department of Computer Science Utah State University Outline Fundamental Theorem of Arithmetic Unbounded Minimalization Fundamental Theorem of Arithmetic Review Euclid s 1St Theorem If a prime divides the product of two positive integers then the prime divides at least one of the two integers prab then pa or pb Fundamental Theorem of Arithmetic FTA Every positive integer greater than 1 is either a prime or can be written as a product of primes The factorization is unique except for the order Unique Factorization Theorem FTA Examples 623 823 10251 5121 12223322 120024352 FTA Motivation 1200 24 352 Any divisor of 1200 is of the form 2X 3y 52 Where x e 04y e 01z 6 02 For example 22 30 5 is a divisor of 1200 FTA Proof 1 We need to prove 2 statements 1 Every natural number greater than 1 has a prime factorization ie can be written as a product of primes 2 The prime factorization is unique FTA Proof Part 1 1 Suppose not every natural number greater than 1 has a prime factorization 2 By the well ordering principle there must be the smallest such number Call this number n 3 n is not a prime because if it were it would have itself as its factorization 4 So 11 is a composite 5 Since 11 is a composite n ab where a lt n and b lt n 6 Since a and b are positive integers less than n and n is the smallest number that does not have a prime factorization a and I both have prime factorizations FTA Proof Part 1 Conclusion 7 n has a prime factorizaion thatconsistsof the prime factoriza ion of a follwedby theprimefactorizaion of b FTA Proof Part 2 1 Recall Euclid39s lst Theorem if p is a prime and piab then pia 0r pib 2 Let n be a natural number greater than 1 that has two prime factorizations F1 and F2 3 n 2 F1 2 p1pn 2 F2 2 qlqm n 4 Take 91 plinThus pliqlqm 5 By Euclid s 1st Theorem pliq1 0r pliqzqm Since 91 is a prime it must be the case that 91 q1 or 91 qt 2 3139 S m 6 The same trick can be repeated for 92 93 etc Unbounded Minimalization Unbounded Minimalization minPyx1xnltgt y The least value of y for which Py x1 x is true if there is such a value If there is no value of y for which Py x1 x is true min Py x1 x y is undefined Example 1 x yminyzx Example 1 10 7min7z103 7 10min10z7T Theorem 72 Ch 3 If Py x1 x is a computable predicate and if gx1 x min Pyx1 x then y g is partially computable Theorem 72 Proof A IF PYX1Xn GOTO E Ylt Y1 GOTOA Theorem 72 Ch 3 Observations Theorem 72 in Ch 3 offers us an important insight into unbounded minimalization Even when a predicate is computable there is no guarantee that the unbounded minimalization of that predicate will be computable Theorem 72 Ch 3 Observation Let PZ107 10 z 7 P is computable However minPz1 07 is not Recommended Reading Section 37