A Problem Course in Mathematical Logic Version 1.6 Stefan Bilaniuk DEPARTMENT OF MATHEMATICS TRENT UNIVERSITY PETERBOROUGH, ONTARIO CANADA K9J 7B8 E-mail address: sbilaniuk@trentu. ca  1991 Mathematics Subject Classification. 03 Key words and phrases. logic, computability, incompleteness ABSTRACT. This is a text for a problem-oriented course on math- ematical logic and computability. Copyright @ 1994-2003 Stefan Bilaniuk. Permission is granted to copy, distribute and/or modify this doc- ument under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the sec- tion entitled "GNU Free Documentation License". This work was typeset with LATEX, using the AMSLATEX and AMSFonts packages of the American Mathematical Society.  Contents Preface v Introduction ix Part I. Propositional Logic 1 Chapter 1. Language 3 Chapter 2. Truth Assignments 7 Chapter 3. Deductions 11 Chapter 4. Soundness and Completeness 15 Hints for Chapters 1-4 17 Part II. First-Order Logic 21 Chapter 5. Languages 23 Chapter 6. Structures and Models 33 Chapter 7. Deductions 41 Chapter 8. Soundness and Completeness 47 Chapter 9. Applications of Compactness 53 Hints for Chapters 5-9 59 Part III. Computability 65 Chapter 10. Turing Machines 67 Chapter 11. Variations and Simulations 75 Chapter 12. Computable and Non-Computable Functions 81 Chapter 13. Recursive Functions 87 Chapter 14. Characterizing Computability 95 iii  iv CONTENTS Hints for Chapters 10-14 101 Part IV. Incompleteness 109 Chapter 15. Preliminaries 111 Chapter 16. Coding First-Order Logic 113 Chapter 17. Defining Recursive Functions In Arithmetic 117 Chapter 18. The Incompleteness Theorem 123 Hints for Chapters 15-18 127 Appendices 131 Appendix A. A Little Set Theory 133 Appendix B. The Greek Alphabet 135 Appendix C. Logic Limericks 137 Appendix D. GNU Free Documentation License 139 Appendix. Bibliography 147 Appendix. Index 149  Preface This book is a free text intended to be the basis for a problem- oriented course(s) in mathematical logic and computability for students with some degree of mathematical sophistication. Parts I and II cover the basics of propositional and first-order logic respectively, Part III covers the basics of computability using Turing machines and recursive functions, and Part IV covers Gbdel's Incompleteness Theorems. They can be used in various ways for courses of various lengths and mixes of material. The author typically uses Parts I and II for a one-term course on mathematical logic, Part III for a one-term course on computability, and/or much of Part III together with Part IV for a one-term course on computability and incompleteness. In keeping with the modified Moore-method, this book supplies definitions, problems, and statements of results, along with some ex- planations, examples, and hints. The intent is for the students, indi- vidually or in groups, to learn the material by solving the problems and proving the results for themselves. Besides constructive criticism, it will probably be necessary for the instructor to supply further hints or direct the students to other sources from time to time. Just how this text is used will, of course, depend on the instructor and students in question. However, it is probably not appropriate for a conventional lecture-based course nor for a really large class. The material presented in this text is somewhat stripped-down. Various concepts and topics that are often covered in introductory mathematical logic and computability courses are given very short shrift or omitted entirely.1 Instructors might consider having students do projects on additional material if they wish to to cover it. Prerequisites. The material in this text is largely self-contained, though some knowledge of (very basic) set theory and elementary num- ber theory is assumed at several points. A few problems and examples draw on concepts from other parts of mathematics; students who are 'Future versions of both volumes may include more - or less! - material. Feel free to send suggestions, corrections, criticisms, and the like I'll feel free to ignore them or use them. V  vi PREFACE not already familiar with these should consult texts in the appropri- ate subjects for the necessary definitions. What is really needed to get anywhere with all of the material developed here is competence in handling abstraction and proofs, including proofs by induction. The experience provided by a rigorous introductory course in abstract al- gebra, analysis, or discrete mathematics ought to be sufficient. Chapter Dependencies. The following diagram indicates how the parts and chapters depend on one another, with the exception of a few isolated problems or subsections. L LL Acknowledgements. Various people and institutions deserve some credit for this text. Foremost are all the people who developed the subject, even though almost no attempt has been made to give due credit to those who developed and refined the ideas, results, and proofs mentioned in this work. In mitigation, it would often be difficult to assign credit fairly because many people were involved, frequently having interacted in complicated ways. Those interested in who did what should start by consulting other texts or reference works covering similar material. In  PREFACE vii particular, a number of the key papers in the development of modern mathematical logic can be found in [9] and [6]. Others who should be acknowledged include my teachers and col- leagues; my students at Trent University who suffered, suffer, and will suffer through assorted versions of this text; Trent University and the taxpayers of Ontario, who paid my salary; Ohio University, where I spent my sabbatical in 1995-96; all the people and organizations who developed the software and hardware with which this book was pre- pared. Gregory H. Moore, whose mathematical logic course convinced me that I wanted to do the stuff, deserves particular mention. Any blame properly accrues to the author. Availability. The URL of the home page for A Problem Course In Mathematical Logic, with links to BJTEX, PostScript, and Portable Document Format (pdf) files of the latest available release is: http: //euclid.trentu. ca/math/sb/pcml/ Please note that to typeset the JTEX source files, you will need the AMS-JTEX and AMSFonts packages in addition to J4TEX. If you have any problems, feel free to contact the author for assis- tance, preferably by e-mail: Stefan Bilaniuk Department of Mathematics Trent University Peterborough, Ontario K9J 7B8 e-mail: sbilaniuk@trentu. ca Conditions. See the GNU Free Documentation License in Appen- dix D for what you can do with this text. The gist is that you are free to copy, distribute, and use it unchanged, but there are some restric- tions on what you can do if you wish to make changes. If you wish to use this text in a manner not covered by the GNU Free Documentation License, please contact the author. Author's Opinion. It's not great, but the price is right!   Introduction What sets mathematics aside from other disciplines is its reliance on proof as the principal technique for determining truth, where science, for example, relies on (carefully analyzed) experience. So what is a proof? Practically speaking, a proof is any reasoned argument accepted as such by other mathematicians.2 A more precise definition is needed, however, if one wishes to discover what mathematical reasoning can - or cannot accomplish in principle. This is one of the reasons for studying mathematical logic, which is also pursued for its own sake and in order to find new tools to use in the rest of mathematics and in related fields. In any case, mathematical logic is concerned with formalizing and analyzing the kinds of reasoning used in the rest of mathematics. The point of mathematical logic is not to try to do mathematics per se completely formally the practical problems involved in doing so are usually such as to make this an exercise in frustration but to study formal logical systems as mathematical objects in their own right in order to (informally!) prove things about them. For this reason, the formal systems developed in this part and the next are optimized to be easy to prove things about, rather than to be easy to use. Natural deductive systems such as those developed by philosophers to formalize logical reasoning are equally capable in principle and much easier to actually use, but harder to prove things about. Part of the problem with formalizing mathematical reasoning is the necessity of precisely specifying the language(s) in which it is to be done. The natural languages spoken by humans won't do: they are so complex and continually changing as to be impossible to pin down completely. By contrast, the languages which underly formal logical systems are, like programming languages, rigidly defined but much sim- pler and less flexible than natural languages. A formal logical system also requires the careful specification of the allowable rules of reasoning, 2If you are not a mathematician, gentle reader, you are hereby temporarily promoted. ix  x INTRODUCTION plus some notion of how to interpret statements in the underlying lan- guage and determine their truth. The real fun lies in the relationship between interpretation of statements, truth, and reasoning. The de facto standard for formalizing mathematical systems is first- order logic, and the main thrust of this text is studying it with a view to understanding some of its basic features and limitations. More specifically, Part I of this text is concerned with propositional logic, developed here as a warm-up for the development of first-order logic proper in Part II. Propositional logic attempts to make precise the relationships that certain connectives like not, and, or, and if ... then are used to ex- press in English. While it has uses, propositional logic is not powerful enough to formalize most mathematical discourse. For one thing, it cannot handle the concepts expressed by the quantifiers all and there is. First-order logic adds these notions to those propositional logic handles, and suffices, in principle, to formalize most mathematical rea- soning. The greater flexibility and power of first-order logic makes it a good deal more complicated to work with, both in syntax and seman- tics. However, a number of results about propositional logic carry over to first-order logic with little change. Given that first-order logic can be used to formalize most mathe- matical reasoning it provides a natural context in which to ask whether such reasoning can be automated. This question is the Entschei- dungsproblem3: ENTSCHEIDUNGSPROBLEM. Given a set E of hypotheses and some statement c, is there an effective method for determining whether or not the hypotheses in E suffice to prove p? Historically, this question arose out of David Hilbert's scheme to secure the foundations of mathematics by axiomatizing mathematics in first-order logic, showing that the axioms in question do not give rise to any contradictions, and that they suffice to prove or disprove every statement (which is where the Entscheidungsproblem comes in). If the answer to the Entscheidungsproblem were "yes" in general, the effective method(s) in question might put mathematicians out of busi- ness... Of course, the statement of the problem begs the question of what "effective method" is supposed to mean. In the course of trying to find a suitable formalization of the no- tion of "effective method", mathematicians developed several different 3Entscheidungsproblem - decision problem.  INTRODUCTION xi abstract models of computation in the 1930's, including recursive func- tions, A-calculus, Turing machines, and grammars4. Although these models are very different from each other in spirit and formal defini- tion, it turned out that they were all essentially equivalent in what they could do. This suggested the (empirical, not mathematical!) principle: CHURCH'S THESIS. A function is effectively computable in princi- ple in the real world if and only if it is computable by (any) one of the abstract models mentioned above. Part III explores two of the standard formalizations of the notion of "effective method", namely Turing machines and recursive functions, showing, among other things, that these two formalizations are actually equivalent. Part IV then uses the tools developed in Parts II ands III to answer the Entscheidungsproblem for first-order logic. The answer to the general problem is negative, by the way, though decision proce- dures do exist for propositional logic, and for some particular first-order languages and sets of hypotheses in these languages. Prerequisites. In principle, not much is needed by way of prior mathematical knowledge to define and prove the basic facts about propositional logic and computability. Some knowledge of the natu- ral numbers and a little set theory suffices; the former will be assumed and the latter is very briefly summarized in Appendix A. ([10] is a good introduction to basic set theory in a style not unlike this book's; [8] is a good one in a more conventional mode.) Competence in han- dling abstraction and proofs, especially proofs by induction, will be needed, however. In principle, the experience provided by a rigorous introductory course in algebra, analysis, or discrete mathematics ought to be sufficient. Other Sources and Further Reading. [2], [5], [7], [12], and [13] are texts which go over large parts of the material covered here (and often much more besides), while [1] and [4] are good references for more advanced material. A number of the key papers in the development of modern mathematical logic and related topics can be found in [9] and [6]. Entertaining accounts of some related topics may be found in [11], 4The development of the theory of computation thus actually began before the development of electronic digital computers. In fact, the computers and program- ming languages we use today owe much to the abstract models of computation which preceded them. For example, the standard von Neumann architecture for digital computers was inspired by Turing machines and the programming language LISP borrows much of its structure from A-calculus.  xii INTRODUCTION [14] and[15]. Those interested in natural deductive systems might try [3], which has a very clean presentation.  Part I Propositional Logic   CHAPTER 1 Language Propositional logic (sometimes called sentential or predicate logic) attempts to formalize the reasoning that can be done with connectives like not, and, or, and if ... then. We will define the formal language of propositional logic, Ep, by specifying its symbols and rules for as- sembling these symbols into the formulas of the language. DEFINITION 1.1. The symbols of lp are: (1) Parentheses: ( and ). (2) Connectives: and -. (3) Atomic formulas: A0, A1, A2, ..., An, ... We still need to specify the ways in which the symbols of Ep can be put together. DEFINITION 1.2. The formulas of Ep are those finite sequences or strings of the symbols given in Definition 1.1 which satisfy the following rules: (1) Every atomic formula is a formula. (2) If a is a formula, then (-a) is a formula. (3) If a and # are formulas, then (a /) is a formula. (4) No other sequence of symbols is a formula. We will often use lower-case Greek characters to represent formulas, as we did in the definition above, and upper-case Greek characters to represent sets of formulas.1 All formulas in Chapters 1-4 will be assumed to be formulas of Ep unless stated otherwise. What do these definitions mean? The parentheses are just punc- tuation: their only purpose is to group other symbols together. (One could get by without them; see Problem 1.6.) and - are supposed to represent the connectives not and if ... then respectively. The atomic formulas, Ao, A1, ..., are meant to represent statements that cannot be broken down any further using our connectives, such as "The moon is made of cheese." Thus, one might translate the the English sen- tence "If the moon is red, it is not made of cheese" into the formula 1The Greek alphabet is given in Appendix B. 3  4 1. LANGUAGE (Ao - (-A1)) of lP by using Ao to represent "The moon is red" and A1 to represent "The moon is made of cheese." Note that the truth of the formula depends on the interpretation of the atomic sentences which appear in it. Using the interpretations just given of A0 and A1, the formula (Ao - (-A1)) is true, but if we instead use A0 and A1 to interpret "My telephone is ringing" and "Someone is calling me", respectively, (Ao - (-A1)) is false. Definition 1.2 says that that every atomic formula is a formula and every other formula is built from shorter formulas using the connectives and parentheses in particular ways. For example, A1123, (A2 - (,A0)), and (((-A1) - (A1 - A7)) - A7) are all formulas, but X3, (A5), QA41, A5 -- A7, and (A2 - (-,Ao) are not. PROBLEM 1.1. Why are the following not formulas of Pe ? There might be more than one reason... (1) A_56 (2) (Y- A) (3) (A7 <-A4) (4) A7 - (-,AS)) (5) (AsA9 -+ A1043998 (6) (((,A1) - (AP - A7) --A7) PROBLEM 1.2. Show that every formula of lP has the same number of left parentheses as it has of right parentheses. PROBLEM 1.3. Suppose a is any formula of eP. Let f(a) be the length of a as a sequence of symbols and let p(a) be the number of parentheses (counting both left and right parentheses) in a. What are the minimum and maximum values of p(a)/t(a)? PROBLEM 1.4. Suppose a is any formula of eP. Let s(a) be the number of atomic formulas in a (counting repetitions) and let c(a) be the number of occurrences of - in a. Show that s(a) = c(a) + 1. PROBLEM 1.5. What are the possible lengths of formulas of Pe ? Prove it. PROBLEM 1.6. Find a way for doing without parentheses or other punctuation symbols in defining a formal language for propositional logic. PROPOSITION 1.7. Show that the set of formulas of lP is countable. Informal Conventions. At first glance, Eir may not seem capable of breaking down English sentences with connectives other than not and if ... then. However, the sense of many other connectives can be  1. LANGUAGE 5 captured by these two by using suitable circumlocutions. We will use the symbols A, V, and to represent and, or,2 and if and only if respectively. Since they are not among the symbols of lp, we will use them as abbreviations for certain constructions involving only and -. Namely, * (a A 3) is short for (-(a - (,#))), S(a V 3) is short for ((-a) - #), and * (a #,) is short for ((a - /3) A (/3 -- a)). Interpreting A0 and A1 as before, for example, one could translate the English sentence "The moon is red and made of cheese" as (A0 A A1). (Of course this is really (-(A0 - (-A1))), i.e. "It is not the case that if the moon is green, it is not made of cheese.") A, V, and - were not included among the official symbols of Ep partly because we can get by without them and partly because leaving them out makes it easier to prove things about Cp. PROBLEM 1.8. Take a couple of English sentences with several con- nectives and translate them into formulas of Cp. You may use A, V, and e if appropriate. PROBLEM 1.9. Write out ((a V,3) A (3 - a)) using only and - . For the sake of readability, we will occasionally use some informal conventions that let us get away with writing fewer parentheses: " We will usually drop the outermost parentheses in a formula, writing a /3 instead of (a /3) and -a instead of (-a). " We will let take precedence over - when parentheses are missing, so -a 3 is short for ((a) - 3), and fit the informal connectives into this scheme by letting the order of precedence be ,, A, V, -, and e. " Finally, we will group repetitions of -, V, A, or to the right when parentheses are missing, so a /3 - is short for Just like formulas using V, A, or ,, formulas in which parentheses have been omitted as above are not official formulas of Ep, they are conve- nient abbreviations for official formulas of Cp. Note that a precedent for the precedence convention can be found in the way that - commonly takes precedence over + in writing arithmetic formulas. PROBLEM 1.10. Write out ,(a ,5) A/3 - ,a - first with the missing parentheses included and then as an official formula of lip. 2We will use or inclusively, so that "A or B" is still true if both of A and B are true.  6 1. LANGUAGE The following notion will be needed later on. DEFINITION 1.3. Suppose c is a formula of EP. The set of subfor- mulas of c, S(p), is defined as follows. (1) If c is an atomic formula, then S(p) {y}. (2) If c is (-ia), then S(p) =S(a) U {(,a)}. (3) Ifycois (a -3), then S(p) = 1, a (possibly empty) set of k-place function symbols. (8) For each k > 1, a (possibly empty) set of k-place relation (or predicate) symbols. The symbols described in parts 1-5 are the logical symbols of C, shared by every first-order language, and the rest are the non-logical symbols of C, which usually depend on what the language's intended use. NOTE. It is possible to define first-order languages without =, so is considered a non-logical symbol by many authors. While such lan- guages have some uses, they are uncommon in ordinary mathematics. Observe that any first-order language C has countably many logical symbols. It may have uncountably many symbols if it has uncountably many non-logical symbols. Unless explicitly stated otherwise, we will 1It is possible to formalize almost all of mathematics in a single first-order language, like that of set theory or category theory. However, trying to actually do most mathematics in such a language is so hard as to be pointless. 2Specifically, to countable one-sorted first-order languages with equality.  5. LANGUAGES 25 assume that every first-order language we encounter has only count- ably many non-logical symbols. Most of the results we will prove actu- ally hold for countable and uncountable first-order languages alike, but some require heavier machinery to prove for uncountable languages. Just as in lp, the parentheses are just punctuation while the con- nectives, i and -, are intended to express not and if ... then. How- ever, the rest of the symbols are new and are intended to express ideas that cannot be handled by Cp. The quantifier symbol, V, is meant to represent for all, and is intended to be used with the variable symbols, e.g. Vv4. The constant symbols are meant to be names for particular elements of the structure under discussion. k-place function symbols are meant to name particular functions which map k-tuples of elements of the structure to elements of the structure. k-place relation symbols are intended to name particular k-place relations among elements of the structure.3 Finally, = is a special binary relation symbol intended to represent equality. EXAMPLE 5.1. Since the logical symbols are always the same, first- order languages are usually defined by specifying the non-logical sym- bols. A formal language for elementary number theory like that unof- ficially described above, call it liNT, can be defined as follows. " Constant symbols: 0 and 1 " Two 2-place function symbols: + and " Two binary relation symbols: < and Each of these symbols is intended to represent the same thing it does in informal mathematical usage: 0 and 1 are intended to be names for the numbers zero and one, + and - names for the operations of addition and multiplications, and < and names for the relations "less than" and "divides". (Note that we could, in principle, interpret things completely differently let 0 represent the number forty-one, + the operation of exponentiation, and so on or even use the language to talk about a different structure say the real numbers, R, with 0, 1, +, -, and < representing what they usually do and, just for fun, interpreted as "is not equal to". More on this in Chapter 6.) We will usually use the same symbols in our formal languages that we use informally for various common mathematical objects. This convention 3Intuitively, a relation or predicate expresses some (possibly arbitrary) relation- ship among one or more objects. For example, "n is prime" is a 1-place relation on the natural numbers, < is a 2-place or binary relation on the rationals, and d x (b x c-) =0 is a 3-place relation on TR3. Formally, a k-place relation on a set X is just a subset of Xk, i. e. the collection of sequences of length k of elements of X for which the relation is true.  26 5. LANGUAGES can occasionally cause confusion if it is not clear whether an expression involving these symbols is supposed to be an expression in a formal language or not. EXAMPLE 5.2. Here are some other first-order languages. Recall that we need only specify the non-logical symbols in each case and note that some parts of Definitions 5.2 and 5.3 may be irrelevant for a given language if it is missing the appropriate sorts of non-logical symbols. (1) The language of pure equality, C_: " No non-logical symbols at all. (2) A language for fields, CF: " Constant symbols: 0, 1 " 2-place function symbols: +, (3) A language for set theory, Es: " 2-place relation symbol: E (4) A language for linear orders, Lo: " 2-place relation symbol: < (5) Another language for elementary number theory, EN: " Constant symbol: 0 " 1-place function symbol: S " 2-place function symbols: +, -, E Here 0 is intended to represent zero, S the successor func- tion, i.e. S(n) = n + 1, and E the exponential function, i.e. E(n, m) = n". (6) A "worst-case" countable language, L1: " Constant symbols: c1, c2, c3, ... " For each k;> 1, k-place function symbols: fj , fj, fk, ... " For each k;> 1, k-place relation symbols: Pk, P2, P3, ... This language has no use except as an abstract example. It remains to specify how to form valid formulas from the symbols of a first-order language C. This will be more complicated than it was for Cp. In fact, we first need to define a type of expression in C which has no counterpart in propositional logic. DEFINITION 5.2. The terms of a first-order language C are those finite sequences of symbols of C which satisfy the following rules: (1) Every variable symbol vn is a term. (2) Every constant symbol c is a term. (3) If f is a k-place function symbol and ti, . . ., tk are terms, then ft1 ... tk is also a term. (4) Nothing else is a term.  5. LANGUAGES 27 That is, a term is an expression which represents some (possibly indeterminate) element of the structure under discussion. For example, in ENT or 'N, +vov1 (informally, v0 + v1 ) is a term, though precisely which natural number it represents depends on what values are assigned to the variables v0 and v1. PROBLEM 5.1. Which of the following are terms of one of the lan- guages defined in Examples 5.1 and 5.2? If so, which of these lan- guage(s) are they terms of; if not, why not? (1) -v2 (2) +0 - +v611 (3) |1 + v30 (4) (for all a E 9NI, if s(v3) = 0 - a, then s(v3) = 0 <>for all ae II,if4=0-a,then 4=0 <->for all a E9|M, if 4 =0, then 4 =0 ... which last is true whether or not 4 = 0 is true or false. PROBLEM 6.4. Let 91 be the structure for EN in Problem 6.2. Let p : V - N be defined by p(v2k) = k and p(v2k+1) = k. Verify that (1) 1= Vw(-Sw = 0) [p] and (2) TX Vz~y x + y = 0 [p]. PROPOSITION 6.5. Suppose 9)11 is a structure for , s is an as- signment for 9)1, z is a variable, and y is a formula of a first-order language £. Then 9)1 |= Bzo[s] if and only if 9) |=o[ s~zim i] for some m 9)11|.  6. STRUCTURES AND MODELS 37 Working with particular assignments is difficult but, while some- times unavoidable, not always necessary. DEFINITION 6.5. Suppose 9) is a structure for G, and c a formula of G. Then 9) |= if and only if 9A |= [s] for every assignment s V - 9)| for 9). 9 is a model of c or that c is true in 9) if T2|1= c. We will often write 9) X @ if it is not the case that 9)1|= @ Similarly, if F is a set of formulas, we will write 9)1= F if 9)1= for every formula y E F, and say that 9) is a model of F or that 9) satisfies F. A formula or set of formulas is satisfiable if there is some structure 9) which satisfies it. We will often write 9)1 F if it is not the case that 91 = F. NOTE. 9)1 X c does not mean that for every assignment s: V - |9I, it is not the case that 9)1 =p[s]. It only means that that there is some assignment r : V - 9I for which 9 | =y[r] is not true. PROBLEM 6.6. £2 - (Q, <) is a structure for Co. For each of the following formulas c of Co, determine whether or not £ | =y. (1) Vvo v2 vo 2, a sentence, o-, which asserts that there are at least n different elements in the universe: " ±X1 ... Edx ((,icc =X2)A (-,i =X3)... A (--cn-1 = c)) 53  54 9. APPLICATIONS OF COMPACTNESS We claim that every finite subset of E is satisfiable. The most direct way to verify this is to show how, given a finite subset A of E, to produce a model 9A1 of A. Let n be the largest integer such that oa E A U {c-2} (Why is there such an n?) and choose an integer k such that 2k > n. Define a structure (G, o) for CG as follows: G={(aP | 1 Y k)I a=Oor1} *(af |1Y 1 there is an integer Rn such that any graph with at least Rn vertices has a clique with n vertices or an independent set with n vertices. Rn is the nth Ramsey number. It is easy to see that R1 = 1 and R2 = 2, but R3 is already 6, and Rn grows very quickly as a function of n thereafter. Ramsey's Theorem is fairly hard to prove directly, but the corresponding result for infinite graphs is comparatively straight- forward. LEMMA 9.3. If (V, E) is a graph with infinitely many vertices, then it has an infinite clique or an infinite independent set. A relatively quick way to prove Ramsey's Theorem is to first prove its infinite counterpart, Lemma 9.3, and then get Ramsey's Theorem out of it by way of the Compactness Theorem. (If you're an ambitious minimalist, you can try to do this using the Compactness Theorem for propositional logic instead!) Elementary equivalence and non-standard models. One of the common uses for the Compactness Theorem is to construct "non- standard" models of the theories satisfied by various standard math- ematical structures. Such a model satisfies all the same first-order sentences as the standard model, but differs from it in some way not expressible in the first-order language in question. This brings home one of the intrinsic limitations of first-order logic: it can't always tell essentially different structures apart. Of course, we need to define just what constitutes essential difference. DEFINITION 9.2. Suppose E is a first-order language and 91 and 91i are two structures for £. Then 91 and 931 are: (1) isomorphic, written as 91 a 9), if there is a function F: |91 |)I such that  56 9. APPLICATIONS OF COMPACTNESS (a) F is 1 - 1 and onto, (b) F(c) = c" for every constant symbol c of L, (c) F(f"(ai, ... , ak) = f(F(ai),. . . , F(ay)) for every k-place function symbol f of £ and elements a1, . . . , ak E II, and (d) P (ai,..., ak) holds if and only if PI(F(ai),..., F(ak)) for every k-place relation symbol of £ and elements ai, ..., akof |91; and (2) elementarily equivalent, written as 91 -9Y, if Th(1) = Th(M), i.e. if 9 |=uo if and only if 91= o for every sentence o of G. That is, two structures for a given language are isomorphic if they are structurally identical and elementarily equivalent if no statement in the language can distinguish between them. Isomorphic structures are elementarily equivalent: PROPOSITION 9.4. Suppose £ is a first-order language and 91 and T2 are structures for £ such that 91 9)9. Then 91 9-l9. However, as the following application of the Compactness Theorem shows, elementarily equivalent structures need not be isomorphic: EXAMPLE 9.2. Note that (t= (N) is an infinite structure for E=. Expand G= to ER by adding a constant symbol cr for every real number r, and let E be the set of sentences of C. including " every sentence T of Th(E), i.e. such that ( t= r, and " ,cr = c. for every pair of real numbers r and s such that r / s. Every finite subset of E is satisfiable. (Why?) Thus, by the Compact- ness Theorem, there is a structure S,' for ER satisfying E, and hence Th(E). The structure U obtained by dropping the interpretations of all the constant symbols cr from S,' is then a structure for C. which satisfies Th(E). Note that |UI = |J'l is at least large as the set of all real numbers R, since ' requires a distinct element of the universe to interpret each constant symbol cr of ER. Since Th(E) is a maximally consistent set of sentences of G= by Problem 8.6, it follows from the above that ( t .. On the other hand, ( cannot be isomorphic to U because there cannot be an onto map between a countable set, such as N =_|E|, and a set which is at least as large as R, such as|I In general, the method used above can be used to show that if a set of sentences in a first-order language has an infinite model, it has many different ones. In E= that is essentially all that can happen:  9. APPLICATIONS OF COMPACTNESS 57 PROPOSITION 9.5. Two structures for G- are elementarily equiva- lent if and only if they are isomorphic or infinite. PROBLEM 9.6. Let 91= (N, 0, 1, S, +, -, E) be the standard structure for 'N- Use the Compactness Theorem to show there is a structure 9A for 1N such that 91 =9 but not 91 99. Note that because 91 and 9) both satisfy Th(91), which is maximally consistent by Problem 8.6, there is absolutely no way of telling them apart in IN- PROPOSITION 9.7. Every model of Th(91) which is not isomorphic to 91 has (1) an isomorphic copy of 91 embedded in it, (2) an infinite number, i.e. one larger than all of those in the copy of 91, and (3) an infinite decreasing sequence. The apparent limitation of first-order logic that non-isomorphic structures may be elementarily equivalent can actually be useful. A non-standard model may have features that make it easier to work with than the standard model one is really interested in. Since both structures satisfy exactly the same sentences, if one uses these features to prove that some statement expressible in the given first-order lan- guage is true about the non-standard structure, one gets for free that it must be true of the standard structure as well. A prime example of this idea is the use of non-standard models of the real numbers con- taining infinitesimals (numbers which are infinitely small but different from zero) in some areas of analysis. THEOREM 9.8. Let N9= (R, 0, 1, +, -) be the field of real numbers, considered as a structure for 'F- Then there is a model of Th(at) which contains a copy of R and in which there is an infinitesimal. The non-standard models of the real numbers actually used in anal- ysis are usually obtained in more sophisticated ways in order to have more information about their internal structure. It is interesting to note that infinitesimals were the intuition behind calculus for Leibniz when it was first invented, but no one was able to put their use on a rigourous footing until Abraham Robinson did so in 1950.   Hints for Chapters 5-9 Hints for Chapter 5. 5.1. Try to disassemble each string using Definition 5.2. Note that some might be valid terms of more than one of the given languages. 5.2. This is similar to Problem 1.5. 5.3. This is similar to Proposition 1.7. 5.4. Try to disassemble each string using Definitions 5.2 and 5.3. Note that some might be valid formulas of more than one of the given languages. 5.5. This is just like Problem 1.2. 5.6. This is similar to Problem 1.5. You may wish to use your solution to Problem 5.2. 5.7. This is similar to Proposition 1.7. 5.8. You might want to rephrase some of the given statements to make them easier to formalize. (1) Look up associativity if you need to. (2) "There is an object such that every object is not in it." (3) This should be easy. (4) Ditto. (5) "Any two things must be the same thing." 5.9. If necessary, don't hesitate to look up the definitions of the given structures. (1) Read the discussion at the beginning of the chapter. (2) You really need only one non-logical symbol. (3) There are two sorts of objects in a vector space, the vectors themselves and the scalars of the field, which you need to be able to tell apart. 5.10. Use Definition 5.3 in the same way that Definition 1.2 was used in Definition 1.3. 59  60 HINTS FOR CHAPTERS 5-9 5.11. The scope of a quantifier ought to be a certain subformula of the formula in which the quantifier occurs. 5.12. Check to see whether they satisfy Definition 5.4. 5.13. Check to see which pairs satisfy Definition 5.5. 5.14. Proceed by induction on the length of cp using Definition 5.3. 5.15. This is similar to Theorem 1.12. 5.16. This is similar to Theorem 1.12 and uses Theorem 5.15. Hints for Chapter 6. 6.1. In each case, apply Definition 6.1. (1) This should be easy. (2) Ditto. (3) Invent objects which are completely different except that they happen to have the right number of the right kind of compo- nents. 6.2. Figure out the relevant values of s(vn) and apply Definition 6.3. 6.3. Suppose s and r both extend the assignment s. Show that s(t) = r(t) by induction on the length of the term t. 6.4. Unwind the formulas using Definition 6.4 to get informal state- ments whose truth you can determine. 6.5. Unwind the abbreviation I and use Definition 6.4. 6.6. Unwind each of the formulas using Definitions 6.4 and 6.5 to get informal statements whose truth you can determine. 6.7. This is much like Proposition 6.3. 6.8. Proceed by induction on the length of the formula using Defi- nition 6.4 and Lemma 6.7. 6.9. How many free variables does a sentence have? 6.10. Use Definition 6.4. 6.12. Unwind the sentences in question using Definition 6.4. 6.11. Use Definitions 6.4 and 6.5; the proof is similar in form to the proof of Proposition 2.9. 6.14. Use Definitions 6.4 and 6.5; the proof is similar in form to the proof for Problem 2.10.  HINTS FOR CHAPTERS 5-9 61 6.15. Use Definitions 6.4 and 6.5 in each case, plus the meanings of our abbreviations. 6.17. In one direction, you need to add appropriate objects to a structure; in the other, delete them. In both cases, you still have to verify that F is still satisfied. 6.18. Here are some appropriate languages. (1) A_ (2) Modify your language for graph theory from Problem 5.9 by adding a 1-place relation symbol. (3) Use your language for group theory from Problem 5.9. (4) £F Hints for Chapter 7. 7.1. (1) Use Definition 7.1. (2) Ditto. (3) Ditto. (4) Proceed by induction on the length of the formula cp. 7.2. Use the definitions and facts about |= from Chapter 6. 7.3. Check each case against the schema in Definition 7.4. Don't forget that any generalization of a logical axiom is also a logical axiom. 7.4. You need to show that any instance of the schemas Al-A8 is a tautology and then apply Lemma 7.2. That each instance of schemas Al-A3 is a tautology follows from Proposition 6.15. For A4-A8 you'll have to use the definitions and facts about |= from Chapter 6. 7.5. You may wish to appeal to the deductions that you made or were given in Chapter 3. (1) Try using A4 and A6. (2) You don't need A4-A8 here. (3) Try using A4 and A8. (4) A8 is the key; you may need it more than once. (5) This is just A6 in disguise. 7.6. This is just like its counterpart for propositional logic. 7.7. Ditto. 7.8. Ditto. 7.9. Ditto. 7.10. Ditto.  62 HINTS FOR CHAPTERS 5-9 7.11. Proceed by induction on the length of the shortest proof of c from F. 7.12. Ditto. 7.13. As usual, don't take the following suggestions as gospel. (1) Try using A8. (2) Start with Example 7.1. (3) Start with part of Problem 7.5. Hints for Chapter 8. 8.1. This is similar to the proof of the Soundness Theorem for propositional logic, using Proposition 6.10 in place of Proposition 3.2. 8.2. This is similar to its counterpart for prpositional logic, Propo- sition 4.2. Use Proposition 6.10 instead of Proposition 3.2. 8.3. This is just like its counterpart for propositional logic. 8.4. Ditto. 8.5. Ditto. 8.6. This is a counterpart to Problem 4.6; use Proposition 8.2 in- stead of Proposition 4.2 and Proposition 6.15 instead of Proposition 2.4. 8.7. This is just like its counterpart for propositional logic. 8.8. Ditto 8.9. Ditto. 8.10. This is much like its counterpart for propositional logic, The- orem 4.10. 8.11. Use Proposition 7.8. 8.12. Use the Generalization Theorem for the hard direction. 8.13. This is essentially a souped-up version of Theorem 8.10. To ensure that C is a set of witnesses of the maximally consistent set of sentences, enumerate all the formulas y of 12' with one free variable and take care of one at each step in the inductive construction.  HINTS FOR CHAPTERS 5-9 63 8.14. To construct the required structure, 9)T, proceed as follows. Define an equivalence relation on C by setting c d if and only if c = d E E, and let [c] = { a E C a c} be the equivalence class of c E C. The universe of 92 will be M = { [c] | c E C }. For each k-place function symbol f define f" by setting f"([a1], ..., [ak]) = [b] if and only if fa1... ak = b is in E. Define the interpretations of constant symbols and relation symbols in a similar way. You need to show that all these things are well-defined, and then show that 9)|=1E. 8.15. Expand F to a maximally consistent set of sentences with a set of witnesses in a suitable extension of £, apply Theorem 8.14, and then cut down the resulting structure to one for £. 8.16. One direction is just Proposition 8.2. For the other, use Corollary 8.15. 8.17. This follows from Theorem 8.16 in the same way that the Completeness Theorem for propositional logic followed from Theorem 4.11. 8.18. This follows from Theorem 8.16 in the same way that the Compactness Theorem for propositional logic followed from Theorem 4.11. Hints for Chapter 9. 9.1. In each case, apply the trick used in Example 9.1. For defi- nitions and the concrete examples, consult texts on combinatorics and abstract algebra. 9.2. Suppose Ramsey's Theorem fails for some n. Use the Com- pactness Theorem to get a contradiction to Lemma 9.3 by showing there must be an infnite graph with no clique or independent set of size n. 9.3. Inductively define a sequence ao, ai, ... , of vertices so that for every n, either it is the case that for all k > n there is an edge joining an to ak or it is the case that for all k > n there is no edge joining an to ak. There will then be a subsequence of the sequence which is an infinite clique or a subsequence which is an infinite independent set. 9.4. The key is to figure out how, given an assignment for one structure, one should define the corresponding assignment in the other structure. After that, proceed by induction using the definition of satisfaction. 9.5. When are two finite structures for C_ elementarily equivalent?  64 HINTS FOR CHAPTERS 5-9 9.6. In a suitable expanded language, consider Th(91) together with the sentences Ex 0 + x = c, E SO + x = c, Ex SSO + x = c, ... 9.7. Suppose 9)1= Th(91) but is not isomorphic to 1. (1) Consider the subset of 192I given by 09, S"(0), S"(S"(0)), (2) If it didn't have one, it would be a copy of 1. (3) Start with a infinite number and work down. 9.8. Expand EF by throwing in a constant symbol for every real number, plus an extra one, and take it from there.  Part III Computability   CHAPTER 10 Turing Machines Of the various ways to formalize the notion an "effective method", the most commonly used are the simple abstract computers called Tur- ing machines, which were introduced more or less simultaneously by Alan Turing and Emil Post in 1936.1 Like most real-life digital com- puters, Turing machines have two main parts, a processing unit and a memory (which doubles as the input/output device), which we will consider separately before seeing how they interact. The memory can be thought of as an infinite tape which is divided up into cells like the frames of a movie. The Turing machine proper is the processing unit. It has a scanner or head which can read from or write to a single cell of the tape, and which can be moved to the left or right one cell at a time. Tapes. To keep things simple, in this chapter we will only allow Turing machines to read and write the symbols 0 and 1. (One symbol per cell!) Moreover, we will allow the tape to be infinite in only one direction. That these restrictions do not affect what a Turing machine can, in principle, compute follows from the results in the next chapter. DEFINITION 10.1. A tape is an infinite sequence a = ao a1 a2 a3... such that for each integer i the cell a2 E {0, 1}. The ith cell is said to be blank if a2 is 0, and marked if a2 is 1. A blank tape is one in which every cell is 0. EXAMPLE 10.1. A blank tape looks like: 000000000000000000000000... The 0th cell is the leftmost one, cell 1 is the one immediately to the right, cell 2 is the one immediately to the right of cell 1, and so on. The following is a slightly more exciting tape: 0101101110001000000000000000... 1Both papers are reprinted in [6]. Post's brief paper gives a particularly lucid informal description. 67  68 10. TURING MACHINES In this case, cell 1 is marked (i.e. contains a 1), as do cells 3, 4, 5, 7, 8, and 12; all the rest are blank (i.e. contain a 0). PROBLEM 10.1. Write down tapes satisfying the following. (1) Entirely blank except for cells 3, 12, and 20. (2) Entirely marked except for cells 0, 2, and 3. (3) Entirely blank except that 1025 is written out in binary just to the right of cell 2. To keep track of which cell the Turing machine's scanner is at, plus which instruction the Turing machine is to execute next, we will usually attach additional information to our description of the tape. DEFINITION 10.2. A tape position is a triple (s, i, a), where s and i are natural numbers with s > 0, and a is a tape. Given a tape position (s, i, a), we will refer to cell i as the scanned cell and to s as the state. Note that if (s, i, a) is a tape position, then the corresponding Tur- ing machine's scanner is presently reading a2 (which is one of 0 or 1). Conventions for tapes. Unless stated otherwise, we will assume that all but finitely many cells of any given tape are blank, and that any cells not explicitly described or displayed are blank. We will usually depict as little of a tape as possible and omit the - - - s we used above. Thus 0101101110001 represents the tape given in the Example 10.1. In many cases we will also use z" to abbreviate n consecutive copies of z, so the same tape could be represented by 01012013031. Similarly, if o is a finite sequence of elements of {0, 1}, we may write o- for the sequence consisting of n copies of o stuck together end-to-end. For example, (010)3 is short for 010010010. In displaying tape positions we will usually underline the scanned cell and write s to the left of the tape. For example, we would display the tape position using the tape from Example 10.1 with cell 3 being scanned and state 2 as follows: 2: 0101101110001 Note that in this example, the scanner is reading a 1. P ROBLEM 10.2. Using the tapes you gave in the corresponding part of Problem 10.1; write down tape positions satisfying the following con- ditions.  10. TURING MACHINES 69 (1) Cell 7 being scanned and state 4. (2) Cell 4 being scanned and state 3. (3) Cell 3 being scanned and state 413. Turing machines. The "processing unit" of a Turing machine is just a finite list of specifications describing what the machine will do in various situations. (Remember, this is an abstract computer...) The formal definition may not seem to amount to this at first glance. DEFINITION 10.3. A Turing machine is a function M such that for some natural number n, dom(M) C {1,...,n} x {0,1} = {(s,b) 1 1 is least such that M satisfies the definition above, we shall say that M is an n-state Turing machine and that {1,. . . , n} is the set of states of M. Intuitively, we have a processing unit which has a finite list of basic instructions, the states, which it can execute. Given a combination of current state and the symbol marked in the currently scanned cell of the tape, the list specifies " a symbol to be written in the currently scanned cell, overwrit- ing the symbol being read, then " a move of the scanner one cell to the left or right, and then " the next instruction to be executed. That is, M(s, c) = (b, d, t) means that if our machine is in state s (i.e. executing instruction number s) and the scanner is presently reading a c in cell i, then the machine M should * set ai b (i.e. write b instead of c in the scanned cell), then * move the scanner to ag±d (i.e. move one cell left if d =--1 and one cell right if d =1), and then * enter state t (i.e. go to instruction t).  70 10. TURING MACHINES If our processor isn't equipped to handle input c for instruction s (i.e. M(s, c) is undefined), then the computation in progress will simply stop dead or halt. EXAMPLE 10.2. We will usually present Turing machines in the form of a table, with a row for each state and a column for each possible entry in the scanned cell. Instead of -1 and 1, we will usually use L and R when writing such tables in order to make them more readable. Thus the table M 0 1 1 1R2 OR1 2 0L2 defines a Turing machine M with two states such that M(1, 0) (1,1, 2), M(1,1) = (0,1,1), and M(2,0) =_(0, -1, 2), but M(2,1) is undefined. In this case M has domain { (1, 0), (1, 1), (2, 0) } and range { (1, 1, 2), (0, 1, 1), (0, -1, 2) }. If the machine M were faced with the tape position 1: 01001111, it would, since it was in state 1 while scanning a cell containing 0, " write a 1 in the scanned cell, " move the scanner one cell to the right, and " go to state 2. This would give the new tape position 2: 01011111. Since M doesn't know what to do on input 1 in state 2, it would then halt, ending the computation. PROBLEM 10.3. In each case, give the table of a Turing machine M meeting the given requirement. (1) M has three states. (2) M changes 0 to 1 and vice versa in any cell it scans. (3) M is as simple as possible. How many possibilities are there here? Computations. Informally, a computation is a sequence of actions of a machine M on a tape according to the rules above, starting with instruction 1 and the scanner at cell 0 on the given tape. A computation ends (or halts) when and if the machine encounters a tape position which it does not know what to do in If it never halts, and doesn't crash by running the scanner off the left end of the tape2 either, the 2Be warned that most authors prefer to treat running the scanner off the left end of the tape as being just another way of halting. Halting with the scanner  10. TURING MACHINES 71 computation will never end. The formal definition makes all this seem much more formidable. DEFINITION 10.4. Suppose M is a Turing machine. Then: " If p = (s, i, a) is a tape position and M(s, a) =(b, d, t) is defined, then M(p) (t, i+d, a') is the successor tape position, where a' = b and a = a3 whenever j/i. " A partial computation with respect to M is a sequence P1P2 ... of tape positions such that p +1i= M(pf) for each £ < k. " A partial computation p1P2 ... Pk with respect to M is a com- putation (with respect to M) with input tape a if pi = (1, 0, a) and M(pk) is undefined (and not because the scanner would run off the end of the tape). The output tape of the computa- tion is the tape of the final tape position Pk. Note that a partial computation is a computation only if the Turing machine halts but doesn't crash in the final tape position. The require- ment that it halt means that any computation can have only finitely many steps. Unless stated otherwise, we will assume that every partial computation on a given input begins in state 1. We will often omit the "partial" when speaking of computations that might not strictly satisfy the definition of computation. EXAMPLE 10.3. Let's see the machine M of Example 10.2 perform a computation. Our input tape will be a = 1100, that is, the tape which is entirely blank except that ao = ai1= 1. The initial tape position of the computation of M with input tape a is: 1: 1100 The subsequent steps in the computation are: 1: 0100 1: 0000 2: 0010 2: 001 We leave it to the reader to check that this is indeed a partial com- putation with respect to M. Since M(2, 1) is undefined the process terminates at this point and this partial computation is therefore a computation. on the tape is more convenient, however, when putting together different Turing machines to make more complex ones.  72 10. TURING MACHINES PROBLEM 10.4. Give the (partial) computation of the Turing ma- chine M of Example 10.2 starting in state 1 with the input tape: (1) 00 (2) 110 (3) The tape with all cells marked and cell 5 being scanned. PROBLEM 10.5. For which possible input tapes does the partial com- putation of the Turing machine M of Example 10.2 eventually termi- nate? Explain why. PROBLEM 10.6. Find a Turing machine that (eventually!) fills a blank input tape with the pattern 010110001011000101100... . PROBLEM 10.7. Find a Turing machine that never halts (or crashes), no matter what is on the tape. Building Turing Machines. It will be useful later on to have a library of Turing machines that manipulate blocks of is in various ways, and very useful to be able to combine machines peforming simpler tasks to perform more complex ones. EXAMPLE 10.4. The Turing machine S given below is intended to halt with output 01k0 on input 01k, if k > 0; that is, it just moves past a single block of 1s without disturbing it. S 0 1 1 0R2 2 1R2 Trace this machine's computation on, say, input 013 to see how it works. The following machine, which is itself a variation on S, does the reverse of what S does: on input 01k0 it halts with output 01k*. T 0 1 1 0L2 2 1L2 We can combine S and T into a machine U which does nothing to a block of is: given input 01k it halts with output 01k. (Of course, a better way to do nothing is to really do nothing!) T 0 1 1 0R2 2 0L3 1R2 3 1L3 Note how the states of T had to be renumbered to make the combina- tion work.  10. TURING MACHINES 73 EXAMPLE 10.5. The Turing machine P given below is intended to move a block of is: on input 00n1k, where n > 0 and k > 0, it halts with output 01k. P 0 1 1 0R2 2 1R3 1L8 3 0R3 OR4 4 0R7 1L5 5 0L5 IR6 6 1R3 7 0L7 1L8 8 1L8 Trace P's computation on, say, input 00313 to see how it works. Trace it on inputs 012 and 0021 as well to see how it handles certain special cases. NOTE. In both Examples 10.4 and 10.5 we do not really care what the given machines do on other inputs, so long as they perform as intended on the particular inputs we are concerned with. PROBLEM 10.8. We can combine the machine P of Example 10.5 with the machines S and T of Example 10.4 to get the following ma- chine. R 0 1 1 0R2 2 0R3 1R2 3 1R4 1L9 4 OR4 0R5 5 0R8 1L6 6 OL6 1R7 7 1R4 8 0L8 1L9 9 OL10 1L9 10 1L10 What task involving blocks of Is is this machine intended to perform? PROBLEM 10.9. In each case, devise a Turing machine that: (1) Halts with output 014 on input 0. (2) Halts with output 01"0 on input 00"1. (3) Halts with output 012nh on input 01". (4) Halts with output 0(10<" on input 01". (5) Halts with output Q1"* on input 01"01"m whenever n, m > 0.  74 10. TURING MACHINES (6) Halts with output 01m01"01k on input 01"01k01m, if n, m, k > 0. (7) Halts with output 01m01"01k01m01"01k on input 01m01"01k, if n,m,k >0. (8) On input o1mo, where m, n > 0, halts with output 01 if m n and output 011 if m = n. It doesn't matter what the machine you define in each case may do on other inputs, so long as it does the right thing on the given one(s).  CHAPTER 11 Variations and Simulations The definition of a Turing machine given in Chapter 10 is arbitrary in a number of ways, among them the use of the symbols 0 and 1, a single read-write scanner, and a single one-way infinite tape. One could further restrict the definition we gave by allowing " the machine to move the scanner only to one of left or right in each state, or expand it by allowing the use of " any finite alphabet of at least two symbols, " separate read and write heads, " multiple heads, " two-way infinite tapes, " multiple tapes, " two- and higher-dimensional tapes, or various combinations of these, among many other possibilities. We will construct a number of Turing machines that simulate others with additional features; this will show that various of the modifications mentioned above really change what the machines can compute. (In fact, none of them turn out to do so.) EXAMPLE 11.1. Consider the following Turing machine: M 0 1 1 1R2 0L1 2 0L2 1L1 Note that in state 1, this machine may move the scanner to ei- ther the left or the right, depending on the contents of the cell being scanned. We will construct a Turing machine using the same alpha- bet that emulates the action of M on any input, but which moves the scanner to only one of left or right in each state. There is no problem with state 2 of M, by the way, because in state 2 M always moves the scanner to the left. The basic idea is to add some states to M which replace part of the description of state 1. 75  76 11. VARIATIONS AND SIMULATIONS M' 0 1 1 1R2 0R3 2 0L2 1L1 3 0L4 1L4 4 OL1 This machine is just like M except that in state 1 with input 1, instead of moving the scanner to the left and going to state 1, the machine moves the scanner to the right and goes to the new state 3. States 3 and 4 do nothing between them except move the scanner two cells to the left without changing the tape, thus putting it where M would have put it, and then entering state 1, as M would have. PROBLEM 11.1. Compare the computations of the machines M and M' of Example 11.1 on the input tapes (1) 0 (2) 011 and explain why is it not necessary to define M' for state 4 on input 1. PROBLEM 11.2. Explain in detail how, given an arbitrary Turing machine M, one can construct a machine M' that simulates what M does on any input, but which moves the scanner only to one of left or right in each state. It should be obvious that the converse, simulating a Turing machine that moves the scanner only to one of left or right in each state by an ordinary Turing machine, is easy to the point of being trivial. It is often very convenient to add additional symbols to the alphabet that Turing machines are permitted to use. For example, one might want to have special symbols to use as place markers in the course of a computation. (For a more spectacular application, see Example 11.3 below.) It is conventional to include 0, the "blank" symbol, in an alphabet used by a Turing machine, but otherwise any finite set of symbols goes. PROBLEM 11.3. How do you need to change Definitions 10.1 and 10.3 to define Turing machines using a finite alphabet E? While allowing arbitary alphabets is often convenient when design- ing a machine to perform some task, it doesn't actually change what can, in principle, be computed. EXAMPLE 11.2. Consider the machine W below which uses the alphabet {0, x, y, z}. W 0 x yz 1 0R1 cvR1 0L2 zR1  11. VARIATIONS AND SIMULATIONS 77 For example, on input Ozzyxy, W will eventually halt with output Oxz0xy. Note that state 2 of W is used only to halt, so we don't bother to make a row for it on the table. To simulate W with a machine Z using the alphabet {0, 1}, we first have to decide how to represent W's tape. We will use the following scheme, arbitrarily chosen among a number of alternatives. Every cell of W's tape will be represented by two consecutive cells of Z's tape, with a 0 on W's tape being stored as 00 on Z's, an x as 01, a y as 10, and a z as 11. Thus, if W had input tape Ozzyxy, the corresponding input tape for Z would be 000111100110. Designing the machine Z that simulates the action of W on the representation of W's tape is a little tricky. In the example below, each state of W corresponds to a "subroutine" of states of Z which between them read the information in each representation of a cell of W's tape and take appropriate action. Z 0 1 1 0R2 1R3 2 0L4 1L6 3 0L8 1L13 4 0R5 5 OR1 6 0R7 7 1R1 8 0R9 9 OL1O 10 OL11 11 0L12 1L12 12 0L15 1L15 13 1R14 14 1R1 States 1-3 of Z read the input for state 1 of W and then pass on control to subroutines handling each entry for state 1 in W's table. Thus states 4-5 of Z take action for state 1 of W on input 0, states 6-7 of Z take action for state 1 of W on input x, states 8-12 of Z take action for state 1 of W on input y, and states 13-14 take action for state 1 of W on input z. State 15 of Z does what state 2 of W does: nothing but halt. PROBLEM 11.4. Trace the (partial) computations of W, aid their counterparts for Z, for the input 0xvzyzvy for W . Why is the subroutine for state 1 of W on input y so much longer than the others? How much can you simplify it?  78 11. VARIATIONS AND SIMULATIONS PROBLEM 11.5. Given a Turing machine M with an arbitrary al- phabet E, explain in detail how to construct a machine N with alphabet {0, 1} that simulates M. Doing the converse of this problem, simulating a Turing machine with alphabet {0, 1} by one using an arbitrary alphabet, is pretty easy. To define Turing machines with two-way infinite tapes we need only change Definition 10.1: instead of having tapes a = aoaia2.... indexed by N, we let them be b = ... b-2b_1bobib2 ... indexed by Z. In defining computations for machines with two-way infinite tapes, we adopt the same conventions that we did for machines with one-way infinite tapes, such as having the scanner start off scanning cell 0 on the input tape. The only real difference is that a machine with a two-way infinite tape cannot crash by running off the left end of the tape; it can only stop by halting. EXAMPLE 11.3. Consider the following two-way infinite tape Turing machine with alphabet {0, 1}: T 0 1 1 1L1 0R2 2 0R2 1L1 To emulate T with a Turing machine 0 that has a one-way infinite tape, we need to decide how to represent a two-way infinite tape on a one-way infinite tape. This is easier to do if we allow ourselves to use an alphabet for 0 other than {0, 1}, chosen with malice aforethought: { 0 1 0 0 1 1 if S, s, 0, 1, , We can now represent the tape a = ... a-2a_1aoa1a2... for T by the tape a' = Sa 1a . .. for O. In effect, this trick allows us to split O's tape into two tracks, each of which accomodates half of the tape of T. To define 0, we split each state of T into a pair of states for 0, one for the lower track and one for the upper track. One must take care to keep various details straight: when 0 changes a "cell" on one track, it should not change the corresponding "cell" on the other track; directions are reversed on the lower track; one has to "turn a corner" moving past cell 0; and so on. 00 0 _0 0 1 1 1 |1 |3 L1 |L1 OR R2 "R2 1L1S 0 1R 2 R2 0R2 0R2 0R2 TR3 TL1 L1 3 OR3 |R3 OR3 OLA OR2 |R3 |LA 4 GLA OR2 OLA OR3 AR3 |LA |R3  11. VARIATIONS AND SIMULATIONS 79 States 1 and 3 are the upper- and lower-track versions, respectively, of T's state 1; states 2 and 4 are the upper- and lower-track versions, respectively, of T's state 2. We leave it to the reader to check that 0 actually does simulate T... PROBLEM 11.6. Trace the (partial) computations of T, and their counterparts for O, for each of the following input tapes for T: (1) 0 (i.e. a blank tape) (2) 10 (3) ... 1111111... (i.e. every cell marked with 1) PROBLEM 11.7. Explain in detail how, given a Turing machine N with alphabet E and a two-way infinite tape, one can construct a Turing machine P with an one-way infinite tape that simulates N. PROBLEM 11.8. Explain in detail how, given a Turing machine P with alphabet E and an one-way infinite tape, one can construct a Tur- ing machine N with a two-way infinite tape that simulates P. Combining the techniques we've used so far, we could simulate any Turing machine with a two-way infinite tape and arbitrary alphabet by a Turing machine with a one-way infinite tape and alphabet {0, 1}. PROBLEM 11.9. Give a precise definition for Turing machines with two tapes. Explain how, given any such machine, one could construct a single-tape machine to simulate it. PROBLEM 11.10. Give a precise definition for Turing machines with two-dimensional tapes. Explain how, given any such machine, one could construct a single-tape machine to simulate it. These results, and others like them, imply that none of the variant types of Turing machines mentioned at the start of this chapter differ essentially in what they can, in principle, compute. In Chapter 14 we will construct a Turing machine that can simulate any (standard) Turing machine.   CHAPTER 12 Computable and Non-Computable Functions A lot of computational problems in the real world have to do with doing arithmetic, and any notion of computation that can't deal with arithmetic is unlikely to be of great use. Notation and conventions. To keep things as simple as pos- sible, we will stick to computations involving the natural numbers, i. e. the non-negative integers, the set of which is usually denoted by N = {0,1, 2,... }.. The set of all k-tuples (ni,... , n) of natural num- bers is denoted by Nk. For all practical purposes, we may take N1 to be N by identifying the 1-tuple (n) with the natural number n. For k;> 1, f is a k-place function (from the natural numbers to the natural numbers), often written as f : Nk - N, if it associates a value, f (ni, ... , nk), to each k-tuple (ni, n2,.... , nk) E Nk. Strictly speaking, though we will frequently forget to be explicit about it, we will often be working with k-place partial functions which might not be defined for all the k-tuples in Nk. If f is a k-place partial function, the domain of f is the set dom(f)={((l,...,mnk) E N k f(ni,..., nk) is defined}. Similarly, the range of f is the set ran(f) = { f(ni, .. . , n) E IN |(ni,,. . . , n) E dom(f)} . In subsequent chapters we will also work with relations on the nat- ural numbers. Recall that a k-place relation on N is formally a subset P of Nk; P(ni,... ,ni) is true if (ni,...,ni) E P and false otherwise. In particular, a 1-place relation is really just a subset of N. Relations and functions are closely related. All one needs to know about a k-place function f can be obtained from the (k + 1)-place relation Pf given by Pf(ni, ... , ink, nk+1) < f (ni, ... , nk) = nk+1 81  82 12. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS Similarly, all one needs to know about the k-place relation P can be obtained from its characteristic function : 1 if P(ni, ..., nk) is true; xp(ni, . .. , na)= . 0 if P(ni,..., nk) is false. The basic convention for representing natural numbers on the tape of a standard Turing machine is a slight variation of unary notation: n is represented by 11+1. (Why would using 11 be a bad idea?) A k-tuple (n1, n2, ..., nk) E N will be represented by 111+10112+10... 011k+1, i.e. with the representations of the individual numbers separated by Os. This scheme is inefficient in its use of space compared to binary notation, for example but it is simple and can be implemented on Turing machines restricted to the alphabet {1}. Turing computable functions. With suitable conventions for representing the input and output of a function on the natural numbers on the tape of a Turing machine in hand, we can define what it means for a function to be computable by a Turing machine. DEFINITION 12.1. A k-place function f is Turing computable, or just computable, if there is a Turing machine M such that for any k-tuple (ni,... , nk) E dom(f) the computation of M with input tape 0111+10112+1 . . . 01nk+1 eventually halts with output tape 01f(ni,.,)+1. Such a machine M is said to compute f. Note that for a Turing machine M to compute a function f, M need only do the right thing on the right kind of input: what M does in other situations does not matter. In particular, it does not matter what M might do with k-tuple which is not in the domain of f. EXAMPLE 12.1. The identity function iN: N - N, i.e. iN(n) = n, is computable. It is computed by M = 0, the Turing machine with an empty table that does absolutely nothing on any input. EXAMPLE 12.2. The projection function wrl : N2 - N given by Fr2(n, m) = n is computed by the Turing machine: P2 0 1 1 0R2 2 0R3 1R2 3 0L4 0R3 4 0LA 1L5 5 1L5  12. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS 83 Pl acts as follows: it moves to the right past the first block of is without disturbing it, erases the second block of is, and then returns to the left of first block and halts. The projection function 72 : N2 - N given by 72(n, m) = m is also computable: the Turing machine P of Example 10.5 does the job. PROBLEM 12.1. Find Turing machines that compute the following functions and explain how they work. (1) O (n) = 0. (2) S(n) = n + 1. (3) SuM(n,m)=n+m. n-1 >nn (4) PRED(n) = 0 n=0 (5) DIFF(n, m) = 0o n C< m (6) w2(p, q, r) = q. (7) 72 (ai, . . . , ai, . . . , ak) = a2 We will consider methods for building functions computable by Tur- ing machines out of simpler ones later on. A non-computable function. In the meantime, it is worth ask- ing whether or not every function on the natural numbers is com- putable. No such luck! PROBLEM 12.2. Show that there is some 1-place function f : N - N which is not computable by comparing the number of such functions to the number of Turing machines. The argument hinted at above is unsatisfying in that it tells us there is a non-computable function without actually producing an explicit example. We can have some fun on the way to one. DEFINITION 12.2 (Busy Beaver Competition). A machine M is an n-state entry in the busy beaver competition if: " M has a two-way infinite tape and alphabet {1} (see Chap- ter 11; " M has n + 1 states, but state n + 1 is used only for halting (so both M(n + 1, 0) and M(n + 1, 1) are undefined); * M eventually halts when given a blank input tape. M's score in the competition is the number of l's on the output tape of its computation from a blank input tape. The greatest possible score of an in-state entry in the competition is denoted by E(in).  84 12. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS Note that there are only finitely many possible n-state entries in the busy beaver competition because there are only finitely many (n + 1)- state Turing machines with alphabet {1}. Since there is at least one n-state entry in the busy beaver competition for every n;> 0 , it follows that E(n) is well-defined for each n E N. EXAMPLE 12.3. M = 0 is the only 0-state entry in the busy beaver competition, so E(0) = 0. EXAMPLE 12.4. The machine P given by P 0 1 1 1R2 1L2 2 1L1 1L3 is a 2-state entry in the busy beaver competition with a score of 4, so E(2) > 4. The function E grows extremely quickly. It is known that E(0) = 0, E(1) = 1, E(2) = 4, E(3) = 6, and E(4) = 13. The value of E(5) is still unknown, but must be quite large.1 PROBLEM 12.3. Show that: (1) The 2-state entry given in Example 12.4 actually scores 4. (2) E(1)=1. (3) E(3)>6. (4) E(n) 1, g is an m-place function, and hi, ..., hm are k-place functions. Then the k-place function f is said to be obtained from g, hi, ..., hm by composition, written as f =g o(hi,...,hm), if for all (ni, ..., nk) E Nk, f (ni, ... ,1nk) = g(hi(n1, ... ,1nk), ... , hm(n1i, ... ,nk)). EXAMPLE 12.5. The constant function cl, where cl(n) = 1 for all n, can be obtained by composition from the functions S and O. For any n E N, ct(n) =_(S o O)(n) = S(O(n)) = S(0) = 0 + 1 = 1. PROBLEM 12.6. Suppose k > 1 and a E N. Use composition to define the constant function ca, where c (n1,..., nk) = a for all (n1,... , nk) E Nk, from functions already known to be computable. PROPOSITION 12.7. Suppose that 1 < k, 1 < m, g is a Turing computable m-place function, and h1, ..., hm are Turing computable k-place functions. Then g o (h1,... , hm) is also Turing computable. Starting with a small set of computable functions, and applying computable ways (such as composition) of building functions from sim- pler ones, we will build up a useful collection of computable functions. This will also provide a characterization of computable functions which does not mention any type of computing device. The "small set of computable functions" that will be the fundamen- tal building blocks is infinite only because it includes all the projection functions. DEFINITION 12.4. The following are the initial functions: " O, the 1-place function such that O(n) = 0 for all n E N; " S, the 1-place function such that S(n) = n + 1 for all n E N; and, " for each k > 1 and 1 < i < k, wI, the k-place function such that wf(n1,..., nk) = n2 for all (n1,.... , nk) E Nk. 0 is often referred to as the zero function, S is the successor function, and the functions 7k are called the projection functions. Note that 71 is just the identity function on N. We have already shown, in Problem 12.1, that all the initial func- tions are computable. It follows from Proposition 12.7 that every func- tion defined from the initial functions using composition (any number of times) is computable too. Since one can build relatively few func- tions from the initial functions using only composition.. .  86 12. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS PROPOSITION 12.8. Suppose f is a 1-place function obtained from the initial functions by finitely many applications of composition. Then there is a constant c E N such that f (n) < n+ c for all n E N. ... in the next chapter we will add other methods of building func- tions to our repertoire that will allow us to build all computable func- tions from the initial functions.  CHAPTER 13 Recursive Functions We will add two other methods of building computable functions from computable functions to composition, and show that one can use the three methods to construct all computable functions on N from the initial functions. Primitive recursion. The second of our methods is simply called recursion in most parts of mathematics and computer science. His- torically, the term "primitive recursion" has been used to distinguish it from the other recursive method of defining functions that we will consider, namely unbounded minimalization. ... Primitive recursion boils down to defining a function inductively, using different functions to tell us what to do at the base and inductive steps. Together with composition, it suffices to build up just about all familiar arithmetic functions from the initial functions. DEFINITION 13.1. Suppose that k;> 1, g is a k-place function, and h is a k + 2-place function. Let f be the (k + 1)-place function such that (1) f (ni, ... , nm, 0) = g(ni, ... , n) and (2) f(ni, ... , nT, m + 1) = h (ni, ... , nk, m, f(ni, . . ., n, m)) for every (ni,..., nk) E Nk and m E N. Then f is said to be obtained from g and h by primitive recursion. That is, the initial values of f are given by g, and the rest are given by h operating on the given input and the preceding value of f. For a start, primitive recursion and composition let us define addi- tion and multiplication from the initial functions. EXAMPLE 13.1. SUM(n, m) = n+m is obtained by primitive recur- sion from the initial function wi and the composition S o w7 of initial functions as follows: * SuM(n, 0) = w7(n); " SUM(n, m + 1) = (S O w7)(n, m, SUM(n, m)). To see that this works, one can proceed by induction on m: 87  88 13. RECURSIVE FUNCTIONS At the base step, m = 0, we have SUM(n, 0) =w(n) = n = n + 0. Assume that m;> 0 and SUM(n, m) = n + m. Then SUM(n, m + 1) = (S o w3)(n, m, SUM(n, m)) = S(w3(n, m, SUM(n, m))) = S(SUM(n, m)) = SUM(n, m) + 1 n+m+1, as desired. As addition is to the successor function, so multiplication is to addition. EXAMPLE 13.2. MULT(n, m) = nm is obtained by primitive recur- sion from 0 and SUM o (733, wy): " MULT(n, 0) 0=O(n); " MULT(n, m + 1) = (SUM o (73, wf))(n, m, MULT(n, m)). We leave it to the reader to check that this works. PROBLEM 13.1. Use composition and primitive recursion to obtain each of the following functions from the initial functions or other func- tions already obtained from the initial functions. (1) ExP(n, m) = nm (2) PRED(n) (defined in Problem 12.1) (3) DIFF(n, m) (defined in Problem 12.1) (4) FACT(n) = n! PROPOSITION 13.2. Suppose k > 1, g is a Turing computable k- place function, and h is a Turing computable (k + 2)-place function. If f is obtained from g and h by primitive recursion, then f is also Turing computable. Primitive recursive functions and relations. The collection of functions which can be obtained from the initial functions by (possibly repeatedly) using composition and primitive recursion is useful enough to have a name. DEFINITION 13.2. A function f is primitive recursive if it can be defined from the initial functions by finitely many applications of the operations of composition and primitive recursion. So we already know that all the initial functions, addition, and multiplication, among others, are primitive recursive.  13. RECURSIVE FUNCTIONS 89 PROBLEM 13.3. Show that each of the following functions is prim- itive recursive. (1) For any k > 0 and primitive recursive (k + 1)-place function g, the (k + 1)-place function f given by f (ni, ..... ,, m) = UJog(ni, ... ,hn, i) = g(ni, ... , nk, 0) - . . . -g(ni,... , nk, im) (2) For any constant a E N, X{a}(n) =0{ n 1 n=a. (3) h(ni,.k.(.,,n ) = , if a (ni,., nk) =(c1,...ck) f is a primitive recursive k-place function and a, c1,... , ck E N are constants. THEOREM 13.4. Every primitive recursive function is Turing com- putable. Be warned, however, that there are computable functions which are not primitive recursive. We can extend the idea of "primitive recursive" to relations by using their characteristic functions. DEFINITION 13.3. Suppose k > 1. A k-place relation P C Nk is primitive recursive if its characteristic function p~nl,.., k) 1I(ni, ..., nk) E P 0 (i .,n) P is primitive recursive. EXAMPLE 13.3. P = {2} C N is primitive recursive since X{2} is recursive by Problem 13.3. PROBLEM 13.5. Show that the following relations and functions are primitive recursive. (1) ,iP, i.e. Nk \ P, if P is a primitive recursive k-place relation. (2) P V Q, i.e. P U Q, if P and Q are primitive recursive k-place relations. (3) P A Q, i.e. P 0 Q, if P and Q are primitive recursive k-place relations. (4) EQUAL, where EQUAL(n2, m) <----> nm. (5) h(ni,. ..,n2k,mr) = Eitog(ni,... ,nk,i), for any k ;> 0 and primitive recursive (k + 1)-place function g. (6) Dlv, where Dw12, m) <->1 nn.  90 13. RECURSIVE FUNCTIONS (7) ISPRIME, where ISPRIME(n) < n is prime. (8) PRIME(k) =Pk, where po = 1 and pk is the kth prime if k > 1. (9) POWER(n, m) = k, where k;> 0 is maximal such that nk |M. (10) LENGTH(n) =_E, where £ is maximal such that p n. (11) ELEMENT(n, i) = n2, if n = pf1 (.. plkand n2 = 0 if i > k). . . p p1. . . p~jif 1 pl'... p" E P' . A computable but not primitive recursive function. While primitive recursion and composition do not quite suffice to build all Turing computable functions from the initial functions, they are pow- erful enough that specific counterexamples are not all that easy to find. EXAMPLE 13.4 (Ackerman's Function). Define the 2-place function A from as follows: " A(0,j) = S(f) " A(S(k), 0) = A(k, 1) * A(S(k),S(f)) = A(k,A(S(k),f)) Given A, define the 1-place function a by a(n) = A(n, n). It isn't too hard to show that A, and hence also a, are Turing computable. However, though it takes considerable effort to prove it, a grows faster with in than any primitive recursive function. (Try working out the first few values of . . .)  13. RECURSIVE FUNCTIONS 91 PROBLEM 13.8. Show that the functions A and a defined in Exam- ple 13.4 are Turing computable. If you are very ambitious, you can try to prove the following theo- rem. THEOREM 13.9. Suppose a is the function defined in Example 13.4 and f is any primitive recursive function. Then there is an n E N such that for all k > n, a(k) > f(k). COROLLARY 13.10. The function a defined in Example 13.4 is not primitive recursive. ... but if you aren't, you can still try the following exercise. PROBLEM 13.11. Informally, define a computable function which must be different from every primitive recursive function. Unbounded minimalization. The last of our three method of building computable functions from computable functions is unbounded minimalization. The functions which can be defined from the initial functions using unbounded minimalization, as well as composition and primitive recursion, turn out to be precisely the Turing computable functions. Unbounded minimalization is the counterpart for functions of "brute force" algorithms that try every possibility until they succeed. (Which, of course, they might not... ) DEFINITION 13.4. Suppose k > 1 and g is a (k + 1)-place func- tion. Then the unbounded minimalization of g is the k-place function f defined by f(ni,...,mnk) = m wherermis least so that g(nl, ..., nk, m) = 0. This is often written as f(ni,..., nk) = m[g(ni, ... , n, m) = 01. NOTE. If there is no m such that g(ni, ... , nk, m) = 0, then the unbounded minimalization of g is not defined on (ni,..., nk). This is one reason we will occasionally need to deal with partial functions. If the unbounded minimalization of a computable function is to be computable, we have a problem even if we ask for some default out- put (0, say) to ensure that it is defined for all k-tuples. The obvious procedure which tests successive values of g to find the needed m will run forever if there is no such mn, and the incomputability of the Halt- ing Problem suggests that other procedure's won't necessarily succeed either. It follows that it is desirable to be careful, so far as possible, which functions unbounded minimalization is applied to.  92 13. RECURSIVE FUNCTIONS DEFINITION 13.5. A (k + 1)-place function g is said to be regular if for every (ni,..., nk) E Nk, there is at least one m E N so that g(ni,.. . . ,n, m) = 0. That is, g is regular precisely if the obvious strategy of computing g(ni,... , nk, m) for m = 0, 1, ... in succession until an m is found with g(ni,... , nk, m) = 0 always succeeds. PROPOSITION 13.12. If g is a Turing computable regular (k + 1)- place function, then the unbounded minimalization of g is also Turing computable. While unbounded minimalization adds something essentially new to our repertoire, it is worth noticing that bounded minimalization does not. PROBLEM 13.13. Suppose g is a (k + 1) -place primitive recursive regular function such that for some primitive recursive k-place function h, pm[g(ni,..., nk, m) = 0] h(ni,... , nk) for all (n1,... , nk) E N. Show that pm[g(n1,... , nk,im) = 0] is also primitive recursive. Recursive functions and relations. We can finally define an equivalent notion of computability for functions on the natural numbers which makes no mention of any computational device. DEFINITION 13.6. A k-place function f is recursive if it can be defined from the initial functions by finitely many applications of com- position, primitive recursion, and the unbounded minimalization of regular functions. Similarly, k-place partial function is recursive if it can be defined from the initial functions by finitely many applications of composition, primitive recursion, and the unbounded minimalization of (possibly non-regular) functions. In particular, every primitive recursive function is a recursive func- tion. THEOREM 13.14. Every recursive function is Turing computable. We shall show that every Turing computable function is recursive later on. Similarly to primitive recursive relations we have the follow- ing. DEFINITION 13.7. A k-place relation P is said to be recursive ( Tur- ing computable) if its characteristic function XP is recursive (Turing computable).  13. RECURSIVE FUNCTIONS 93 Since every recursive function is Turing computable, and vice versa, "recursive" is just a synonym of "Turing computable", for functions and relations alike. Also, similarly to Theorem 13.6 and Corollary 13.7 we have the following. THEOREM 13.15. A k-place function g is recursive if and only if the 1-place function h given by h(n) = g(n1,... , n) if n = plfpl is recursive. As before, it doesn't really matter what the function h does on an n which does not represent a sequence of length k. COROLLARY 13.16. A k-place relation P is recursive if and only if the 1-place relation P' is recursive, where (n1,... ,nfk) E P p1'...pkk E P'.   CHAPTER 14 Characterizing Computability By putting together some of the ideas in Chapters 12 and 13, we can use recursive functions to simulate Turing machines. This will let us show that Turing computable functions are recursive, completing the argument that Turing machines and recursive functions are essentially equivalent models of computation. We will also use these techniques to construct an universal Turing machine (or UTM): a machine U that, when given as input (a suitable description of) some Turing machine M and an input tape a for M, simulates the computation of M on input a. In effect, an universal Turing machine is a single piece of hardware that lets us treat other Turing machines as software. Turing computable functions are recursive. Our basic strat- egy is to show that any Turing machine can be simulated by some recursive function. Since recursive functions operate on integers, we will need to encode the tape positions of Turing machines, as well as Turing machines themselves, by integers. For simplicity, we shall stick to Turing machines with alphabet {1}; we already know from Chap- ter 11 that such machines can simulate Turing machines with bigger alphabets. DEFINITION 14.1. Suppose (s, i, a) is a tape position such that all but finitely many cells of a are blank. Let n be any positive integer such that ak = 0 for all k > n. Then the code of (s, i, a) is (si, a) = 2s35ao7a11a2 . ..p+ EXAMPLE 14.1. Consider the tape position (2, 1, 1001). Then r(2, 1, 1001) =22315170110131 =780. PROBLEM 14.1. Find the codes of the following tape positions. (1) (1, 0, a), where a is entirely blank. (2) (4, 3, a), where a is 1011100101. PROBLEM 14.2. What is the tape position whose code is 10314720? When dealing with computations, we will also need to encode se- quences of tape positions by integers. 95  96 14. CHARACTERIZING COMPUTABILITY DEFINITION 14.2. Suppose tit2... tin is a sequence of tape positions. Then the code of this sequence is tit2. . . t7 - - 2 6'3t '. . . ' NOTE. Both tape positions and sequences of tape positions have unique codes. PROBLEM 14.3. Pick some (short!) sequence of tape positions and find its code. Having defined how to represent tape positions as integers, we now need to manipulate these representations using recursive functions. The recursive functions and relations in Problems 13.3 and 13.5 provide most of the necessary tools. PROBLEM 14.4. Show that both of the following relations are prim- itive recursive. (1) TAPEPOS, where TAPEPOS(n) < n is the code of a tape position. (2) TAPEPOSSEQ, where TAPEPOSSEQ(n) < n is the code of a sequence of tape positions. PROBLEM 14.5. Show that each of the following is primitive recur- sive. (1) The 4-place function ENTRY such that ENTRY(j, w, t, n) (t, i +w - 1, a') if n = (s,i,a)7, j E {0, 1}, w E {0,2}, i+w- 1;>0, andt> 1, where a'= ak for k i and a'= j; 0 otherwise. (2) For any Turing machine M with alphabet {1}, the 1-place function STEPM such that M (s, i, a)7 if n =- (s, i, a)7 and STEPM(n) = M(s, i, a) is defined; 10 otherwise. (3) For any Turing machine M with alphabet {1}, the 1-place re- lation COMPM, where COMPM(n) - n is the code of a computation of M.  14. CHARACTERIZING COMPUTABILITY 97 The functions and relations above may be primitive recursive, but the last big step in showing that Turing computable functions are re- cursive requires unbounded minimalization. PROPOSITION 14.6. For any Turing machine M with alphabet {1}, the 1-place (partial) function SIMM is recursive, where SIMM(n) = (t,J, b) if n =E(1, 0,a) 7 for some input tape a and M eventually halts in position (t, j, b) on input a. (Note that SIMM(n) may be undefined if n f r(1, 0,a) 7 for an input tape a, or if M does not eventually halt on input a.) LEMMA 14.7. Show that the following functions are primitive re- cursive: (1) For anyfixed k;> 1, CoDEk (n1,... , nk) = r(1, 0, 01n10...).01 - (2) DECODE(t) = n if t =7|(s, i, 01n+1)7 (and anything you like otherwise). THEOREM 14.8. Any k-place Turing computable function is recur- sive. COROLLARY 14.9. A function f : Nk - N is Turing computable if and only if it is recursive. Thus Turing machines and recursive functions are essentially equiv- alent models of computation. An universal Turing machine. One can push the techniques used above little farther to get a recursive function that can simulate any Turing machine. Since every recursive function can be computed by some Turing machine, this effectively gives us an universal Turing machine. PROBLEM 14.10. Devise a suitable definition for the code 'M7 of a Turing machine M with alphabet {1}. PROBLEM 14.11. Show, using your definition of' M7 from Problem 14.10, that the following are primitive recursive. (1) The 2-place function STEP, where STEP(m, n) { 'M(s, i, a)7 ifm m =M7 for some machine M, n = '(s, i, a)7, & M(s, i, a) is defined; 0 otherwise.  98 14. CHARACTERIZING COMPUTABILITY (2) The 2-place relation COMP, where COMP(m,n) < m = 1M1 for some Turing machine M and n is the code of a computation of M. PROPOSITION 14.12. The 2-place (partial) function SIM is recur- sive, where, for any Turing machine M with alphabet {1} and input tape a for M, SIM(7M7,7(1,0, a)7) = (t,jb)7 if M eventually halts in position (t, j, b) on input a. (Note that SIM(m, n) may be undefined if m is not the code of some Turing machine M, or if n r (1, 0, a)7 for an input tape a, or if M does not eventually halt on input a.) COROLLARY 14.13. There is a Turing machine U which can simu- late any Turing machine M. COROLLARY 14.14. There is a recursive function f which can com- pute any other recursive function. The Halting Problem. An effective method to determine whether or not a given machine will eventually halt on a given input short of waiting forever! would be nice to have. For example, assuming Church's Thesis is true, such a method would let us identify computer programs which have infinite loops before we attempt to execute them. THE HALTING PROBLEM. Given a Turing machine M and an in- put tape a, is there an effective method to determine whether or not M eventually halts on input a? Given that we are using Turing machines to formalize the notion of an effective method, one of the difficulties with solving the Halting Problem is representing a given Turing machine and its input tape as input for another machine. As this is one of the things that was accom- plished in the course of constructing an universal Turing machine, we can now formulate a precise version of the Halting Problem and solve it. THE HALTING PROBLEM. Is there a Turing machine T which, for any Turing machine M with alphabet {1} and tape a for M, halts on input with output 011 if M halts on input a, and with output 01 if M does not halt on input a?  14. CHARACTERIZING COMPUTABILITY 99 Note that this precise version of the Halting Problem is equivalent to the informal one above only if Church's Thesis is true. PROBLEM 14.15. Show that there is a Turing machine C which, for any Turing machine M with alphabet {1}, on input 01Mu+1 eventually halts with output 01rM'+101-(0,1,01' "'+1),+1 THEOREM 14.16. The answer to (the precise version of) the Halting Problem is "No." Recursively enumerable sets. The following notion is of partic- ular interest in the advanced study of computability. DEFINITION 14.3. A subset (i.e. a 1-place relation) P of N is re- cursively enumerable, often abbreviated as r. e., if there is a 1-place recursive function f such that P = im(f) = { f (n) | n E N }. Since the image of any recursive 1-place function is recursively enu- merable by definition, we do not lack for examples. For one, the set E of even natural numbers is recursively enumerable, since it is the image of f (n) = MULT(S(S(O(n))), n). PROPOSITION 14.17. If P is a 1-place recursive relation, then P is recursively enumerable. This proposition is not reversible, but it does come close. PROPOSITION 14.18. P C N is recursive if and only if both P and N \ P are recursively enumerable. PROBLEM 14.19. Find an example of a recursively enumerable set which is not recursive. PROBLEM 14.20. Is P C N primitive recursive if and only if both P and N \ P are enumerable by primitive recursive functions? PROBLEM 14.21. P C N recursively enumerable if and only if there is a 1-place recursive partial function g such that P =dom(g) ={ n g(n) is defined }   Hints for Chapters 10-14 Hints for Chapter 10. 10.1. This should be easy... 10.2. Ditto. 10.3. (1) Any machine with the given alphabet and a table with three non-empty rows will do. (2) Every entry in the table in the 0 column must write a 1 in the scanned cell; similarly, every entry in the 1 column must write a 0 in the scanned cell. (3) What's the simplest possible table for a given alphabet? 10.4. Unwind the definitions step by step in each case. Not all of these are computations... 10.5. Examine your solutions to the previous problem and, if nec- essary, take the computations a little farther. 10.6. Have the machine run on forever to the right, writing down the desired pattern as it goes no matter what may be on the tape already. 10.7. Consider your solution to Problem 10.6 for one possible ap- proach. It should be easy to find simpler solutions, though. 10.8. Consider the tasks S and T are intended to perform. 10.9. (1) Use four states to write the is, one for each. (2) The input has a convenient marker. (3) Run back and forth to move one marker n cells from the block of l's while moving another through the block, and then fill in. (4) Modify the previous machine by having it delete every other 1 after writing out 12n. (5) Run back and forth to move the right block of is cell by cell to the desired position. (6) Run back and forth to move the left block of is cell by cell past the other two, and then apply a minor modification of the machine in part 5. 101  102 HINTS FOR CHAPTERS 10-14 (7) Variations on the ideas used in part 6 should do the job. (8) Run back and forth between the blocks, moving a marker through each. After the race between the markers to the ends of their respective blocks has been decided, erase everything and write down the desired output. Hints for Chapter 11. 11.1. This ought to be easy. 11.2. Generalize the technique of Example 11.1, adding two new states to help with each old state that may cause a move in different directions. You do have to be a bit careful not to make a machine that would run off the end of the tape when the original would not. 11.3. You only need to change the parts of the definitions involving the symbols 0 and 1. 11.4. If you have trouble figuring out whether the subroutine of Z simulating state 1 of W on input y, try tracing the partial computations of W and Z on other tapes involving y. 11.5. Generalize the concepts used in Example 11.2. Note that the simulation must operate with coded versions of Ms tape, unless E {1}. The key idea is to use the tape of the simulator in blocks of some fixed size, with the patterns of Os and is in each block corresponding to elements of E. 11.6. This should be straightforward, if somewhat tedious. You do need to be careful in coming up with the appropriate input tapes for 0. 11.7. Generalize the technique of Example 11.3, splitting up the tape of the simulator into upper and lower tracks and splitting each state of N into two states in P. You will need to be quite careful in describing just how the latter is to be done. 11.8. This is mostly pretty easy. The only problem is to devise N so that one can tell from its output whether P halted or crashed, and this is easy to indicate using some extra symbol in Ns alphabet. 11.9. If you're in doubt, go with one read/write scanner for each tape, and have each entry in the table of a two-tape machine take both scanners into account. Simulating such a machine is really just a variation on the techniques used in Example 11.3.  HINTS FOR CHAPTERS 10-14 103 11.10. Such a machine should be able to move its scanner to cells up and down from the current one, as well to the side. (Diagonally too, if you want to!) Simulating such a machine on a single tape machine is a challenge. You might find it easier to first describe how to simulate it on a suitable multiple-tape machine. Hints for Chapter 12. 12.1. (1) Delete most of the input. (2) Add a one to the far end of the input. (3) Add a little to the input, and delete a little more elsewhere. (4) Delete a little from the input most of the time. (5) Run back and forth between the two blocks in the input, delet- ing until one side disappears. Clean up appropriately! (This is a relative of Problem 10.9.8.) (6) Delete two of blocks and move the remaining one. (7) This is just a souped-up version of the machine immediately preceding... 12.2. There are just as many functions N - N as there are real numbers, but only as many Turing machines as there are natural num- bers. 12.3. (1) Trace the computation through step-by-step. (2) Consider the scores of each of the 1-state entries in the busy beaver competition. (3) Find a 3-state entry in the busy beaver competition which scores six. (4) Show how to turn an n-state entry in the busy beaver compe- tition into an (n + 1)-state entry that scores just one better. 12.4. You could start by looking at modifications of the 3-state entry you devised in Problem 12.3.3, but you will probably want to do some serious fiddling to do better than what Problem 12.3.4 do from there. 12.5. Suppose E was computable by a Turing machine M. Modify M to get an n-state entry in the busy beaver competition for some n which achieves a score greater than E(n). The key idea is to add a "pre-processor" to M which writes a block with more is than the number odf states that M and the pre-processor have between them. 12.6. Generalize Example 12.5.  104 HINTS FOR CHAPTERS 10-14 12.7. Use machines computing g, hi, ..., hm as sub-machines of the machine computing the composition. You might also find sub- machines that copy the original input and various stages of the output useful. It is important that each sub-machine get all the data it needs and does not damage the data needed by other sub-machines. 12.8. Proceed by induction on the number of applications of com- position used to define f from the initial functions. Hints for Chapter 13. 13.1. (1) Exponentiation is to multiplication as multiplication is to addition. (2) This is straightforward except for taking care of PRED(O) = PRED(1) = 0. (3) DIFF is to PRED as S is to SUM. (4) This is straightforward if you let 0! = 1. 13.2. Machines used to compute g and h are the principal parts of the machine computing f, along with parts to copy, move, and/or delete data on the tape between stages in the recursive process. 13.3. (1) f is to g as FACT is to the identity function. (2) Use DIFF and a suitable constant function as the basic building blocks. (3) This is a slight generalization of the preceding part. 13.4. Proceed by induction on the number of applications of prim- itive recursion and composition. 13.5. (1) Use a composition including DIFF, Xp, and a suit- able constant function. (2) A suitable composition will do the job; it's just a little harder than it looks. (3) A suitable composition will do the job; it's rather more straight- forward than the previous part. (4) Note that n = m exactly when n - m = 0 = m - n. (5) Adapt your solution from the first part of Problem 13.3. (6) First devise a characteristic function for the relation PRODUCT(n, k, m) nk = , and then sum up. (7) Use XDiv and sum up. (8) Use ISPRIME and some ingenuity. (9) Use EXP and Div and some more ingenuity. (10) A suitable combination of PRIME with other things will do.  HINTS FOR CHAPTERS 10-14 105 (11) A suitable combination of PRIME and POWER will do. (12) Throw the kitchen sink at this one... (13) Ditto. 13.6. In each direction, use a composition of functions already known to be primitive recursive to modify the input as necessary. 13.7. A straightforward application of Theorem 13.6. 13.8. This is not unlike, though a little more complicated than, showing that primitive recursion preserves computability. 13.9. It's not easy! Look it up... 13.10. This is a very easy consequence of Theorem 13.9. 13.11. Listing the definitions of all possible primitive recursive functions is a computable task. Now borrow a trick from Cantor's proof that the real numbers are uncountable. (A formal argument to this effect could be made using techniques similar to those used to show that all Turing computable functions are recursive in the next chapter.) 13.12. The strategy should be easy. Make sure that at each stage you preserve a copy of the original input for use at later stages. 13.13. The primitive recursive function you define only needs to check values of g(n, ....,mnk, m) for m such that 0 < m < h(nl,...,nk), but it still needs to pick the least m such that g(ni, ... , nk, m) = 0. 13.14. This is very similar to Theorem 13.4. 13.15. This is virtually identical to Theorem 13.6. 13.16. This is virtually identical to Corollary 13.7. Hints for Chapter 14. 14.1. Emulate Example 14.1 in both parts. 14.2. Write out the prime power expansion of the given number and unwind Definition 14.1. 14.3. Find the codes of each of the positions in the sequence you chose and then apply Definition 14.2. 14.4. (1) XTAPEPOS(n) = 1 exactly when the power of 2 in the prime power expansion of n is at least 1 and every other prime appears in the expansion with a power of 0 or 1. This can be achieved with a composition of recursive functions from Problems 13.3 and 13.5.  106 HINTS FOR CHAPTERS 10-14 (2) XTAPEPOSSEQ(n) = 1 exactly when n is the code of a sequence of tape positions, i. e. every power in the prime power expansion of n is the code of a tape position. 14.5. (1) If the input is of the correct form, make the necessary changes to the prime power expansion of n using the tools in Problem 13.5. (2) Piece STEPM together by cases using the function ENTRY in each case. The piecing-together works a lot like redefining a function at a particular point in Problem 13.3. (3) If the input is of the correct form, use the function STEPM to check that the successive elements of the sequence of tape positions are correct. 14.6. The key idea is to use unbounded minimalization on XCOMP, with some additions to make sure the computation found (if any) starts with the given input, and then to extract the output from the code of the computation. 14.7. (1) To define CODEk, consider what ' (1, 0, 01"10... 011k)7 is as a prime power expansion, and arrange a suitable compo- sition to obrtain it from (n1, . . . ,Tnk). (2) To define DECODE you only need to count how many pow- ers of primes other than 3 in the prime-power expansion of '(s, i, 01n+1)7 are equal to 1. 14.8. Use Proposition 14.6 and Lemma 14.7. 14.9. This follows directly from Theorems 13.14 and 14.8. 14.10. Take some creative inspiration from Definitions 14.1 and 14.2. For example, if (s, i) E dom(M) and M(s, i) = (j, d, t), you could let the code of M(s, i) be '7M(s, i)7 '- 2335j7d+111t. 14.11. Much of what you need for both parts is just what was needed for Problem 14.5, except that STEP is probably easier to define than STEPM was. (Define it as a composition...) The additional ingredients mainly have to do with using m = M7 properly. 14.12. Essentially, this is to Problem 14.11 as proving Proposition 14.6 is to Problem 14.5. 14.13. The machine that computes SIM does the job.  HINTS FOR CHAPTERS 10-14 107 14.14. A modification of SIM does the job. The modifications are needed to handle appropriate input and output. Check Theorem 13.15 for some ideas on what may be appropriate. 14.15. This can be done directly, but may be easier to think of in terms of recursive functions. 14.16. Suppose the answer was yes and such a machine T did exist. Create a machine U as follows. Give T the machine C from Problem 14.15 as a pre-processor and alter its behaviour by having it run forever if M halts and halt if M runs forever. What will T do when it gets itself as input? 14.17. Use xP to help define a function f such that im(f) = P. 14.18. One direction is an easy application of Proposition 14.17. For the other, given an n E N, run the functions enumerating P and N \ P concurrently until one or the other outputs n. 14.19. Consider the set of natural numbers coding (according to some scheme you must devise) Turing machines together with input tapes on which they halt. 14.20. See how far you can adapt your argument for Proposition 14.18. 14.21. This may well be easier to think of in terms of Turing ma- chines. Run a Turing machine that computes g for a few steps on the first possible input, a few on the second, a few more on the first, a few more on the second, a few on the third, a few more on the first, ...   Part IV Incompleteness   CHAPTER 15 Preliminaries It was mentioned in the Introduction that one of the motivations for the development of notions of computability was the following question. ENTSCHEIDUNGSPROBLEM. Given a reasonable set E of formulas of a first-order language C and a formula c of C, is there an effective method for determining whether or not E H p? Armed with knowledge of first-order logic on the one hand and of computability on the other, we are in a position to formulate this question precisely and then solve it. To cut to the chase, the answer is usually "no". Gbdel's Incompleteness Theorem asserts, roughly, that given any set of axioms in a first-order language which are computable and also powerful enough to prove certain facts about arithmetic, it is possible to formulate statements in the language whose truth is not decided by the axioms. In particular, it turns out that no consistent set of axioms can hope to prove its own consistency. We will tackle the Incompleteness Theorem in three stages. First, we will code the formulas and proofs of a first-order language as num- bers and show that the functions and relations involved are recursive. This will, in particular, make it possible for us to define a "computable set of axioms" precisely. Second, we will show that all recursive func- tions and relations can be defined by first-order formulas in the presence of a fairly minimal set of axioms about elementary number theory. Fi- nally, by putting recursive functions talking about first-order formulas together with first-order formulas defining recursive functions, we will manufacture a self-referential sentence which asserts its own unprov- ability. NOTE. It will be assumed in what follows that you are familiar with the basics of the syntax and semantics of first-order languages, as laid out in Chapters 5-8 of this text. Even if you are already familiar with the material, you may wish to look over Chapters 5-8 to familiarize yourself with the notation, definitions, and conventions used here, or at least keep them handy in case you need to check some such point. 111  112 15. PRELIMINARIES A language for first-order number theory. To keep things as concrete as possible we will work with and in the following language for first-order number theory, mentioned in Example 5.2. DEFINITION 15.1. EN is the first-order language with the following symbols: (1) Parentheses: ( and ) (2) Connectives: and - (3) Quantifier: V (4) Equality: = (5) Variable symbols: v0, v2, v3, ... (6) Constant symbol: 0 (7) 1-place function symbol: S (8) 2-place function symbols: +, -, and E. The non-logical symbols of 'N, 0, S, +, -, and E, are intended to name, respectively, the number zero, and the successor, addition, multiplication, and exponentiation functions on the natural numbers. That is, the (standard!) structure this language is intended to discuss is 91 (N,0,S,+,.,E). Completeness. The notion of completeness used in the Incom- pleteness Theorem is different from the one used in the Completeness Theorem.1 "Completeness" in the latter sense is a property of a logic: it asserts that whenever F |=uo (i.e. the truth of the sentence o follows from that of the set of sentences F), F H o- (i.e. there is a deduction of o from F). The sense of "completeness" in the Incompleteness Theorem, defined below, is a property of a set of sentences. DEFINITION 15.2. A set of sentences E of a first-order language C is said to be complete if for every sentence r either E H r or E H -ir. That is, a set of sentences, or non-logical axioms, is complete if it suffices to prove or disprove every sentence of the langage in in question. PROPOSITION 15.1. A consistent set E of sentences of a first-order language C is complete if and only if the theory of E, Th(E) ={T T is a sentence of 1 and E H T}, is maximally consistent. 1Which, to confuse the issue, was also first proved by Kurt G6del.  CHAPTER 16 Coding First-Order Logic We will encode the symbols, formulas, and deductions of EN as natural numbers in such a way that the operations necessary to ma- nipulate these codes are recursive. Although we will do so just for IJN, any countable first-order language can be coded in a similar way. Godel coding. The basic approach of the coding scheme we will use was devised by Gbdel in the course of his proof of the Incomplete- ness Theorem. DEFINITION 16.1. To each symbol s of 'N we assign an unique positive integer Esc, the Gddel code of s, as follows: (1) E( 1 and E)= 2 (2) 7,Q 3 and 7 = 4 (3) EV7 - 5 (4) r=_ - 6. (5) Ev, k + 12 (6) 7,- 7 (7) ES7 - 8 (8) r+7 = 9, r-.7 = 10, and EE7 = 11 Note that each positive integer is the Gbdel code of one and only one symbol of 'N. We will also need to code sequences of the symbols of £N, such as terms and formulas, as numbers, not to mention sequences of sequences of symbols of £N, such as deductions. DEFINITION 16.2. Suppose s1s2... Sk is a sequence of symbols of 'N. Then the Gddel code of this sequence is F -I - F s 81 . . . Sk -p . . k, where pn is the nth prime number. Similarly, if o1-2... o- is a sequence of sequences of symbols of £N, then the Gddel code of this sequence is o-1...of-,= p " ...p. 113  114 16. CODING FIRST-ORDER LOGIC EXAMPLE 16.1. The code of the formula Vv1 =-v1SOv1 (the official form of Vv1 v1 - SO= v1), EVv1 =v1S0v17, works out to 2r- 3rV1-'5r=-' 7r''11rv1-'13rs-'17ro-'19rv1 ' = 25313 56 71011131381771913 = 109425289274918632559342112641443058962750733001979829025245569500000. This is not the most efficient conceivable coding scheme! EXAMPLE 16.2. The code of the sequence of formulas =00 i.e.0=0 (=OO- SOSO) i.e. 0 = 0 - SO = SO = SOSO i.e. SO = SO works out to 2=00',3r (=00-=3030) '5r=So03-' 22 , 01 5r0-1 ~ § - 32 r 3r =5 0'7r01 lr1 13r-117rs119r0123rs129r0'31r)- - 52r_-=3rs'5r0'7rs11r0' _ 2263757321365777114136178197238297312526385778117 which is large enough not to be worth the bother of working it out explicitly. PROBLEM 16.1. Pick a short sequence of short formulas of 'N and find the code of the sequence. A particular integer n may simultaneously be the Gbdel code of a symbol, a sequence of symbols, and a sequence of sequences of symbols of £N. We shall rely on context to avoid confusion, but, with some more work, one could set things up so that no integer was the code of more than one kind of thing. In any case, we will be most interested in the cases where sequences of symbols are (official) terms or formulas and where sequences of sequences of symbols are sequences of (official) formulas. In these cases things are a little simpler. PROBLEM 16.2. Is there a natural number n which is simultaneously the code of a symbol of 1N, the code of a formula of 1N, and the code of a sequence of formulas of N ? If not, how many of these three things can a natural number be? Recursive operations on G~del codes. We will need to know that various relations and functions which recognize and manipulate Gbdel codes are recursive, and hence computable.  16. CODING FIRST-ORDER LOGIC 115 PROBLEM 16.3. Show that each of the following relations is primi- tive recursive. (1) TERM(n) < n =rt for some term t of IN- (2) FORMULA(n) n = rp for some formula c of EN- (3) SENTENCE(n) n = r7 for some sentence - of EN- (4) LOGICAL(n) < n = ry7 for some logical axiom - of EN- Using these relations as building blocks, we will develop relations and functions to handle deductions of EN. First, though, we need to make "a computable set of formulas" precise. DEFINITION 16.3. A set A of formulas of 'N is said to be recursive if the set of Gbdel codes of formulas of A, A7={ _ f l6o5EA}, is a recursive subset of N (i.e. a recursive 1-place relation). Similarly, A is said to be recursively enumerable if rA7 is recursively enumerable. PROBLEM 16.4. Suppose A is a recursive set of sentences of 'N- Show that each of the following relations is recursive. (1) PREMISSA(n) < n = r/37 for some formula /3 of IN which is either a logical axiom or in A. (2) FORMULAS(n) <---- n = 1... k for some sequence 1-... -pk of formulas of IJN- (3) INFERENCE(n, i, j) <- n =n 1-... - k for some sequence -... ck of formulas of 1N, 1 G ij Gk, and cpk follows from pi and cp by Modus Ponens. (4) DEDUCTIONA(n) <---> = 1... -k for a deduction 1 -...cs from A in 1N- (5) CONCLUSIONA(n, m) <---- n = 1... k for a deduction l...ckfrom AOin IN and m =F k- If rA7 is primitive recursive, which of these are primitive recursive? It is at this point that the connection between computability and completeness begins to appear. THEOREM 16.5. Suppose A is a recursive set of sentences of 'N- Then 7Th(A)7 is (1) recursively enumerable, and (2) recursive if and only if A is complete. NOTE. It follows that if A is not complete, then 7Th(A)7 is an example of a recursively enumerable but not recursive set.   CHAPTER 17 Defining Recursive Functions In Arithmetic The definitions and results in Chapter 17 let us use natural numbers and recursive functions to code and manipulate formulas of EN. We will also need complementary results that let us use terms and formu- las of 'N to represent and manipulate natural numbers and recursive functions. Axioms for basic arithmetic. We will define a set of non-logical axioms in EN which prove enough about the operations of successor, addition, mutliplication, and exponentiation to let us define all the recursive functions using formulas of £N. The non-logical axioms in question essentially guarantee that basic arithmetic works properly. DEFINITION 17.1. Let A be the following set of sentences of 'N, written out in official form. Ni: Vvo (-,= SvoO) N2: Vvo ((-, =vo0) - (,Vi (-,= Svivo))) N3: VoVvi (= SvoSv1 -= vov1) N4: Vvo = +voOvo N5: Vv0Vv1 = +voSv1S + vov1 N6: Vvo = -v000 N7: VoVvi =-voSvi + -vovivo N8: Vvo = Evo0S0 N9: VoVvi =EvoSv1 - Evovivo Translated from the official forms, A consists of the following ax- ioms about the natural numbers: Ni: For all n, n + 1 / 0. N2: For all n, n 0 there is a k such that k + 1 = n. N3: For all n and k, n + 1 = k + 1 implies that n = k. N4: For all n, n + 0 = n. N5: For all nand k, n+ (k+1) =(n+k)+1. N6: For all n, n 0 =0. N7: For all nand k, n -(k+1)= (nk)+n. N8: For all n, no = 1. N9: For all n and k, nk+1 _=(k) . n. 117  118 17. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC Each of the axioms in A is true of the natural numbers: PROPOSITION 17.1. 91= A, where 91 (N,0, S,+, -, E) is the structure consisting of the natural numbers with the usual zero and the usual successor, addition, multiplication, and exponentiation oper- ations. However, A is a long way from being able to prove all the sentences of first-order arithmetic true in 9. For example, though we won't prove it, it turns out that A is not enough to ensure that induction works: that for every formula c with at most the variable x free, if po and Vy (c ox ycs) hold, then so does Vx co. On the other hand, neither 1N nor A are quite as minimal as they might be. For example, with some (considerable) extra effort one could do without E and define it from- and +. Representing functions and relations. For convenience, we will adopt the following conventions. First, we will often abbreviate the term of 'N consisting of m SS followed by 0 by Sm0. For example, S30 abbreviates SSSO. The term Sm0 is a convenient name for the natural number m in the language EN since the interpretation of Sm0 in 9 is m: LEMMA 17.2. For every m E N and every assignment s for 91, s(Sm0) = m. Second, if c is a formula of 'N with all of its free variables among vi, ... ,Vk, and m, i, ..., mk are natural numbers, we will write p (S"0, ... ,Smk0) for the sentence p1s-.kmi.e. p with S"20 sub- stituted for every free occurrence of vi. Since the term Sm20 involves no variables, it is substitutable for v2 in co. DEFINITION 17.2. Suppose E is a set of sentences of EN. A k-place function f is said to be representable in Th(E) = { T |E F T } if there is a formula c of 'N with at most v1, ... , Vk, and Vk+1 as free variables such that f (ni, ... , nk) = m < A(Sn10, ... , Sk0, S") E Th(E) <> EHp(S"10,..., Snk0, S"0) for all ni, ..., nk, and m in N. The formula p is said to represent f in Th(E). We will use this definition mainly with EZ A. EXAMPLE 17.1. The constant function ci given by cs(in) =3 is representable in Th(A); v2 S 33 is a formula representing it. Note  17. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC 119 that that this formula has no free variable for the input of the 1-place function, but then the input is irrelevant... To see that v2 S=S30 really does represent c3 in Th(A), we need to verify that c3(n) = m <-> A H v2 = S3O(S"O, SmO) <-> AH SmO= S3O for all n, m E N. In one direction, suppose that c'3(n) = m. Then, by the definition of c3, we must have m = 3. Now (1) Vxz=x -x S3O S3O A4 (2) Vxx=x A8 (3) S30 = S30 1,2 MP is a deduction of S30 = S30 from A. Hence if c3(n) = m, then A H Smo = S30. In the other direction, suppose that A H Sm0 = S30. Since 91= A, it follows that 1 |= Sm0 = S30. It follows from Lemma 17.2 that m = 3, so c3(n) = m. Hence if A H SmO= S30, then c3(n) = m. PROBLEM 17.3. Show that the projection function r2w can be repre- sented in Th(A). DEFINITION 17.3. A k-place relation P C Nk is said to be repre- sentable in Th(E) if there is a formula @ of EN with at most vi, ..., Vk as free variables such that P(ni, ... , nk) <-> (S"1 0, ... , Snk0) E Th(E) <- EZH @(S"1O,..., Snk0) for all ni, ..., nk in N. The formula @ is said to represent P in Th(E). We will also use this definition mainly with E= A. EXAMPLE 17.2. Almost the same formula, vi = S30, serves to represent the set i.e. 1-place relation {3} in Th(A). Showing that vi = S30 really does represent {3} in Th(A) is virtually identical to the corresponding argument in Example 17.1. PROBLEM 17.4. Explain why v2 = SSSO does not represent the set {3} in Th( A) and v1= SSSO does not represent the constant function ch in Th(A). PROBLEM 17.5. Show that the set of all even numbers can repre- sentable in T h( A).  120 17. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC PROBLEM 17.6. Show that the initial functions are representable in Th(A): (1) The zero function O(n) = 0. (2) The successor function S(n) = n + 1. (3) For every positive k and i < k, the projection function k. It turns out that all recursive functions and relations are repre- sentable in Th(A). PROPOSITION 17.7. A k-place function f is representable in Th(A) if and only if the k + 1-place relation Pf defined by Pf(ni, ... ,nk, nk+1) < f (ni, . --, nk) = k+1 is representable in Th(A). Also, a relation P C Nk is representable in Th(A) if and only if its characteristic function xP is representable in Th(A). PROPOSITION 17.8. Suppose gi, . . , 9m are k-place functions and h is an m-place function, all of them representable in Th(A). Then f = h o (gi,..., gi) is a k-place function representable in Th(A). PROPOSITION 17.9. Suppose g is a k + 1-place regular function which is representable in Th(A). Then the unbounded minimalization of g is a k-place function representable in Th(A). Between them, the above results supply most of what is needed to conclude that all recursive functions and relations on the natural numbers are representable. The exception is showing that functions defined by primitive recursion from representable functions are also representable, which requires some additional effort. The basic problem is that it is not obvious how a formula defining a function can get at previous values of the function. To accomplish this, we will borrow a trick from Chapter 13. PROBLEM 17.10. Show that each of the following relations and func- tions (first defined in Problem 13.5) is representable in Th(A). (1) Div (n, m) <>n | m (2) ISPRIME(n) < n is prime (3) PRIME(k) P=Pk, where po = 1 and pk is the kth prime if k > 1. (4) POWER(n, m) = k, where k;> 0 is maximal such that n1k |I. (5) L ENGT H (n) = 1 where e is maximal such that pg |1n. (6) ELEMENT(n, i) = nj, where nm p ... p k (and nt = 0 if i > k). Using the representable functions and relations given above, we can represent a "history function" of any representable function...  17. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC 121 PROBLEM 17.11. Suppose f is a k-place function representable in Th(A). Show that __f (ml.fk,O) f (mi,.1km) F(ni,... , nk, m) - p.. .,pm,, - 1Jf(ni...,nk,i) i=O is also representable in Th(A). ... and use it! PROPOSITION 17.12. Suppose g is a k-place function and h is a k + 2-place function, both representable in Th(A). Then the k + 1- place function f defined by primitive recursion from g and h is also representable in Th(A). THEOREM 17.13. Recursive functions are representable in Th(A). In particular, it follows that there are formulas of 'N represent- ing each of the functions from Chapter 16 for manipulating the codes of formulas. This will permit us to construct formulas which encode assertions about terms, formulas, and deductions; we will ultimately prove the Incompleteness Theorem by showing there is a formula which codes its own unprovability. Representability. We conclude with some more general facts about represent ability. PROPOSITION 17.14. Suppose E is a set of sentences of 1N and f is a k-place function which is representable in Th(Z). Then E must be consistent. PROBLEM 17.15. If Z is a set of sentences of 'N and P is a k-place relation which is representable in Th(Z), does E have to be consistent? PROPOSITION 17.16. Suppose E and F are consistent sets of sen- tences of 'N and , H F; i.e. Z H y for every 'y E F. Then every function and relation which is representable in Th(F) is representable in Th(E). This lets us use everything we can do with represent ability in Th(A) with any set of axioms in 'N that is at least as powerful as A. COROLLARY 17.17. Functions and relations which representable in T h( A) are also representable in T h(ZL), for any consistent set of sen- tences Z such that Z |- A.   CHAPTER 18 The Incompleteness Theorem The material in Chapter 16 effectively allows us to use recursive functions to manipulate coded formulas of EN, while the material in Chapter 17 allows us to represent recursive functions using formulas 'N. Combining these techniques allows us to use formulas of EN to refer to and manipulate codes of formulas of EN. This is the key to proving Gbdel's Incompleteness Theorem and related results. In particular, we will need to know one further trick about manip- ulating the codes of formulas recursively, that the operation of substi- tuting (the code of) the term Sk0 into (the code of) a formula with one free variable is recursive. PROBLEM 18.1. Show that the function 1(Sk0), if n = y, for a formula c of EN SUB(n, k) = with at most v1 free 0 otherwise is recursive, and hence representable Th(A). In order to combine the the results from Chapter 16 with those from Chapter 17, we will also need to know the following. LEMMA 18.2. A is a recursive set of sentences of EN. The First Incompleteness Theorem. The key result needed to prove the First Incompleteness Theorem (another will follow shortly!) is the following lemma. It asserts, in effect, that for any statement about (the code of) some sentence, there is a sentence o which is true or false exactly when the statement is true or flase of (the code of) o. This fact will allow us to show that the self-referential sentence we will need to verify the Incompleteness theorem exists. LEMMA 18.3 (Fixed-Point Lemma). Suppose c is a formula of EN with only v1 as a free variable. Then there is a sentence o of LN such that A - So0 123  124 18. THE INCOMPLETENESS THEOREM Note that o must be different from the sentence A(30O): there is no way to find a formula c with one free variable and an integer k such that Fp(Sk0)7= k. (Think about how Gbdel codes are defined...) With the Fixed-Point Lemma in hand, Gbdel's First Incompleteness Theorem can be put away in fairly short order. THEOREM 18.4 (Gbdel's First Incompleteness Theorem). Suppose E is a consistent recursive set of sentences of 'N such that E H A. Then E is not complete. That is, any consistent set of sentences which proves at least as much about the natural numbers as A does can't be both complete and recursive. The First Incompleteness Theorem has many variations, corollaries, and relatives, a few of which will be mentioned below. [17] is a good place to learn about more of them. COROLLARY 18.5. (1) Let F be a complete set of sentences of 'N such that F U A is consistent. Then F is not recursive. (2) Let A be a recursive set of sentences such that A U A is con- sistent. Then A is not complete. (3) The theory of 91, Th(9) ={ o|o is a sentence of 1N and 91o u}, is not recursive. There is nothing really special about working in £N. The proof of Gbdel's Incompleteness Theorem can be executed for any first order language and recursive set of axioms which allow one to code and prove enough facts about arithmetic. In particular, it can be done whenever the language and axioms are powerful enough as in Zermelo-Fraenkel set theory, for example to define the natural numbers and prove some modest facts about them. The Second Incompleteness Theorem. Gbdel also proved a strengthened version of the Incompleteness Theorem which asserts that, in particular, a consistent recursive set of sentences E of 'N cannot prove its own consistency. To get at it, we need to express the state- ment "E is consistent" in £N. PROBLEM 18.6. Suppose E is a recursive set of sentences of IN- Find a sentence of IN, which we'll denote by Con(Z), such that E is consistent if and only if A F- Con(Z). THEOREM 18.7 (Gbdel's Second Incompleteness Theorem). Let E be a consistent recursive set of sentences of 'N such that Z H- A. Then EJF Con(E).  18. THE INCOMPLETENESS THEOREM 125 As with the First Incompleteness Theorem, the Second Incomplete- ness Theorem holds for any recursive set of sentences in a first-order language which allow one to code and prove enough facts about arith- metic. The perverse consequence of the Second Incompleteness Theo- rem is that only an inconsistent set of axioms can prove its own con- sistency. Truth and definability. A close relative of the Incompleteness Theorem is the assertion that truth in 91= (N, S, +, -, E, 0) is not definable in 91. To make sense of this, of course, we need to sort out what "truth" and "definable in 91" mean here. "Truth" means what it usually does in first-order logic: all we mean when we say that a sentence u of 'N is true in 91 is that when o is true when interpreted as a statement about the natural numbers with the usual operations. That is, o is true in 91 exactly when 91 satisfies o, i.e. exactly when 9 |. "Definable in 91" we do have to define... DEFINITION 18.1. A k-place relation is definable in 91 if there is a formula c of 'N with at most v1, ..., Vk as free variables such that P(ni,..., nk) <> 1= p[s(vilni)... (Vklnk)] for every assignment s of 91. The formula c is said to define P in 91. A definition of "function definable in 91" could be made in a similar way, of course. Definability is a close relative of representability: PROPOSITION 18.8. Suppose P is a k-place relation which is rep- resentable in Th(A). Then P is definable in 91. PROBLEM 18.9. Is the converse to Proposition 18.8 true? The question of whether truth in 91 is definable is then the question of whether the set of G6del codes of sentences of 'N true in 91, 7Th(9)7= {7Y o- |is a sentence of 'N and 91 is definable in 91. It isn't: THEOREM 18.10 (Tarski's Undefinability Theorem). 7Th(91)7 is not definable in 91. The implications. Gbdel's Incompleteness Theorems have some serious consequences. Since almost all of mathematics can be formalized in first-order logic, the First Incompleteness Theorem implies that there is no effec- tive procedure that will find and prove all theorems. This might be considered as job security for research mathematicians.  126 18. THE INCOMPLETENESS THEOREM The Second Incompleteness Theorem, on the other hand, implies that we can never be completely sure that any reasonable set of axioms is actually consistent unless we take a more powerful set of axioms on faith. It follows that one can never be completely sure faith aside that the theorems proved in mathematics are really true. This might be considered as job security for philosophers of mathematics. We leave the question of who gets job security from Tarski's Unde- finability Theorem to you, gentle reader...  Hints for Chapters 15-18 Hints for Chapter 15. 15.1. Compare Definition 15.2 with the definition of maximal con- sistency. Hints for Chapter 16. 16.1. Do what is done in Example 16.2 for some other sequence of formulas. 16.2. You need to unwind Definitions 16.1 and 16.2, keeping in mind that you are dealing with formulas and sequences of formulas, not just arbitrary sequences of symbolsof 'N or sequences of sequences of symbols. 16.3. In each case, use Definitions 16.1 and 16.2, along with the appropriate definitions from first-order logic and the tools developed in Problems 13.3 and 13.5. (1) Recall that in 'N, a term is either a variable symbol, i.e. Vk for some k, the constant symbol 0, of the form St for some (shorter) term t, or +t1t2 for some (shorter) terms ti and t2. XTERM(n) needs to check the length of the sequence coded by n. If this is of length 1, it will need to check if the symbol coded is 0 or Vk for some k; otherwise, it needs to check if the sequence coded by n begins with an S or +, and then whether the rest of the sequence consists of one or two valid terms. Primitive recursion is likely to be necessary in the latter case if you can't figure out how to do it using the tools from Problems 13.3 and 13.5. (2) This is similar to showing TERM(n) is primitive recursive. Re- call that in £N, a formula is of the form either= tit2 for some terms ti and t2, (/a) for some (shorter) formula a, (3 - y) for some (shorter) formulas 3 and T, or Vv o for some variable symbol v2 and some (shorter) formula b. XFORMULA(n) needs to check the first symbol of the sequence coded by n to identify which case ought to apply and then take it from there. 127  128 HINTS FOR CHAPTERS 15-18 (3) Recall that a sentence is justa formula with no free variable; that is, every occurrence of a variable is in the scope of a quantifier. (4) Each logical axiom is an instance of one of the schema Al-A8, or is a generalization thereof. 16.4. In each case, use Definitions 16.1 and 16.2, together with the appropriate definitions from first-order logic and the tools developed in Problems 13.5 and 16.3. (1) EA7 is recursive and LOGICAL is primitive recursive, so... (2) All XFORMULAS(n) has to do is check that every element of the sequence coded by n is the code of a formula, and FORMULA is already known to be primitive recursive. (3) XINFERENCE(n) needs to check that n is the code of a sequence of formulas, with the additional property that either pj is (cy - (pk) or ps is (pi - Ck). Part of what goes into XFORMULA(n) may be handy for checking the additional property. (4) Recall that a deduction from A is a sequence of formulas 1 ... Ok where each formula is either a premiss or follows from preceding formulas by Modus Ponens. (5) XCONCLUSION(n, m) needs to check that n is the code of a de- duction and that m is the code of the last formula in that deduction. They're all primitive recursive if 7A7 is, by the way. 16.5. (1) Use unbounded minimalization and the relations in Problem 16.4 to define a function which, given n, returns the nth integer which codes an element of Th(A). (2) If A is complete, then for any sentence o, either Fa1 or Io must eventually turn up in an enumeration of 7Th(A)7. The other direction is really just a matter of unwinding the defini- tions involved. Hints for Chapter 17. 17.16. Every deduction from F can be replaced by a deduction of E with the same conclusion. 17.14. If E were insconsistent it would prove entirely too much... 17.6. (1) Adapt Example 17.1. (2) Use the 1-place function symbol S of £N- (3) There is much less to this part than meets the eye...  HINTS FOR CHAPTERS 15-18 129 17.7. In each case, you need to use the given representing formula to define the one you need. 17.8. String together the formulas representing gi, ..., gm, and h with As and put some existential quantifiers in front. 17.9. First show that that < is representable in Th(A) and then exploit this fact. 17.10. (1) n |m if and only if there is some k such that n- k m. (2) n is prime if and only if there is no £ such that |n and 1 < 1. (4) If X is a non-empty finite or countable set, then the set of all finite sequences of elements of X, Xw m= EN X" is count- able. The properly sceptical reader will note that setting up propositional or first-order logic formally requires that we have some set theory in hand, but formalizing set theory itself requires one to have first-order logic.1 1Which came first, the chicken or the egg? Since, biblically speaking, "In the beginning was the Word", maybe we ought to plump for alphabetical order. Which begs the question: In which alphabet?  APPENDIX B The Greek Alphabet A a alpha B # beta F gamma A o delta E E e epsilon Z ( zeta H r/ eta e 0 8 theta I t iota K s kappa A A lambda M p mu N v nu O o omicron E ( xi II r wupi P p o rho E o cSsigma T T tau T v upsilon # So phi X chi & @ psi Q w omega 135   APPENDIX C Logic Limericks Deduction Theorem A Theorem fine is Deduction, For it allows work-reduction: To show "A implies B", Assume A and prove B; Quite often a simpler production. Generalization Theorem When in premiss the variable's bound, To get a "for all" without wound, Generalization. For civilization Could use some help for reasoning sound. Soundness Theorem It's a critical logical creed: Always check that it's safe to proceed. To tell us deductions Are truthful productions, It's the Soundness of logic we need. Completeness Theorem The Completeness of logics is Gbdel's. 'Tis advice for looking for models: They're always existent For statements consistent, Most helpful for logical labors. 137   APPENDIX D GNU Free Documentation License Version 1.2, November 2002 Copyright @2000,2001,2002 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. 0. PREAMBLE The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others. This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software. We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference. 1. APPLICABILITY AND DEFINITIONS This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and 139  140 D. GNU FREE DOCUMENTATION LICENSE is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law. A "Modified Version" of the Document means any work contain- ing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language. A "Secondary Section" is a named appendix or a front-matter sec- tion of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connec- tion with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them. The "Invariant Sections" are certain Secondary Sections whose ti- tles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invari- ant Sections. If the Document does not identify any Invariant Sections then there are none. The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words. A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightfor- wardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage sub- sequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque". Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG.  2. VERBATIM COPYING 141 Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only. The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text. A section "Entitled XYZ" means a named subunit of the Docu- ment whose title either is precisely XYZ or contains XYZ in paren- theses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Ac- knowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this def- inition. The Document may include Warranty Disclaimers next to the no- tice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other im- plication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License. 2. VERBATIM COPYING You may copy and distribute the Document in any medium, ei- ther commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use tech- nical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compen- sation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3. You may also lend copies, under the same conditions stated above, and you may publicly display copies.  142 D. GNU FREE DOCUMENTATION LICENSE 3. COPYING IN QUANTITY If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects. If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages. If you publish or distribute Opaque copies of the Document num- bering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the gen- eral network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reason- ably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessi- ble at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public. It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document. 4. MODIFICATIONS You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you re- lease the Modified Version under precisely this License, with the Modi- fied Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:  4. MODIFICATIONS 143 A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous ver- sions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission. B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement. C. State on the Title page the name of the publisher of the Mod- ified Version, as the publisher. D. Preserve all the copyright notices of the Document. E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices. F. Include, immediately after the copyright notices, a license no- tice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Ad- dendum below. G. Preserve in that license notice the full lists of Invariant Sec- tions and required Cover Texts given in the Document's license notice. H. Include an unaltered copy of this License. I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Docu- ment, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sen- tence. J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for pre- vious versions it was based on. These may be placed in the " History" section. You may omit a network location for a work that was published at least four years before the Document it- self, or if the original publisher of the version it refers to gives permission. K. For any section Entitled "Acknowledgements" or "Dedications" Preserve the Title of the section, and preserve in the section  144 D. GNU FREE DOCUMENTATION LICENSE all the substance and tone of each of the contributor acknowl- edgements and/or dedications given therein. L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equiv- alent are not considered part of the section titles. M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version. N. Do not retitle any existing section to be Entitled "Endorse- ments" or to conflict in title with any Invariant Section. 0. Preserve any Warranty Disclaimers. If the Modified Version includes new front-matter sections or appen- dices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles. You may add a section Entitled "Endorsements", provided it con- tains nothing but endorsements of your Modified Version by various parties-for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard. You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one. The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version. 5. COMBINING DOCUMENTS You may combine the Document with other documents released un- der this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invari- ant Sections of all of the original documents, unmodified, and list them  7. AGGREGATION WITH INDEPENDENT WORKS 145 all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers. The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work. In the combination, you must combine any sections Entitled "His- tory" in the various original documents, forming one section Enti- tled "History"; likewise combine any sections Entitled "Acknowledge- ments", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements." 6. COLLECTIONS OF DOCUMENTS You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects. You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document. 7. AGGREGATION WITH INDEPENDENT WORKS A compilation of the Document or its derivatives with other sep- arate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copy- right resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document. If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on cov- ers that bracket the Document within the aggregate, or the electronic  146 D. GNU FREE DOCUMENTATION LICENSE equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate. 8. TRANSLATION Translation is considered a kind of modification, so you may dis- tribute translations of the Document under the terms of section 4. Re- placing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warrany Disclaimers, provided that you also include the original English version of this Li- cense and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail. If a section in the Document is Entitled "Acknowledgements", "Ded- ications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title. 9. TERMINATION You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 10. FUTURE REVISIONS OF THIS LICENSE The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new ver- sions will be similar in spirit to the present version, but may differ in de- tail to address new problems or concerns. See http://www.gnu.org/copyleft/. Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.  Bibliography [1] Jon Barwise (ed.), Handbook of Mathematical Logic, North Holland, Amster- dam, 1977, ISBN 0-7204-2285-X. [2] J. Barwise and J. Etchemendy, Language, Proof and Logic, Seven Bridges Press, New York, 2000, ISBN 1-889119-08-3. [3] Merrie Bergman, James Moor, and Jack Nelson, The Logic Book, Random House, NY, 1980, ISBN 0-394-32323-8. [4] C.C. Chang and H.J. Keisler, Model Theory, third ed., North Holland, Ams- terdam, 1990. [5] Martin Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958; Dover, New York, 1982, ISBN 0-486-61471-9. [6] Martin Davis (ed.), The Undecidable; Basic Papers On Undecidable Propo- sitions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. [7] Herbert B. Enderton, A Mathematical Introduction to Logic, Academic Press, New York, 1972. [8] Paul R. Halmos, Naive Set Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1974, ISBN 0-387-90092-6. [9] Jean van Heijenoort, From Frege to Gddel, Harvard University Press, Cam- bridge, 1967, ISBN 0-674-32449-8. [10] James M. Henle, An Outline of Set Theory, Problem Books in Mathematics, Springer-Verlag, New York, 1986, ISBN 0-387-96368-5. [11] Douglas R. Hofstadter, Gddel, Escher, Bach, Random House, New York, 1979, ISBN 0-394-74502-7. [12] Jerome Malitz, Introduction to Mathematical Logic, Springer-Verlag, New York, 1979, ISBN 0-387-90346-1. [13] Yu.I. Manin, A Course in Mathematical Logic, Graduate Texts in Mathemat- ics 53, Springer-Verlag, New York, 1977, ISBN 0-387-90243-0. [14] Roger Penrose, The Emperor's New Mind, Oxford University Press, Oxford, 1989. [15] Roger Penrose, Shadows of the Mind, Oxford University Press, Oxford, 1994, ISBN 0 09 958211 2. [16] T. Rado, On non-computable functions, Bell System Tech. J. 41 (1962), 877- 884. [17] Raymond M. Smullyan, Gddel's Incompleteness Theorems, Oxford University Press, Oxford, 1992, ISBN 0-19-504672-2. 147   Index (, 3, 24 ), 3, 24 =,24, 25 0, 89, 133 U, 89, 133 ] , 30 V, 24, 25, 30 <, 5, 30 E, 133 A, 5, 30, 89 -P, 89 -%3, 24, 25, 89 V, 5, 30, 89 _10, 35, 37, 38 X, 10, 36, 37 HJ, 133 H-, 12, 43 \, 133 C, 133 x, 133 ->, 3, 24, 25 A, 117 Al, 11, 42 A2, 11, 42 A3, 11, 42 A4, 42 AS, 42 A6, 42 A7, 42 A8, 43 An , 3 Con(s), 124 r- -1 115 dom(f), 81 F, 7 f : Nk - N, 81 p ,42 4C 24 ,C1, 26 ,C=, 26 ,CF, 26 IC, 53 ,CN, 26, 112 ,Co1 26 ,CS, 26 £NT, 25 9i1, 33 N, 81, 134 J t, 33, 112 Ni, 117 N2, 117 N3, 117 N4, 117 N5, 117 N6, 117 N7, 117 N8, 117 N9, 117 lk , 81 lk \ P, 89 2, 133 PonQ, 89 P UQ, 89 P AQ, 89 P VQ, 89 Irk, 85, 120 Q, 134 IR, 134 ran(f), 81 Rn, 55 S,16 149  150 INDEX Sm0, 118 T,7 Th, 39, 45 Th(E), 112 Th(91), 124 Vn, 24 X, 133 [X]k, 133 Y, 133 A, 90 a, 90 CODEk, 97, 106 COMP, 98 COMPM, 96 CONCLUSIONA, 115 DECODE, 97, 106 DEDUCTIONA, 115 DIFF, 83, 88 Div, 90, 120 ELEMENT, 90, 120 ENTRY, 96 EQUAL, 89 Exp, 88 FACT, 88 FORMULAS, 115 FORMULA, 115 1N, 82 INFERENCE, 115 ISPRIME, 90, 120 LENGTH, 90, 120 LOGICAL, 115 MULT, 88 0, 83, 85, 120 POWER, 90, 120 PRED, 83, 88 PREMISSA, 115 PRIME, 90, 120 SIM, 106, 107 SENTENCE, 115 SIM, 98 SIMM, 97 STEP, 97, 106 STEPM, 96, 106 SUBSEQ, 90 SUB, 123 SUM, 83, 87 5, 83, 85, 120 TAPEPOSSEQ, 96, 106 TAPEPOS, 96, 105 TERM, 115 abbreviations, 5, 30 Ackerman's Function, 90 all, x alphabet, 75 and, x, 5 assignment, 7, 34, 35 extended, 35 truth, 7 atomic formulas, 3, 27 axiom, 11, 28, 39 for basic arithmetic, 117 Ni, 117 N2, 117 N3, 117 N4, 117 N5, 117 N6, 117 N7, 117 N8, 117 N9, 117 logical, 43 schema, 11, 42 Al, 11, 42 A2, 11, 42 A3, 11, 42 A4, 42 AS, 42 A6, 42 A7, 42 A8, 43 blank cell, 67 blank tape, 67 bound variable, 29 bounded minimalization, 92 busy beaver competition, 83 n-state entry, 83 score in, 83 cell, 67 blank, 67 marked, 67 scanned, 68 characteristic function, 82 chicken, 134 Church's Thesis, xi  INDEX 151 clique, 55 code G6del, 113 of sequences, 113 of symbols of EN, 113 of a sequence of tape positions, 96 of a tape position, 95 of a Turing machine, 97 Compactness Theorem, 16, 51 applications of, 53 complement, 133 complete set of sentences, 112 completeness, 112 Completeness Theorem, 16, 50, 137 composition, 85 computable function, 82 set of formulas, 115 computation, 71 partial, 71 connectives, 3, 4, 24 consistent, 15, 47 maximally, 15, 48 constant, 24, 25, 31, 33, 35 constant function, 85 contradiction, 9, 38 convention common symbols, 25 parentheses, 5, 30 countable, 134 crash, 70, 78 cross product, 133 decision problem, x deduction, 12, 43 Deduction Theorem, 13, 44, 137 definable function, 125 relation, 125 domain (of a function), 81 edge, 54 egg, 134 element, 133 elementary equivalence, 56 Entscheidungsproblem, x, 111 equality, 24, 25 equivalence elementary, 56 existential quantifier, 30 extension of a language, 30 finite, 134 first-order language for number theory, 112 languages, 23 logic, x, 23 Fixed-Point Lemma, 123 for all, 25 formula, 3, 27 atomic, 3, 27 unique readability, 6, 32 free variable, 29 function, 24, 31, 33, 35 k-place, 24, 25, 81 bounded minimalization of, 92 composition of, 85 computable, 82 constant, 85 definable in 9t, 125 domain of, 81 identity, 82 initial, 85 partial, 81 primitive recursion of, 87 primitive recursive, 88 projection, 85 recursive, x, 92 regular, 92 successor, 85 Turing computable, 82 unbounded minimalization of, 91 zero, 85 G6del code of sequences, 113 of symbols of EN, 113 G6del Incompleteness Theorem, 111 First Incompleteness Theorem, 124 Second Incompleteness Theorem, 124 generalization, 42 Generalization Theorem, 45, 137 On Constants, 45 gothic characters, 33 graph, 54 Greek characters. 3. 28. 135 halt, 70, 78  152 INDEX Halting Problem, 98 head, 67 multiple, 75 separate, 75 identity function, 82 if ... then, x, 3, 25 if and only if, 5 implies, 10, 38 Incompleteness Theorem, 111 G6del's First, 124 G6del's Second, 124 inconsistent, 15, 47 independent set, 55 inference rule, 11 infinite, 134 Infinite Ramsey's Theorem, 55 infinitesimal, 57 initial function, 85 input tape, 71 intersection, 133 isomorphism of structures, 55 John, 134 k-place function, 81 k-place relation, 81 language, 26, 31 extension of, 30 first-order, 23 first-order number theory, 112 formal, ix natural, ix propositional, 3 limericks, 137 logic first-order, x, 23 mathematical, ix natural deductive, ix predicate, 3 propositional, x, 3 sentential, 3 logical axiom, 43 machine, 69 Turing, xi, 67, 69 marked cell, 67 mathematical logic, ix maximally consistent, 15, 48 metalanguage, 31 metatheorem, 31 minimalization bounded, 92 unbounded, 91 model, 37 Modus Ponens, 11, 43 MP, 11, 43 natural deductive logic, ix natural numbers, 81 non-standard model, 55, 57 of the real numbers, 57 not, x, 3, 25 n-state Turing machine, 69 entry in busy beaver competition, 83 number theory first-order language for, 112 or, x, 5 output tape, 71 parentheses, 3, 24 conventions, 5, 30 doing without, 4 partial computation, 71 function, 81 position tape, 68 power set, 133 predicate, 24, 25 predicate logic, 3 premiss, 12, 43 primitive recursion, 87 primitive recursive function, 88 recursive relation, 89 projection function, 85 proof, 12, 43 propositional logic, x, 3 proves, 12, 43 punctuation, 3, 25 quantifier existential, 30 scope of, 30 universal, 24, 25, 30  INDEX 153 Ramsey number, 55 Ramsey's Theorem, 55 Infinite, 55 range of a function, 81 r.e., 99 recursion primitive, 87 recursive function, 92 functions, xi relation, 93 set of formulas, 115 recursively enumerable, 99 set of formulas, 115 regular function, 92 relation, 24, 31, 33 binary, 25, 134 characteristic function of, 82 definable in 9, 125 k-place, 24, 25, 81, 133 primitive recursive, 89 recursive, 93 Turing computable, 93 represent (in Th(E)) a function, 118 a relation, 119 representable (in Th(E)) function, 118 relation, 119 rule of inference, 11, 43 satisfiable, 9, 37 satisfies, 9, 36, 37 scanned cell, 68 scanner, 67, 75 scope of a quantifier, 30 score in busy beaver competition, 83 sentence, 29 sentential logic, 3 sequence of tape positions code of, 96 set theory, 133 Soundness Theorem, 15, 47, 137 state, 68, 69 structure, 33 subformula, 6, 29 subgraph, 54 subset, 133 substitutable, 41 substitution, 41 successor function, 85 tape position, 71 symbols, 3, 24 logical, 24 non-logical, 24 table of a Turing machine, 70 tape, 67 blank, 67 higher-dimensional, 75 input, 71 multiple, 75 output, 71 tape position, 68 code of, 95 code of a sequence of, 96 successor, 71 two-way infinite, 75, 78 Tarski's Undefinability Theorem, 125 tautology, 9, 38 term, 26, 31, 35 theorem, 31 theory, 39, 45 of 9W, 124 of a set of sentences, 112 there is, x TM, 69 true in a structure, 37 truth assignment, 7 in a structure, 36, 37 table, 8, 9 values, 7 Turing computable function, 82 relation, 93 Turing machine, xi, 67, 69 code of, 97 crash, 70 halt, 70 n-state, 69 table for, 70 universal, 95, 97 two-way infinite tape, 75, 78 unary notation, 82  154 INDEX unbounded minimalization, 91 uncountable, 134 Undefinability Theorem, Tarski's, 125 union, 133 unique readability of formulas, 6, 32 of terms, 32 Unique Readability Theorem, 6, 32 universal quantifier, 30 Turing machine, 95, 97 universe (of a structure), 33 UTM, 95 variable, 24, 31, 34, 35 bound, 29 free, 29 vertex, 54 witnesses, 48 Word, 134 zero function, 85