COMPUTABILITY An introduction to recursive function theory NIGEL CUTLAND Department of Pure Mathematics, University of Hull Wesnsiovlé KO PASABLLOTERA peosnad 12%" CAMBRIDGE UNIVERSITY PRESS Cambridge London New York New Rochelle Melbourne SydneyPublished by the Press Syndicate of the University of Cambridge ‘The Pitt Building, Trumpington Street, Cambridge CB IRP 32 East Sith Street, New York, NY 10022, USA 10 Stamford Road, Oakleigh, Melbourne 3166, Australia © Cambridge University Press 1980 First published 1980 Reprinted 1983, 1988 Printed in Great Britain at The Pitman Press, Bath Library of Congress Cataloguing in Publication Data Cutkand, Niget Computability: an introduction to veursve function theory, Bibliography: Includes index. |. Computable functions. 2. Recursion theory. 1. Tite OA.59.C87 519.4 79.31825 ISBN 0 S21 22384 9 hard covers ISBN 0 521 20465 7 paperbackContents Preface Prologue. Prerequisites and notation 1 Sets 2 Funetions 3 Relations and predicates 4 Logical notation 5 References ‘Computable functions 1 Algorithms, or effective procedures 2 The unlimited register machine 3 URM-computable functions 4 Decidable predicates and problems 5 Computability on other domains Generating computable functions 1 The base functions 2 Joining programs together 3 Substitution 4 Recursion 5 Mini Other approaches to computability: Church’s thesis 1 Other approaches to computability 2 Partial recursive functions (Gédel-Kleene) 3.A digression: the primitive recursive functions 4 Turing-computabilty 5. Symbol manipulation systems of Post and Markov 6 Computability on domains other than N 7 Church's thesis Numbering computable functions 1 Numbering programs 2 Numbering computable functions 3 Discussion: the diagonal method 4 The sm-n theorem10 u 2 Contenss Universal programs 1 Universal functions and universal programs 2 Two applications of the universal program 3 Effective operations on computable functions Appendix. Computability of the function o, Decidabitity, undecidability and partial decidability 1 Undecidable problems in computability 2 The word problem for groups 43 Diophantine equations 4 Sturm’s algorithm 5 Mathematical logic 6 Partially decidable predicates Recursive and recursively enumerable sets 1 Recursive sets 2 Recursively enumerable sets 43 Productive and creative sets 4 Simple sets Arithmetic and Gadel’ incompleteness theorem 1 Formal arithmetic 2 Incompleteness 3 Gode's incompleteness theorem 4 Undecidability Reduciility and degrees 1 Many-one reducibilty 2 Degrees 3 m-complete re. sets 4 Relative computability 5 Turing reducibility and Turing degrees Effective operations on partial functions 1 Recursive operators 2 Effective operations on computable functions 3 The first Recursion theorem 4 An application to the semantics of programming languages ‘The second Recursion theorem 1 The second Recursion theorem 2 Discussion 3. Myhill’s theorem Complexity of computation 1 Complexity and complexity measures 2 The Speed-up theorem 3 Complexity classes 4 The elementary functions 85 8s 90 93 9s 100 101 106 107 los 109 12 ia 121 123 133 140 143 143 146 149 155 17 158 161 Los 167 18 182 182 189 192 196 200, 200 207 210 212 213, 218 223 2253 Contents Further study Bibliography Index of notation Subject Index 236 239 2a 246Preface ‘The emergence of the concept of a computable function over fifty years ago marked the birth of a new branch of mathematics: its importance may bbe judged from the fact that it has had applications and implications in fields as diverse as computer science, philosophy and the foundations of ‘mathematics, as well as in many other areas of mathematics itself. This book is designed to be an introduction to the basic ideas and results of computability theory (or recursian theory, as it is traditionally known ‘among mathematicians) The initial purpose of computability theory is to make precise the intuitive idea of a computable function; that is, a function whose values can be calculated in some kind of automatic or effective way. Thereby we can gain a clearer understanding of this intuitive idea; and only thereby ‘can we begin to explore in a mathematical way the concept of compu- tability as well as the many related ideas such as decidability and effective enumerability. A rich theory then arises, having both positive and negative aspects (here we are thinking of non-computability and undeci- dability results), which it is the aim of this book to introduce. We could describe computability theory, from the viewpoint of computer science, as beginning with the question What can computers do in principle (without restrictions of space, time or money)? —and, by implication ~ What are their inherent theoretical limitations? Thus this book is not about real computers and their hardware, nor is it about programming languages and techniques. Nevertheless, our subject matter is part of the theoretical background to the real world of computers and their use, and should be of interest to the computing. community. For the basic definition of computability we have used the ‘idealised computer’ or register machine approach; we have found that this is readily grasped by students, most of whom are aware of the idea of a computer. (We do not, however, assume such an awareness (although it is helpful)Preface ix and even less do we assume any practical experience with computers or calculators.) Our approach is mathematically equivalent to the many others that have been discovered, including Turing machines, the favourite of many. (We discuss these equivalences in chapter 3.) ‘This text grew out of a course given to undergraduates in mathematics and computer science at the University of Hull. The reader envisaged is a mathematics student with no prior knowledge of this subject, or a student of computer science who may wish to supplement his practical expertise with something of the theoretical background to his subject. We have aimed at the second or third year undergraduate level, although the cearlier chapters covering the basic theory (chapters 1-7) should be within the grasp of good students in sixth forms, high schools and colleges (and their teachers). The only prerequisites are knowledge of the mathemati- cal language of sets and functions (reviewed in the Prologue) and the ability to follow a line of mathematical reasoning. ‘The later chapters (8-12) are largely independent of each other. Thus @ short introductory course could consist of chapters 1-7 supplemented by selection according to taste from chapters 8-12. It has been our aim in these later chapters to provide an introduction to some of the ramifications and applications of basic computability theory, and thereby provide a stepping stone towards more advanced study. To this end, the final chapter contains a brief survey of possible directions for further study, and some suggestions for further reading. (The two main texts that might be regarded as natural sequels to this one are M. L. Minsky, Computation: Finite and Infinite Machines, which would complement the present volume by its broad and comprehensive study of computation (as ‘opposed to computability), and H. Rogers, Theory of Recursive Functions and Effective Computability, which provides a more advanced treatment of recursion theory in depth.) Many people have helped towards the writing of this book. I would first thank John Cleave, who taught me recursive function theory in a gradu- ate course at the University of Bristol in 1966, and introduced me to the register machine approach that I have used here. I have greatly appreci- ated the sustained interest and encouragement from Stan Wainer (who also made valuable suggestions for the material in chapters 10 and 12) and David Jordan: I thank them. I would also like to thank David Jordan and Dick Epstein for reading a draft of the manuscript and making many valuable comments and corrections. I am grateful to the Cambridge University Press for their interest and advice which has resulted in the emergence of the completed manuscript.Preface x Finally, a big thank you to my wife Mary for her patience and ‘encouragement during the many phases of writing and preparation of this book; her idealism and understanding have been a sustaining influence throughout.Prologue Prerequisites and notation ‘The only prerequisite to be able to read this book is familiarity with the basic notations of sets and functions, and the basic ideas of mathematical reasoning. Here we shall review these matters, and explain the notation. and terminology that we shall use. This is mostly standard; so for the reader who prefers to move straight to chapter 1 and refer back to this prologue only as necessary, we point out that we shall use the word function to mean a partial function in general. We discuss this more fully below. 1 Sets Generally we shall use capital letters A, B, C, ... to denote sets. We write x€ A to mean that x is a member of A, and we write x@ A to mean that x is not a member of A. The notation {x:....r...} where x. is some statement involving x means the set of all objects x for which ....x. is true. Thus {x: x is an even natural number} is the set {0,2,4,6,...} If A, B are sets, we write A < B to mean that A is contained in B (or A isa subser of B); we use the notation A < B tomean that Ac B but A # B (ie. A is a proper subset of B). The union of the sets A, B is the set {x: xe A or xB (or both)}, and is denoted by A WB; the intersection of A,B is the set {x:xeA and x€B} and is denoted by AnB. The difference (ot relative complement) of the sets A, B is the set (x: ¢ A. and x# B} and is denoted by A\B. The empty set is denoted by @. We use the standard symbol Ni to denote the set of natural numbers {0, 1, 2,3,...).If A is a set of natural numbers (Le. A GN) we write A to denote the complement of A relative to N, ie. N\A. We write N° for the set of positive natural numbers {1,2,3,,..}, and as usual Z denotes the set of integers.Prologue 2 We write (x) to denote the ordered pair of elements x and y; thus (x, y) *(y, x) in general. If A, B are sets, the Cartesian product of A and B is the set {(x, y):x€ A and y €B), and is denoted by Ax B. More generally, for elements ris...,Xq We Write (xi, ... 4%) t0 denote the ordered n-tuple of x1,..., Xe; an n-tuple is often represented by a single boldfaced symbol such as x. If Ai,...,A, are sets we write AiX...%Ay for the set of n-tuples (Gi,...5%):x1€Ar and xe ‘Ag. sty €Ag) The product AXA. 2A (nr times) is abbreviated by A"; Al means A. Funetions We assume familiarity with the basic idea of a function, and the distinction between a function f and a particular value f(x) at any given x where fis defined.” If fis a function, the domain of fis the set (x: f(x) is defined}, and is denoted Dom(/); we say that f(x) is undefined if xeDom(f). The set {f(x): xe Dom(f)} is called the range of f, and is denoted by Ran(f)-IfA and B are sets we say that fis function from A to B if Dom(/)= A and Ran(/)< B. We use the notation f: A> B to mean that fis a function from A to B with Dom(f)= A A function fis said to be injective if whenever x, y ¢ Domi f) and x # yy then f(x) fi) If Fis injective, then f-" denotes the inverse off, i. the unique function g such that Dom(g)=Ran(f) and g(f(x)) =x for xe Dom(/). A function f from A to B is surjective if Ran(f)= B. If f: A= B, we say that fis an injection (from A to B)ifitis injective, anda surjection (from A to B)ifit is surjective. Iisa bijection if itis both fan injection and a surjection, Suppose that fis a function and X is a set. The restriction of f to X, denoted by f|X, isthe function with domain X -Dom(f) whose value for xX mDomif) is f(x). We write /(X) for Ran(/|X). If ¥ isa set, then the inverse image of ¥ under fis the set f-"(¥)=4x: /(x)e ¥}. (Note that this is defined even when f is not injective.) If fg are functions, we say that g exiends f if Domi) Dom(g) and fle) = g(x) for all xeDom(f): in short, f= g|Dom(f). This is written fs "Usually in mathematical texts «function fis defined to be ast of ordered pairs sueh thatif (x y)€f and (x, 2)€f, then y = 2, and fe is defined tobe this y We {donot insist on this definition of function, but our exposition seonsistent with2 Functions 3 “The composition of two functions f,¢ is the function whose domain is, the set {x:xDom(g) and g(x)eDom({)}, and whose value is f¢g(x)) when defined. This function is denoted fe. We denote by fa the function that is defined nowhere; ie. fo has the property that Dom(fo)=Ran(fa)=@. Clearly fe=g|@ for any function ¢ Often in computability we shall encounter functions, or expressions involving functions, that are not always defined. In such situations the following notation is very useful. Suppose that a(x) and f(x) are expres- sions involving the variables x = (x1,..%9)- Then we write a(x)=B(x) to mean that for any x, the expressions a(x) and B(x) are either both defined, or both undefined, and if defined they are equal. Thus, for example, iff, ¢ are functions, writing f(x) = g(x) is another way of saying that f= g} and for any number y, f(x) = y means that f(x) is defined and flx)=y [since y is always defined). Functions of natural numbers For most of this book we shall be concerned with functions of natural numbers; that is, functions from N" to N for various n, most commonly 1 = 1 or 2. ‘A function f from N” to Nis called an n-ary function, The value of f at fan n-tuple (Xi, .-)%.)€Dom(f) is written flea, -.-5%_) OF fla), if x represents (13, .., %q)- In some texts the phrase partial function is used to describe a function from N" to N whose domain is not necessarily the whole of N’. For us the word function means partial function. On. occasion we will, nevertheless, write partial function to emphasise this fact, A total function from N" to Nisa function whose domains the whole of N". Particularly with number theoretic functions, we shall blur the dis- tinction between a function and its particular values in two fairly standard and unambiguous ways. First we shall allow a phrase such as ‘Let ‘fle.,...,) be a function...” as a means of indicating that f is an n-ary function. Second, we shall often describe a function in terms of its general value when this is given by a formula. For instance, “the function x”* means “the unary function f whose value at any xeN is x”; similarly, ‘the function x+y’ is the binary function whose value at (x, y)eN? is x+y, ‘We describe the zero function N+ Nby 0; and generally, for me N, we denote the function N>N whose value is always m by the boldface symbol m.Prologue 4 3. Relations and predicates If A isa set, a property M(xi,...%) that holds (or is true) for some n-tuples from A" and does not hold (or is false) forall other n-tuples from A is called an n-ary relation or predicate on A.* For example, the property x denotes implies, and ¢> Ry OF y= 0) Successor Sin) Add 1 t0 Fe (r,t 1-2Roy oF =r, + y ‘Transfer Thm.) Replace r, by rm (Pq * Res 01 = fn) Jump Hom m4) Tf r= rs ump tothe ath instruction; otherwise go on to the next instruc~ tion in the program. instruction, say J(m, m, q),is encountered, In this case the URM proceeds to the instruction prescribed by J(m, n, q) and the current contents of the registers R,, and R,. We illustrate this with an example, 21, Example Consider the following program: hh J0,2,6) hb SQ) b 8) Le J0,2,6) Js 31,2) Js T3,1) Let us consider the computation by the URM under this program with initial configuration RR: Rs Re Rs 9]7]ololo (We are not concerned at the moment about what function this program ‘actually computes; we wish to illustrate the way in which the URM ‘operates programs in a purely mechanical fashion without needing to understand the algorithm that is being carried out.) ‘We can represent the progress of the computation by writing down the successive configurations that occur, together with the next instruction to be obeyed at the completion of each stage.2 The unlimited register machine 13 RR: Ry Re Rs Next instruction Initia confe-[ 9 [7 [o]o]o h bration 9[7]elelo I. Gince #7) o[s]o]ole b o[sjifofo] «4 9[sl|tjolo 1 Gince #7) 9/sjijolo fs (since 1 and so on. (We shall continue this computation later.) We can describe the operation of the URM under a program P + J: in general as follows. The URM starts by obeying instruc tion [,. At any future stage in the computation, suppose that the URM is obeying instruction f. Then having done so it proceeds to the next instruction in the computation, defined as follows: if, is not a jump instruction, the mext instruction is Ik: Ty itm evs otherwise, where fay Fs are the current contents of Ry and Ry The URM proceeds thus as long as possible; the computation siops when, and only when, there is no next instruction; i.e. if the URM has just obeyed instruction J, and the ‘next instruction in the computation’ according to the above definition is f, where v > s. This can happen in the following ways: (i) if k= (the last instruction in P has been obeyed) and J, isan arithmetic instruction, Gi) if Le =I, m4), fa =e ad gS, Gil) if Le = Som, mq), Fn Pa and R=. We say then that the computation stops after instruction J4; the final configuration is the sequence ry, r2,r4,... , the contents of the registers at this stage, Hnen)the netinscion |1 Computable functions 14 Let us now continue the computation begun in example 2.1. Example 2.1 (continued) R, Ry Re Rs Next instruction [i b 9]°]1]°J]o 5 9[2[2[o][o L 9[9]2[o]o Ie (since Final 7 confe-[ 2] 9 [2] 0] 0 Ip sror. tration This computation stops as indicated because there is no seventh instruction in the program. 2.2. Exercise Carry out the computation under the program of example 2.1 with initial configuration 8, 4, 2,0, 0, ‘The essence of a program and the progress of computations under itis often conveniently described informally using @ flow diagram. For ‘example, alow diagram representing the program of example 2.1 is given in fig. 16. (We have indicated alongside the flow diagram the typical configuration of the registers at various stages in a computation.) Note the convention that tests or questions (corresponding to jump instructions) are placed in diamond shaped boxes. ‘The translation of this flow diagram into the program of exercise 2.1 is almost self-explanatory. Notice that the backwards jump on answer ‘No’ to the second question ‘7.=r2?" is achieved by the fifth instruction JL, 1, 2) which is an unconditional jump: we always have r= 11, $0 this instruction causes a jump to J; whenever it is encountered. When writing @ program to perform a given procedure it is often helpful to write an informal flow diagram as an intermediate step: the translation of a flow diagram into a program is then usually routine.2 The unlimited register machine 15 Fig. 16. Flow diagram for the program of example 2.1. “Typical configuration RR Ry 7D? ‘After k cycles round the loop in thisprogram x pee Many tk: Pn erie ‘There are, of course, computations that never stop: for example, no computation under the simple program S(1), J(J, 1, 1) ever stops. Computation under this program is represented by the flow diagram in fig, Le. The jump instruction invariably causes the URM to return, or loop back, to the instruction S(1). ‘There are more sophisticated ways in which a computation may run for ever, but always this is caused essentially by the above kind of repetition ‘or looping back in the execution of the program.1 Computable functions 16 Fig. le 23 Exercise Show that the computation under the program of example 2.1 with initial configuration 2, 3, 0,0, 0, .. never stops. The question of deciding whether a particular computation eventually stops or not is one to which we will return later. ‘Some notation will help us now in our discussion. Let ay, a2, as,... be an infinite sequence from N and let P be a program; we will write {) Plai,a3,ds,...) for the computation under P with initial configuration @, 2, dsy...5 (ii) Play,a2,as,-..)] to mean that the computation Play, az,dy,-..) eventually stops; (iii) P(ai,a2,a3,...)f to mean that the computation Pla, a2, as,...) never stops. In most initial configurations that we shall consider, all but finitely many of the 4, will be 0, Thus the following notation is useful. Let 4, day. be & finite sequence of natural numbers; we write liv) Pai, a2, a) for the computation PCa a3, yn 040505. )y Hence (9) Plas,a3,...444)4 means that Play, a2... 0,0,0,---)bs (i) Plaisaay--vds)f means that P(as,d2,-+-+ 4m 0,0,0,..-)t Often a computation that stops is said to converge, and one that never stops is said to diverge. 3. URM-computable functions Suppose that fis @ function from N" to Ny (n= 1); what does it mean to say that fis computable by the URM? It is natural to think in terms of computing a value f(as,..-, dq) by means of a program P on initial configuration ay, @3,..-,4m0,0,.... That is, we consider computations of the form P(a), @2,..., aq). If any such computation3 URM-computable functions 7 stops, we need to have a single number that we can regard asthe output or result of the computation; we make the convention that this isthe number 1: finally contained in R,. The final contents ofthe other registers can be regarded as rough work or jottings, that can be ignored once we have the desired result in Ry Since a computation P(ar,...,a,) may not stop, we can allow our definition of computability to apply to functions f from N° to N whose domain may not be all of N"; ie. partial functions. We shall require that the relevant computations stop (and give the correct result! precisely for inputs from the domain off. Thus we make the following definitions. 3.1 Definitions Let f be a partial function from N* to N. (a) Suppose that P is a program, and let a1, a2,..., day BEN. (i) The computation Play,as,...4dx) converges 10 6 if Plas, @2y..-,d,)) and in the final configuration 8 is in Ry. We write this Pay... , an)bB; (i) P- URM-computes if, for every aiges-sdmb Play... @)bb if and only if (a:,...4a,)€Dom(f) and Alar, -+4,)= 6. (In particular, this means that P(ay,..., dq)bif and only if (@is-+.5 ,)¢ Dom(/).) () The function f is URM-compurable if there is a program that URM-computes f. ‘The class of URM-computable functions is denoted by , and n-ary URM-computable functions by €. From now on we will use the term computable to mean URM-computable, except in chapter 3 where other notions of computability are discussed. ‘We now consider some easy examples of computable functions. 3.2 Examples (a) x+y. We obtain x+y by adding 1 to x (using the successor instruction) y times. A program to compute x+y must begin on initial configuration 4,9,0,0,0,...5 our program will keep adding 1 tor, using Ry as a counter to keep a record of how many times ris thus increased. A typical configuration during the computation is RR: Rs Ry Rs ek [>[* [ele1 Computable functions 18 ‘The program will be designed to stop when k required. ‘The procedure we wish to embody in our program is represented by the flow diagram in fig. 1d. A program that achieves this is the following: 1, 13,2,5) <- hh Sil) BSG) te SQ) (The dotted arrow, which is nor part of the program, is to indicate to the reader that the final instruction has the effect of always jumping back to the first instruction.) Note that the sro has been achieved by a jump instruction to ‘Zs’ which does not exist. Thus, x + y is computable. leaving x+y in Ry as 1d, Flow diagram for addition (example 3.2(a)). keke Gent), ) oe fe 1 itx>0, 0 ifx=0. (Since we are restricting ourselves to functions from Nto N, this is the best approximation to the function x~1.) ‘We will write a program embodying the following procedure. Given initial configuration x, 0,0,0,...., first check whether x =O; if so, stop; otherwise, run two counters, containing k and k +1, starting with k A typical configuration during a computation will be R, RRs Rs x | & [e+]3 URM-computable functions 19 Check whether x = k+ 1;ifso, the required result isk otherwise increase both counters by 1, and check again, ‘A flow diagram representing this procedure is given in fig. le. A program that carries out this procedure isthe following. h 14,9) be SQ) i 10,3, — 1, 8Q) ' 1 SB) ! Je 31,1,3) ~~ Eh 12,1) ‘Thus the funetion x ~ 1 is computable. Fig. 1e, Flow diagram for x~ 1 (example 3.2(6)). stant “Typical configuration RR: Ry x[oe1 Computable functions 20 _ pie it iseven, f fa\= undefined if x is odd. In this example, Dom(/)=E (the even natural numbers) so we must ‘ensure that our program does not stop on odd inputs. ‘A procedure for computing f(x) is as follows. Run two counters, containing k and 2k for k=0,1,2,3,...; for successive values of k, check whether x = 2k; if o, the answer is k; otherwise increase k by one, and repeat. If x is odd, this procedure will clearly continue for ever. ‘The typical configuration will be RR: Ry Re x | 2%] kl o with k = Oinitially. A flow diagram for the above process is given in fig. If Fig. If. Flow diagram for example 3.2(c). kek, (eR) Or3 URM-computable functions a A program that executes itis h 30,2,6) Is SQ) 1 SQ) Ie S02) fs 30,1,1) Is T3,1) Hence fis computable. ‘Note. The programs in these examples are in no sense the only programs that will compute the functions in question. Given any program P (i.e. any finite list of instructions), and n = 1, by thinking of the effect of P on initial configurations of the form 4, 2,5 dy, 0, 0,-.. We See that there isa unique n-ary function that P ‘computes, denoted by fs’. From the definition it is clear that the unique b such that Play,...,ax)1b, Play. dy)=y if PCAs. adds undefined, if Pay, as)f Ina later chapter we shall consider the problem of determining f#” for any given program P. Its clear that a particular computable function can be computed by ‘many different programs; for instance, any program can be altered by adding instructions that have no effect. Less trivially, there may be ditferentinformal methods for calculating a particular function, and when formalised as programs these would give different programs for the same function. In terms of the notation we have introduced, we can have different programs P; and Ps, with ff) = ff for some (or all)n. Later we shall consider the problem of deciding whether or not two programs compute the same functions. 3.3 Exercises 1. Show that the following functions are computable by devising programs that will compute them. won tee () fo)=5; (© fay={) oe1 Computable functions 2 0 itxs 1 ifx>ys _ {he if. isa multiple of 3, (0 fe) [apdetnedtherse: (A) x)= [2x/3]. (z] denotes the greatest integer =). 2. Let P be the program in example 2.1. What is /9°? 3. Suppose that P is a program without any jump instructions. Show that there is a number m such that either @) flyy)= Pads forall x, B(x)=xtm, forall x. 4. Show that for each transfer instruction T(m, m) there is a pro- gram without any transfer instructions that has exactly the same effect as T(m,n) on any configuration of the URM. (Thus transfer instructions are really redundant in the formulation of ‘our URM; it is nevertheless natural and convenient to have transfer as a basic facility of the URM.) 4, Decidable predicates and problems In mathematics a common task is to decide whether numbers possess a given property. For instance, the task described in (1.1) (d) isto decide, given numbers x, y, whether they have the property that x is a multiple of y. An algorithm for this operation would be an effective procedure that on inputs x, y gives output Yes or No. If we adopt the convention that 1 means Yes, and 0 means No, then the operation amounts to calculation of the function 1 if isa multiple of y, fey) 0 if x isnot. multiple of y. ‘Thus we can say that the property or predicate “x is a multiple of y’ is algorithmically or effectively decidable, or just decidable if this function f is computable. Generally, suppose that M(xi,x3....5%) is an r-ary predicate of natural numbers. The characteristic function cy(x) (setting x= Ges, -- 5 tm) is given by 1 if M(x) holds, (0 if M(x) doesn't hold.4. 5 Computability on other domains 23, 1 Definition ‘The predicate M(x) is decidable if the function ey is compu- table; M(x) is undecidable if M(x) is not decidable. 4s 2 Examples The following predicates are decidable: (a) “x #,": the funetion f of exercise 3.3 (1c) is the characteristic function of this predicate. (b) “x= 0": the characteristic function is given by 1 ifx=0, semfo tere ‘The following simple program computes ¢ 301,23) 3(,1,4) SQ) Te,1) (c) ‘x is a multiple of y': itis possible to write a program for the characteristic function, but this would be somewhat lengthy and complicated. A simpler demonstration that this predicate is decidable will emerge from the next chapter, where techniques for generating more complex computable functions are developed. Note that when discussing decidability (or undecidability) we are always concerned with the computability (or non-computability) of toval functions. In the context of decidability, properties or predicates are sometimes described as problems. Thus we might say that the problem ‘x # "is decidable. In chapter 6 we will study undecidable problems. 4 s 3 Exercise ‘Show that the following predicates are decidable. (a) x Nis given by 1 ifx=0(e.x=a(0), ix)=4x-2 ifx>Oand xiseven (ie.x=aln),n>0), x42. ifxisodd. (i.e. x= a(n), <0), Iisa routine exercise to write a program that computes /*; hence x ~1is a computable function on Z. The definitions of computable n-ary function on a domain D and decidable predicate on D are obtained by the obvious extension of the above idea. 52 Exercises 1, Show that the function 2x on Z is computable. 2. Show that the predicate ‘x = 0’ is a decidable predicate on Z.2 Generating computable functions In this chapter we shall see that various methods of combining compu- table functions give rise to other computable functions. This will enable us to show quite rapidly that many commonly occurring functions are computable, without writing a program each time ~a task that would be rather laborious and te: 1, The basic functions First we note that some particularly simple functions are computable; from these basic functions (defined in lemma 1.1 below) we shall then build more complicated computable functions using the tech- niques developed in subsequent sections. 1. Lemma The following basic functions are computa (a) the zero function 0(0(x)=0 for all x); (b) the successor function x +1; (c) foreach n=1 and 11, the projection function U? given By U2 (xy, Xa, Xa) =H Proof. These functions correspond to the arithmetic instructions for the URM. Specifically, programs are as follows: (a) 0: program Z(1); (b) x+1: program S(1); (©) UP: program Ti, 1). 0 2. Joining programs together In each of §§3-5 below we need to write programs that incorporate other programs as subprograms or subroutines. In this section we deal with some technical matters so as to make the program writing of later sections as straightforward as possible.2 Generating computable functions 26 A simple example of program building is when we have programs P and Q, and we wish to write a program for the composite procedure: first do P, and then do Q. Our instinct is to simply write down the instructions in P followed by the instructions in Q. But there are two technical points to consider. Suppose that P=), 2,...,1, A computation under P is completed when the ‘next instruction for the computation’ is I, for some v >s; we then require the computation under our composite program to proceed to the first instruction of Q. This will happen automatically if » = s +1, but not otherwise. Thus for building composite programs we must confine our attention to programs that invariably stop because the next instruction is Z,s1.Such programs are said to be in standard form. Clearly itis only jump. instructions that can cause a program to stop in non-standard fashion. ‘Thus we have the following definition. 24. Definition A program P=, Iz,...,1, i in standard form if, for every jump instruction J(m, n, q) in P we have q=s +1. Examples. In examples 1-3.2 the programs for (a) and (c) are in standard form, whereas the program in (6) is not, Insisting on standard form if necessary is no restriction, as we now see, 22. Lemma For any program P there is @ program P* in standard form such that any computation under P* is identical to the corresponding compu tation under P, except possibly inthe manner of stopping. In particular, for amy a, ---5 Aus by Plar,-4q)4bifand only if P*(ay,.-. ax), and hence ff) =[# for every n>0. Proof. Suppose that P= Ii, 12...» To obtain P* from P simply change the jump instructions so that all jump stops occur because the jump isto fs. Explicitly, put PY =f, ,..., 17 where if his not a jump instruction, then It = Les Ie qestl, Im, ns+1) ifq>s+l. ith w is mentioned in P; ic. if Z(n), or S(n), or Tm, 2), or 3m, q) is an instruction in P, then m,n =u, Clearly, during any computation under P, the contents of R, for » > remain unaltered, and have no effect on the values of rj,...,r Thus when writing our new Program Q the registers R, for v > u can be used, for example, to store information without affecting any computation under the subroutine P. We denote the number u by p(P). Finally, we introduce some notation that will greatly simplify the main Proofs of this chapter. Suppose that is a program in standard form designed to compute a function fxs,..., x). Often when using P as @2 Generating computable functions 28 subroutine in a larger program the inputs x1,...,%_ for which fey, - 4%) is desired may be held in registers Ry,.... Ri, rather than R,,...,Ry as the program P requires; further, the output f(ti, +, %») may be required for future purposes to be in some register R, rather than the conventional R,; and finally the working registers Ri, ..., Raw for P may contain all kinds of unwanted information. We can modify P to take account of all of these points as follows. We write P{h, ....n>{]for the program in fig. 2a that translates the flow diagram alongside. The program P[lh,..., l,->/] has the effect of computing fir,» r,) and placing the result in Ry. Moreover, the only registers aflected by this program are (at most) Rs, Ra, ..., Ruins and Ry (We have assumed in defining P[li.....ln1] that Riy.e.6Ri, ate distinct from Rj,...,Re; this will be the case in all our uses of this notation. The reader should be able to modify the definition for situations ‘where this is not the case.) Fig. 2a. Flow diagram for PCI, + “Trams fom cme Rig RG 1 RyoeeesRy aa = Zine) Gen Bisa ina { I ZK?) fla) Ry (using P) » nok TLD +3 Substitution 29 3. Substitution A common way of manufacturing new functions from old is to substitute functions into other functions, otherwise known as composi- tion of functions. In the following theorem we show that when this process is applied to computable functions, the resulting functions are also computable. In short, we say that € is closed under the operation of substitution. 3.1. Theorem Suppose that fiyss.+++y) and gi(x),.-+5 gelx) are compuiable functions, where x= (x15... 5%). Then the function h(x) given by h(x) = f(gila), «+ gule)) is computable. (Note. h(x) is defined if and only if gi(x),..., x(x) are all defined and (gi(x),-+-,Re(8))}eDom(f); thus, if f and gi,.--,Re are all total functions, then h is total.) Proof. Suppose that F,G1,...,Gy are programs in standard form which compute f, gs, & Fespectively, We will write a program H that embodies the following natural procedure for computing h. "Given 2 use the programs Gi,...,Gi to compute in succession Bilt), 2(8),---,x(), making @ note of these values as they are obtained. Then use the program F to compute f(gi(x),..., se(#)).” We must take a little care to avoid losing information needed at later stages in the procedure, namely x and those values gi(x) already obtained. Putting m = maxi, k, pF), e(Gi),.- p(Gx)), we shall begin by storing x in Rsis..+,Rmens the registers Rmensis +++Rmence Will be used to store the values g(x) as they are computed for f= 1,2,..., ke ‘These registers are completely ignored by computations under F, Gr...» Ge A typical configuration during computation under H will Storage registers i _. Ri--eRe Revie -Raen Rasa Reva? ++ Raeest = x als) | e209] -.-[ a fo | 0 An informal flow diagram for computing /t is given in fig. 26. This is easily translated into the following program H that computes /2 Generating computable functions 30 T,m +1) Tin, m+n) Gilm+1,m+2.....m+n2mtn+1] (Recall the meaning of this notation from Gilm+1,m42,....menomentk] 9?) Flmtn+t,...smtntk=1] Fig. 26. Substitution (theorem 3.1). Migs). 6028,3 Substitution a1 Clearly a computation (x) will stop if and only if each computation G(x) stops (11k) and the computation F(gi(x),..., gx(x)) stops, which is exactly as required. "New functions can be obtained from any given function by rearranging or identifying its variables, or by adding new dummy variables; for instance, from a function f(y, y2) we can obtain Iy(xi x2) =flva,x:) (rearrangement), fax) =f x) (identification), hiss ¥2,23)= fla, 5) (adding dummy variables). ‘The following application of theorem 3.1 shows that any of these opera- tions (or a combination of them) transforms computable functions into computable functions. 3.2. Theorem Suppose that flys,..-.y«) ts a computable function and that Ny Xun ++Xy 8 Sequence of k ofthe variables xs,...,%q (possibly with repetitions). Then the function h given by Bleep tn) Slt ees a) is compuiable. Proof. Writing x= (x1,--., 4) we have that (x)= (UI), Ula), URE) which is computable, by Lemma 1.1(c) and theorem 3.1. Using this result we can see that theorem 3.1 also holds when the functions g:,..., ge Substituted into f are not necessarily funetions of all of the variables x1, x» as in the following example. 33. Brample ‘The function f(x, x2, x3) = 44 +x2+.x is computable; this can be deduced from the fact that x+y is computable (example 1-3.2(a), by Substituting x; +2 for x, and x3 for y in x-+y.2 Generating computable functions 32 Substitution combined with the principle described in the next section gives a powerful method of generating computable functions. 34. Exercises 1, Without writing any programs, show that for every mN the following functions are computable: (a) m (recall that m(x) =m, for all x), (b) mx. 2. Suppose that f(x, y) is computable, and m€N. Show that the function (x)= flx, m) is computable. 3, Suppose that g(x) is a total computable function. Show that the predicate M(x, y) given by M(x, y)="e0)=y" is decidable. 4. Recursion Recursion isa method of defining a function by specifying each of its values in terms of previously defined values, and possibly using other already defined functions. To be precise, suppose that f(x) and g(x, y, 2) are functions (not necessarily total or computable). Consider the following ‘definition’ of a new funetion A(x, y) (4.1) AG, O)=fle), Gi) h(a, y +1) glx, y, AO») At first sight this may seem a little dubious as a definition, for in the second line it appears that his being defined in terms of itself ~a circular definition! However, with alittle thought we can convince ourselves that this is a valid definition: to find the value of h(x, 3) for instance, first find ‘ix, 0) using (4.1)(); then, knowing h(x, 0), use (4.1)(i) to obtain h(x, 1); similarly, obtain h(x,2), and finally h(x; 3) by further applications of (4.1)(i). Thus, circularity is avoided by thinking of the values of h(x, y) as being defined one at a time, always in terms of a value already obtained.4 Recursion 33. ‘A function h defined thus is said to be defined by recursion from the functions f and g; the equations 4.1 are known as recursion equations. Unless both f and g are total, then ht as defined by (4.1) may not be total; the domain of h will satisfy the conditions (x,0)eDom(h) iff reDomi(f), (wy+t)eDom(h) iff (x, y)eDom(h) and (x, y, A(x, y))¢Dom(g). Let us summarise the above discussion in a theorem, whose proof we omit, 4.2. Theorem Let x= (xiy.+.5%0) and suppose that fix) and g(x,y, 2) are ‘functions; then there is a unique function hx, y) satisfying the recursion ‘equations h(x, 0)=fl), Ax y +1) ale», hs y)), Note. When n=0 (ic. the parameters x do not appear) the recursion equations take the form (0) =a, Ay +1) =a, A), where aN, 43. Examples (a) Addition: for any x, y we have x+0=x, xt tDaletyeh ‘Thus addition (ie. the function h(x, y)=x-+) is defined by recursion from the functions f(x) =x and g(x, y,2)=2 +1. (0) yl: with the convention that 0!= 1, we have that ‘Thus the function y! is defined by recursion from 1 and the function 8,2) 2+). ‘There are forms of definition by recursion that are more general than the one we have discussed; we shall encounter an example of this in § 5, and a fuller discussion of this topic is included in chapter 10. In contexts,2 Generating computable functions 34 where general kinds of recursion are being considered, the particularly simple kind of definition given by (4.1) i called primiaive recursion Many commonly occurring functions have easy definitions by (primi- tive) recursion, so for establishing computability the next theorem is ‘extremely useful. Briefly, it shows that © is closed under definition by recursion 44. Theorem Suppose that f(x) and g(x, v, 2) are computable functions, where X= (iyeeeytq)s then the function h(x, y) obtained from f and g by recursion is computable, Proof. Let F and G be programs in standard form which compute the functions f(x) and g(x, y, 2). We will devise a program H for the function ‘h(x, y) given by the recursion equations 4.1. Given an initial configura- tion x1,...5%m90,0,0... HE will first compute f(x, 0) (using F); then, if y#0, H will use G to compute successively (x, 1), h(x, 2), .+4 464, y), and then stop, Let_m=max(n +2, p(F),p(G)); we begin by storing x,y in Ruety +s Rmsanti the next two registers will be used to store the current value of the numbers k and h(x, k) for k=0,1,2,...,y. Writing ¢ for ‘m+n, a typical configuration during the procedure will thus be Storage registers Ri iRy Reo Re Rot Ris ° ose * y | & [awe with k = 0 initially, ‘An informal flow diagram for the procedure is given in fig. 2c. This flow diagram translates easily into the following program H that computes h: TU,m+1) Tin+1,mtn+i) FUL 2,-0.4 143) Ty We+2,¢+1,p) Glm+1,..,m+n,t+2,1+396+3] S(e+2) Jd, 1,4) i, Te+3,1) Hence h is computable.4 Recursion 35 Fig. 2c. Recursion (theorem 4.4) Store Ay IMR Ries (k= initia) a= his.) Rios (At this stage the configration is ()) isk) R (ersR) BUA) Rey (eho, 40) ‘We now proceed to use theorems 3.1 and 4.4 to compile a collection of ‘computable functions. The collection is potentially infinite, so our choice is influenced by (i) the needs of subsequent development of our theory, and (ii) the desire to give eredence to the thesis that all functions that we would regard as computable in the informal sense are indeed URM- computable. For reasons which will become apparent later we shall include some functions such as x +y and x~ 1 for which we have already written programs. We shall use repeatedly the fact that,by theorem 3.2, in a definition by recursion such as (4.1), the computable functions f and g need not be functions of all of the named variables for the function h to be computable.2 Generating computable functions 36 45. Theorem The following functions are computable. (Proofs are given as the functions are listed.) (a) x+y Proof. Example 4.3(a) gives a definition by recursion from the computable functions x and z +1. (6) xy Proof. x0=0, ay+Daay ta, is a definition by recursion from the computable functions O(x) and z+. (©) x” Proof. x°=1, x77" = yx; by recursion and (). (a) x+1 Proof. 0+1=0, (e+1)=1=x; by recursion, soy ifxey, 0 otherwise. Proof. x+0=% y+ 1)= (x+y) 15 by recursion and (d). (cut-off subtraction) satay {PEO (te eneries1-3.3014) Proof. sg(0)=0, sex +1) |; by recursion. wa 1 ifx=0, (8) SB) = 0 ifx¥0. (cf. example 1-4.2(6)) Proof. $3(x)=1~sg(x); by substitution, (e) and (f). Gi |x-yl Proof. e-yl=@=y)+Q=2); by substitution, (a) and (e) (i) x! Proof. Example 4.3(b) gives a definition by recursion from computable functions (x, y)= minimum of x and y. Proof. min(x, y)=x~(x~y); by substitution. (k) max(x, y)= maximum of x and y. Proof. max(x, y)=x+(y~x);_ by substitution. () 1m(x, y)= remainder when y is divided by x (to obtain a total function, we adopt the convention rm(0, y)=¥). Pioof Me have: rm(x, y)+1 isms, y)+1ex, mms ytD= hg itrm(s, y)+1 =x. This gives the following definition by recursion: r(x, 0)=0, r(x, y+1)= (rm(x, y)-+1) sg(lx —(rm(x, y)+1))). a4 Recursion 37 The second equation can be written smix, y+1)= glx, rm(x, y)) where g(x,2)=(2+1)sg(lx—(2 +); and gis computable by several applications of substitution. Hence rm(x, y) is computable. (m) atx, y) = quotient when y is divided by x (to obtain a total function we define qt(0, y)= 0). Proof. Since ats, y) +1 ifrm(x, y)+1=2, atx, y) ——ifrmlx, y) +1 4x, wwe have the following definition by recursion from computable functions atx, 0)=0, Ax, y +1) = atx, y) +5RUlx —Com(x, y)+ 1). 1 ifsly (divides y), 0 ifedy. (We adopt the convention that 0|0 but 0 y if y 40.) Hence x|y is decidable (recall definition 14.1). Proof. div(x, y) = §§(rm(x, y)), computable by substi- tution. O ata. y+D={ (a) div(x,y)= The following are useful corollaries involving decidable predicates. 46. Corollary (Definition by cases) Suppose tht f(s). J) are total computable functions and Mile)... Mule) are decidable predicates, such that for every x exactly one of My(x),.-., M(x) holds. Then the function g(x) given by filx) if Mi(x) holds, ny 30) MEL hos, (file) if M(x) holds, is computable Proof. g(x) = ene(x)flx)+...+¢xg(*) fel), computable by substitu- tion using addition and multiplication. DO 4.7. Corollary (Algebra of decidability) ‘Suppose that M(x) and Q(x) are decidable predicates; then the following aie also decidable. (@) ‘nor M(x)"2 Generating computable functions 38 (b) ‘M(x) and Qa) (©) ‘M(s) or Oy" Proof. The characteristic functions of these predicates are as follows: (a) ‘not M(x)": 1+ ex(), (6) *M(x) and Q(3) exr(x) cola). (c) *M(x) oF Q(x): max(eye(x), colt) (where we take ‘or’ in the inclusive sense), Each of the functions on the right is computable provided cx and co are, by substitution in functions from theorem 4.5. Recursion can be used to establish the computability of functions obtained by other function building techniques, which we now describe. First, we introduce some notation. Suppose that f(x, z) is any function; the bounded sum J... flx,z) and the bounded product J]. <, f(x, 2) are the functions of x, y given by the following recursion equations. fix, z)=0, O98 1d fenz=¥ flaz+fiey, Ti fy2)=1, (4.9) = TL fos2)=(I1 fla) fom) 4.10. Theorem Suppose that ftx,2) is a total computable function; then the functions ¥,<, f(x, 2) and [],<, fix, 2) are computable. Proof. The equations 4.8 and 4.9 are definitions by recursion from computable functions, Cl It is easily seen that if the bound on z in a bounded sum or product is given by any computable function, the result is still computable, as follows. 4.11, Corollary Suppose that f(x, ) and k(x, w) are total computable functions; then so are the functions ¥serigw) fl 2) and Tecra fl 2) (both functions of x, ).4 Recursion 39 Proof. By substitution of k(x, w) for y in the bounded sum, fla, 2) and the bounded product []z<, fla, z). We now describe another useful function building technique which yields computable functions. We write z 1 and the only divisors of x 0 otherwise =5R(D(x)—2)). Fete (©) Po=0, Peat =uz 5(pi!+1)(e>p, and 2 is prime), Which isa definition by recursion; the predicate “2 > y and z is prime’ is decidable, so using corollary 4.14 (and the note follow- ing) we have a computable function. (d) (x), = 42 0, there are unique expressions for x in the forms (2) x= 42%, .42", with O=b)0, Ma) +{ 0 otherwise; asin (2), ifx>Oand 1sisl, wior-{ 0 otherwise; in (3), ifx>Oand1 sist, alix ani show that each of the functions a, |, 6, @ is computable. (The expression (3) is a way of regarding x as coding the sequence (2, a2,..., a) of numbers, and willbe used in chapter 5.) Minimalisation In the previous section we have scen that a large collection of functions can be shown to be computable using the operations of substi tution and recursion, and operations derived from these. There is a third important operation which generates further computable functions, namely unbounded minimalisation, or just minimalisation, which we now describe. Suppose that fl, y) is function (not necessarily total) and we wish to define a function g(x) by glx) = the least y such that f(x, y)=0,5 Minimatisation 43 in such a way thatif fis computable then so is g. Two probiems can arise. First, for some x there may not be any y such that fis, y)=0. Second, assuming that / is computable, consider the following natural algorithm for computing g(x). ‘Compute f(x, 0), f(x, 1)... until y 1sfound such that f(x, y)= 0°. This procedure may not terminate if fis not total, even if such 2 y exists; for instance, if f(x, 0) is undefined but fix, 1) ‘Thus we are led to the following definition of the mnimalsation ‘operator jz, which yields computable functions from computable functions. 5.1, Definition For any function f(x, ») the least y such that (i) fla, 2)isdefined, allz = y, and wilen-O= (ii) flx.y)=0, ifsucha y exists, undefined, if there is no such y. wy(.-.) is read ‘the least y such that ...". This operator is sometimes called simply the 4-operator. ‘The next theorem shows that ¢ is closed under minimalisation. 52. Theorem Suppose’ that f(x, y) is computable; then so is the function g(x) = Hy(Fle y) = 0). Proof. Suppose that x=(x},...,%,) and that F is a program in stan- dard form that computes the function f(x, y). Let m =max(n +1, a(F)). We write a program G that embodies the natural algorithm for g: for K=0,1,2..., compute f(x, k) until a value of k is found such that flx, k)= 0; this value of & is the required output. . ‘The value of x and the current value of k will be stored in registers Ryeiy +s Rmsnst before computing f(x, k): thus the typical configura- tion will be Storage registers ee »s [éefo Ries Ra Roo with k = 0 initially. Note that ry-ns2 is always 0.2 Generating computable functions 44 ‘A flow diagram that carries out the above procedure for g is given in fig. 2d. This translates easily into the following program G for g: T(L,m+1) Tin, m+n) I, Flm+1,m4+2,....m+n+1o1) J, m+n+2,q) Sm+n+1) Jd, 1,p) I, Tom+n+4,1) , is the first instruction of the subroutine Fm +1,m+2,...>1]) Fig. 2d. Minimalisation (theorem 5.2) tk =initiaty) flr. k)+Ry keke k=R,5 Minimalisation 45 5.3. Corollary Suppose that R(x, y) is a decidable predicate; then the function gtx) =ay Rix, y) _ {te least y such that R(x, y) holds, if there is such ay, ~ (undefined otherwise, is computable Proof. g(x: y Gents, y))=0). O In view of this corollary, the w-operator is often called a search operator. Given a decidable predicate R(x, y) the function g(x) searches for a y such that R(x, y) holds, and moreover, finds the least such y if there is one. ‘The w-operator may generate a non-total computable fun total computable function; for instance, putting f(x, y)=|x—y*|, and g(x)~uy(fl, y) = 0), we have that g is the non-total function ve if.x isa perfect square, Bix) = lundefined otherwise ‘Thus, in a trivial sense, using the u-operator together with substitution and recursion, we can generate from the basic functions more functions than can be obtained using only substitution and recursion (since these ‘operations always yield total functions {rom total functions). There are also, however, soial functions for which the use of the 4-operator is essential. Example 5.5 below gives one such function; we present another ‘example in chapter 5. Thus we see that, ina strong sense, minimalisation, unlike bounded minimalisation, cannot be defined in terms of substitu- tion and recursion. It turns out, nevertheless, that most commonly ‘occurring computable total functions can be built up from the basic functions using substitution and recursion only: such functions are called Primitive recursive, and are discussed further in chapter 3 § 3. In practice, of course, we might establish the computability of these functions by what Amounts to a non-essential use of minimalisation, if this makes the task easier. 54. Exercises 1. Suppose that f(x) is a total injective computable function; prove that fis computable. 2. Suppose that p(x) isa polynomial with integer coefficients; show that the function2 Generating computable functions 46 fla)=least non-negative integral root of plx)—alaeN) is computable (f(a) is undefined if there is no such root). 3. Show that the function aly ify #0 and y|x, fin y)= undefined otherwise, is computable We conclude this chapter with an example of a function that makes essential use of the 4-operator; it also shows how this operator can be used not only to search for a single number possessing a given property, but to search for finite sequences or sets of numbers, or other objects coded by a single number. The function is a modification by Péter of an example due to Ackermann, after whom it is named. It is rather more complicated than any function we have considered so far. 5.5. Example (The Ackermann function) ‘The function W(x, y) given by the following equations is computable: YO, y)=y+1, Y(e+1, Ox, VD, Wr, y+ Dawe, Wat yD ‘This definition involves a kind of double recursion that is stronger than the primitive recursion discussed in § 3. To see, nevertheless, that these equations do unambiguously define a function, notice that any value ‘U(x, y) (x > 0) is defined in terms of ‘earlier’ values (x, ys) with xy Sx? -y)Ss where S; and S; are arbitrary strings. ‘A more general manipulation of a string, yet still regarded by Post as elementary, takes the form (5.2) goSieiSz--. 8m1SmBm > hoSihtSihta «+ Silin where B05--+5 Bim fos» fy are fixed strings (and may be null), ii) the subscripts #1,..., iq are all from 1,2,...,m, and need not be distinct.5 Systems of Post and Markov 59 Post called an operation of the form (5.2) a production; it may be applied to any string that can be analysed as, = BOT BTD- + Tbm (iyo Tm ae strings), to produce the string hoo hues. hy 5.3. Example Let 3 ={a, 6}; consider the production (m) aSibSz > S2aSpa. Then the effect of () on some strings is given in the table @ Strings produced by (x) aba ‘aaaa abba aaa and baba ba) does not apply. (The entries in the second line correspond to the two possible analyses of abba | ,aAbba atiba as OSE and 54. Exercise Examine the ways in which the production S\bS,aaSsb > SyabS, applies to the string babaabbaab. Productions form the main ingredient of Post's canonical systems: 5.5. Definition A Post-(canonical) system @ consists of (a) a finite alphabet 5, (6) a finite subset A of E*, the axioms of (c) a finite set Q of productions of the form (5.2), whose fixed strings are in 5° ‘We say that is a Post-system over 5. We write & S + if the string r can be obtained from the string o by a finite succession of applications of productions in Q; then we writes + if there is an axiom o €A such that o =r. In this case we say that 7 is generated by the Post-system; the set of all strings in * generated by is denoted Ts, ie. Tam {oe 3*:i o}3 Other approaches to computability 60 ‘The set Ts is also called the set of theorems of , reflecting the motivation of Post. 5.6. Example Let $ be the Post-system with alphabet ¥ ={a, b}, axioms A, a,b and productions § > aSa and $+ bSb. Then Ty is the set of palindromes ~ the strings reading the same in either direction, such as aba, bbabb, abba. Sometimes, in order to generate a particular set of strings in 2* it is necessary to use auxiliary symbols in the generation process. This leads to the following definition: 5.7. Definition Let ¥ be an alphabet and let X <3". Then X is Post-generable if, there isan alphabet Z; 2 ¥ anda Post-system over 5; such that X is the set of strings in X* that are generated by % ie. X = Ty 3*. Post proved a remarkable theorem showing that really only very simple productions are needed to generate Post-generable sets. A set of produc- tions Q (and any system in which they occur) is said to be normal if all the productions have the form gS » Sh. Post proved 5.8. Theorem (Post’s normal form theorem) Any Post-generable ser can be generated by a normal system. For an excellent proof consult Minsky [1967], Post-systems having only productions of the kind SigSs > SihSz tive models of grammars and languages. They reflect the way in which complex sentences of a language are built up from certain basic units according to the rules of grammar, Restrictions on the nature of g and h provide the context-sensitive and context-free languages of Chomsky, which provide useful models of languages used in computer program- ming. We cannot pursue this interesting topic here: the reader may consult the books of Arbib [1969] and Manna [1974] for further information.5 Systems of Post and Markov 6 5.9. Post-systems and other approaches ro computability ‘As we have seen, Post-systems give a characterisation of the notion of an effectively generated set. We may compare this with the corresponding notion that emerges from the other approaches to compu- tability. For URM-computability (or Turing-computability, ete.) effectively generated sets of numbers are called recursively enumerable (.e.); these are the sets that are the range of some URM-computable function. (We shall study r.e. sets in chapter 7.) To compare sets of strings with sets of numbers, we choose an (intui- tively) effective coding function”: * +N under which the string o = 2* is coded by the number @. A convenient method for an alphabet ¥= la ay} is by the k-adic coding where *: 3*>Nis defined by 4 = 0; igreeGrg = tot nk+...+rk™ It is easily seen that * is actually @ bijection, so if the inverse of “is denoted by ”: N->* we also have a representation of each number n by a string Suppose now that X is a set of strings: let X ={d: « € X}, the set of numbers coding X, We have the equivalence result: 5.10. Theorem X is Post-generable iff X is re. Proof. We sketch one proof of this result. Let X ¢ * and suppose first that X is re, Let X = Rani), where fis URM-computable. Using earlier ‘equivalences we can design a Turing machine M whose symbols include the alphabet ©, so that when in state q: and given initial tape J o 1]i 1fa <—— m1 —— M halts if and only if m ¢ Dom(), and does so in the following configura- tion au t T Lea ive. the symbols on the non-blank part of the tape indicated constitute the string f(m) from 5, and M is in a special halting state qu scanning the square marked J. Now devise a Post-system 9 to simulate the behaviour of M on its tape; the alphabet of % will include ¥ and the symbols and3 Other approaches to computability 62 states of M; 9 will generate strings of the form SiS BS Sin to represent any situation Su |S that occurs during the computation by M from an initial tape of the form. (), To get things going, @ will generate all strings of the form quill”... 11, which represent such initial tapes. If we include in # the production qy.S + S, then the strings from 3* generated by @ will be the set _ {fllm): me Dom(f)}=(: m€ Rant f)} ={ii: ne XI =X. Thus X = Ty.03*, so X is Post generable Conversely, if X is Post-generable by a Post-system , show that the relation “fis generated by @ using at most m productions” is decidable; from the theory of rc. sets (chapter 7) it follows easily that X S.LL. Post-computabitity We now explain two ways to derive a concept of computable function from Post-systems.In both cases the concept is defined first for functions on ¥*, and then extended to N by coding or representation. ‘Suppose that f: 3*-> 2* is a partial function. Select a symbol - not in ¥ and consider the set of strings G(N={o- flo): ¢€Dom(f} from the alphabet U{-}. The set G(f) contains all information about f, and we define: 5.12. Definition f: ">" is Post-compuiable it G() is Post-generable, 5.13. Example } and consider the function f: 2*—E* given by fd... 1)=1111...1011.5 Systems of Post and Markov 63 ‘The set G(/) is generated by the following Post-system: Alphabet {1, +} A-fA)) Production $; * Sz $1 + $,S,8:1. ‘The single production of this system applies to a string of the form MWe. Me1d.. 11 eons os Axiom to produce the string 1c 9AIL, TNL AMM ge ent on ren Hence f is Post-computable. Suppose that G(/) is generated by a Post-system @ To see that f is computable in the informal sense, consider the following algorithm for finding f(e) (where «€ 3*). ‘Generate the strings Ts in some systematic fashion; examine these as, they appear, looking for a string of the form a «r with re*. Such a string will eventually be produced if, and only if, « € Dom(), and then r=flo). ‘The definition (5.12) extends in an obvious way to partial functions (2*)" > 5, Post-computability on {is then defined using any effective representation “:N->5* in the natural way: 5.14. Definition Let g:N" +N be a partial function, and let &:(3*)" + 5* be the function defined by ht thay Hig) = BM Ml) (Ima, «sy END, ‘Then g is Post-computable if g is Post-computable. If we let 6 denote the class of Post-computable functions of natural numbers, we have the equivalence: 5.18. Theorem P€=€=FE=A. (We omit a proof. When the reader has studied chapters 6 and 7 he should be able to see that this follows from theorem 5.10 and the results of chapters 6 and 7 linking r.e. sets with URM-computable functions.)3 Other approaches to computability 64 {An alternative way to derive a notion of computability from Post- systems is to simulate computations by a machine directly. This can be done by using sets of productions such that ar moss one production in Q can apply to any given string. Such sets, and the systems in which they ‘occur, are called monogenic. A monogenic system operates sequentially like a machine, It is convenient for the following to write @ S| r to mean that oS + but no production in Q applies to +. We have the following characterisation of Post-computability. $16 Theorem Let f:3*->E* bea partial function, and let X, ¥ be symbols notin E. Then the following are equivalent (a) fis Post-compuiable: (6) there is a monogenic set of productions Q over an alphabet 323 U(X, ¥} such that fora e3* and ret Xo Sirti eDom(f) and + isthe string ¥f(@). (Note. The symbols X and Y are needed to distinguish ‘input’ strings from ‘output’ strings. Otherwise a desired output string f() would be regarded as a new input string to which further productions might apply.) Proof. The implication (a)=>(b) may be obtained by first showing that f is computable by a Turing machine M, and then devising @ ‘monogenic set of productions to simulate M. In fact itis possible to obtain a normal monogenic set of productions for this task. For (5) > (a) it is quite straightforward to show that the function f:N-+N coding f is partial recursive, then apply theorem 5.18. 1 ‘This equivalence extends to functions f:(2*)"+5* by considering inputs’ of the form Xoy+o°-..+0, For a fuller discussion of Post systems the reader is referred to the excellent chapters in Minsky [1967]. 5.17. Markov-computability Markov’s notion of computability is very similar to that derived from Post-systems by the second method above. Rather than restrict attention to monogenic systems, however, Markov gave rules to deter- mine uniquely which of the available produ are, briefly, as follows:6 Domains other than 6s A Markov normal algorithm over an alphabet ¥ is essentially alist Q of productions over 5 with the following features: (i) every production in Q has the form S:g82 > S\hS2, (Gi) certain productions in Q are singled out as being terminal. Given an input string c, a Markov algorithm applies productions in Q sequentially, according to the following rules. (a) if more than one production in Q applies toa string g, use the first one in the list Q, (b) if a production $;g52- SAS: applies to o in more than one way, apply it to the leftmost occurrence of g in 0, (c) the process halts having produced a string + either when a terminal production is used or if no production in Q applies to 7. With these rules, the definition of Markov-computable function f: *-> 3" is given in the obvious way. A Markov normal algorithm to compute f may use an alphabet extending 5. It is quite straightforward to establish: 5.18. Theorem Let f:3*+5*. Then f is Markov-compusable iff f is Post- computable. Markov-computability on N is defined by using some system of representing numbers in the usual way, and thus coincides with the other approaches to computability. 6. Computability on domains other than N In chapter 1 § 5 we showed how any notion of computability on N can be extended to other domains by the device of coding. By contrast, in the Previous section the definition of Post-computability on the domain of strings on a finite alphabet was given directly in terms of the objects (strings) and their intrinsic structure. A variety of such direct approaches to computability on other domains is possible: we give two examples. 6.1. Example D=Z. The URM idea may be extended to handle integers by making the following modifications: (a) each register contains an integer, () there is an additional instruction S“(n) for each n= 1, 2,3)... that has the effect of subsracting 1 from the contents of register Ry.3 Other approaches to computability 66 62. Example D=S", where ¥=(a,b). The class ®” of partial recursive {functions on 3* isthe smallest class of partial functions such that (a) the basic functions @ fle) W fo (ii) flo)= ob (iv) the projection fun are in #?, (b) is closed under substitution, (c) @ is closed under primitive recursive definitions of the following form: h(o, A)=flo) ie ra)~ gilo, 7, h(@, 7)) h(a, 7) = ga, 7, ho, 7) where f, gi, g26%”, (d) 2” is closed under minimalisation: if fla, z) is in R, so is the function A given by h(o)=ur(flo,7) =A) where yr means the first + in the natural ordering A, a, b, aa, ab, ba, bb, aaa, aab, aba, . For each of these, and other approaches to computability on a domain D that utilise the intrinsic structure of D, we find as expected that they are ‘equivalent to the approach that transfers the notion of computability from N by using coding. And, vice versa, any natural notion of compu- tability on a domain D induces an alternative (but equivalent) notion of computability on N via coding, as with Post-computability in § 5. 63. Exercises 1, Prove that URM-computability on Z as outlined in example 6.1 is equivalent to URM-computability via coding (example 1-5.1). 2. Prove that the class 2” of partial recursive functions on 2*, as defined in example 6.2, is identical to the Post-computable functions on E* 3. Suggest natural definitions of computability on the domains (a) 3x3 matrices, (b) Q (rational numbers). 4, Give a natural definition of Turing-computability on 3*, where 2 is any finite alphabet.7 Church's thesis o7 7, Church's thesis ‘We now turn our attention to the second question of the intro- duction to this chapter: how well is the informal and intuitive idea of effectively computable function captured by the various formal charac- terisations? In the light of their investigations, Church, Turing and Markov each put forward the claim that the class of functions he had defined coincides with the informally defined class of effectively computable functions. In view of the Fundamental result (1.1), these claims are all mathematically equivalent. The name Church's thesis (sometimes the Church-Turing thesis) is now used to describe any of these other claims. Thus, in terms of the URM approach, we can state: Church's thesis The inwitively and informally defined class of effectively computable partial functions coincides exactly with the class € of URM- computable functions, Note immediately that this thesis is not a theorem which is susceptible to mathematical proof; it has the status of a claim or belief which must be substantiated by evidence. The evidence for Church's thesis, which we summarise below, is impressive. 1. The Fundamental result: many independent proposals for a precise formulation of the intuitive idea have led to the same lass of functions, which we have called €. 2. A vast collection of effectively computable functions has been shown explicitly to belong to €; the particular functions of chapter 2 constitute the beginning of such a collection, which can be enlarged ad infininem by the techniques of that chapter, and ‘other more sophisticated methods. 3. The implementation of a program P on the URM to compute a function is clearly an example of an algorithm; thus, directly from the definition of the class %, we see that all functions in © are computable in the informal sense. Similarly with all the other equivalent classes, the very definitions are such as to demon- strate that the functions involved are effectively computable, 4. No one has ever found a function that would be accepted as computable in the informal sense, that does not belong to €. ‘On the basis of this evidence, and that of their own experience, most ‘mathematicians are led to accept Church's thesis. For our part, we3 Other approaches 10 computability 68 propose to accept and use Church's thesis throughout the rest of this book, in a way that we now explain. ‘Suppose that we have an informally described algorithm for computing the values of a function f. Such an algorithm may be described in English, or by means of diagrams, or in semi-formal mathematical terms, or by any other means that communicate unambiguously how to effectively cal- culate the values of f, where defined, ina finite amount of time. In such @ situation we may wish to prove that f is URM-computable. There are, broadly, two methods open to us. Method 1. Write @ program that URM-computes f (and prove that it does so), or prove by indirect means that such a program exists. This could be done, for instance, by the methods of chapter 2, or by showing that f belongs to one of the many classes shown by the Fundamental result to be equivalent to €. ‘Such a full and formal proof that f is URM-computable may be a long. and rather technical process. Essentially it would involve translation of the informally described algorithm into a program or into the language of, one of the other formal characterisations. Probably there would be various flow diagrams as intermediate translations. ‘Method 2. Give an informal (though rigorous) proof that the given informal algorithm is indeed an algorithm that serves to compute f. Then appeal to Church's thesis and conclude immediately that is URM- computable. We propose to accept method 2 as a valid method of proof, which we call proof by Church's thesis. 7A. Examples 1. Let P be a URM program; define a function f by 1 if P(x)Ly after 1 or fewer steps fle y,0=4 of the computation P(x), 0 otherwise. ‘An informal algorithm for computing f is as follows. ‘Given (x, y, 1), simulate the computation P(x) (on a piece of paper, for example, as in example 1-2.1), carrying out 1 steps of P(x) unless this computation stops after fewer than ¢ steps. If P(x) stops after 1 or fewer steps, with y finally in Ry, then flay y, = 1. Otherwise (ic. if P(x) stops in ror fewer steps with7 Church's thesis 69 some number other than y in Ry, or if P(x) has not stopped after ¢ steps) we have f(x, y,1)=0." Simulation of P(x) for at most ¢ steps is clearly a mechanical procedure, which can be completed in a finite amount of time. Thus, fis effectively computable. Hence, by Church’s thesis, fis URM-computable. . Suppose that f and g are unary effectively computable functions. Define a function ht by nay={ 1 ix eDom(f)orx€Dom(g), lundefined otherwise An algorithm for h can be described in terms of given algorithms for the effectively computable functions f and g as follows: “Given x, start the algorithms for computing f(x) and g(x) simultaneously. (Envisage two agents or machines working simultaneously, or one agent who does one step of each algorithm alternately.) If and when one of these computations terminates, then stop altogether, and set (x)= 1. Otherwise, continue indefinitely. This algorithm gives f(x) = 1 for any x such thet either /(x) or £2) is defined; and it goes on for ever if neither is defined. Thus ‘we have an algorithm for computing h, so by Church's thesis his URM-computable. Let fin)=the nth digit in the decimal expansion of = 3.14159... (90 we have f(0) =3, f(1)= 1, f@2)=4,etc.). We can ‘obtain an informal algorithm for computing f(n) as follows. Consider Hutton’ series for 2f.3(2) Beh H(-2(2) 2) 5 SPE fay MY] Eno tao hn by the elementary theory of infinite series cma tl/10" Now se is rational, so the decimal expansion of si can be effectively calculated to any desired number of places using long, division. Thus the following is an effective method for calculating F(a) (given a number n)3 Other approaches to computability 70 ‘Find the first N =n +1 such that the decimal expansion, sw does not have all of ay.1y--., @y equal to 9. (Such an N exists, for otherwise the decimal expansion of would end in recurring 9, making 7 rational.) Then put f(r) = dy.” ‘To see that this gives the required value, suppose that ay, #9 with mN. (Note. The term countable is normally used to mean finite or denumerable; thus, for infinite sets, countable means the same as, denumerable. The term countably infinite is used by some authors instead of denumerable.) (b) An enumeration of a set X is a surjection g: N-» X; this is often represented by writing x [X0y ay aye1 Numbering programs 3 where injective. (c) Let X bea set of finite objects (for example a set of integers, or asetoof instructions, or aset of programs); then X is effectively denumerable if there is a bijection f: X >N such that both f and f°" are effectively computable functions. (Note. We mean here the informal notion of effectively computable. This is compelled on us since, in general, there is no available formal notion of computability of functions from X to IN." In cases where some formal notion does apply, we take this to bbe the meaning, as for example in theorem 1.2(a).) Clearly, a set is denumerable if and only if it can be enumerated without repetitions. (). This is an enumeration without repetitions if gis For the main result ofthis section we need the following (recall that N~ denotes the set of all positive natural numbers): 1.2. Theorem The following sets are effectively denumerable. (a) NX, (b) NU XN XNT, (6) Uneol the set of al finite sequences of natural numbers Proof (a) A bijection 1: NXN-+ Nis defined by (m,n) =2"(2n +1)-1. It is clear from the defiaition that zr is in fact a computable function; to ee that the inverse is effectively computable observe that is given by (x) = (u(x), mlx), where sr, m2 are the computable functions defined by a(x) = (x + Dh, rola) = A(x + 1)/2"'— 1). (Cf. exercise 2-4.16(2).) (b) An explicit bijection ¢: N* x N* XN* > Nis given, using the function = of (a), by Em, q)= m(am=1, n= 1,a-D- ‘Then we have Ex) (wal mi(z)) +1, aralalx)) +1, wale) + 1). * To say that we should ute a notion of computability based on some coding bess the whole question, since a coding san effective (in the informal sense) function4 Numbering computable functions 74 Since the functions 7, m1, 72 are effectively computable, then so are {and ¢-' (c) A bijection: LJk~o'N* > Nis defined by Hass coo yg) = ZENO DTT 2, pgretenctht iy, Clearly + is an effectively computable function. To see that 7 isa bijection, and to calculate + "(x), We use the fact that each natural number has a unique expression as a binary decimal Thus, given x, we can effectively find unique numbers k= 1 and 05) N that maps the four kkinds of instruction onto natural numbers of the forms 4u, 4u + 1,4u +2, 4u +3 respectively; we use the functions a and ¢ defined in the proof of, theorem 1.2. B(TOn, n) = 40m —1,n—1)+2, BUlm, n, 2) =4¢(n, m, gq} +3. ‘This explicit definition shows that B is effectively computable. To find B(x), first find u, r such that x= 4u-+r with O=r-<4, The value of indicates which kind of instruction @'(x) is, and from u we can effectively find the particular instruction of that kind. Specifically then B(x) = Zu +1); Sut 1); ifr1 Numbering programs 75 ifr =2, then 6 "x)= Tmi(u)+1, ma(u) +0); ifr =3, then 6-"(x) =J(m, nq), where (m,n, @) Hence 8" is also effectively computable. 1 Now we can prove: 14. Theorem ® is effectively denumerable. Proof. Define an explicit bijection y:%—N as follows, using the bijections + and # of theorems 1.2 and 1.3: if P= hf... then (P)= 78D), BUD). Since 7 and B are bijections, so is y; the fact that r, and their inverses are effectively computable ensures that y and y” are also effectively computable. 0 ‘The bijection y will play an important role in subsequent development. For a program P, the number y(P) is called the code number of P, or the Gédel” number of P, or just the number of P. We define P, =the program with (code) number n =v" ‘and say that P, is the nth program. By construction of y,if m # n, then Pm, differs from P,, although these programs may compute the same functions. It is of the utmost importance for later results that the functions y and y"' are effectively computable; ie. (a) Given a particular program P, we can effectively find the code number y(P); (6) given a number n, we can effectively find the program Pray '(n)) In order to emphasise this we give two simple illustrations. 1.5. Examples (a) Let P be the program T(1, 3) (4), Z(6). We will calculate y(P). BUTI, 3)) = 4(0, 2)4+2=4(2°(2x2+1)-1)+2=18, B(S(4)) =4x3+1=13, BIZ(6)) = 4x5 = 20. * The term Géde number is wed alter K. Gadel who frst exploited the iden of coding non-numerical objects by numbers in his famous paper (Godel [1931).4 Numbering computable functions 76 Hence y(P)=2'*+27+2"=1 = 9007203549970431. (b) Let n =4127; we will find Pasar. 4127 = 2° +2!?— 1; thus Payar isa program with two instructions Jadawtere BU) =5=4x141, B(h)=12-5-1 X142=4a(1,0)+2, Hence from the definition of 8, I, = $(2) and f2= T(2, 1),50 Passy is 802) 72,1) ‘There are, of course, many other possible effective bijections from to ‘N;our choice in defining the details of y was somewhat arbitrary. What is vital, we again emphasise, is that y and y~* are effectively computable, The particular details of y are not so important, For subsequent theory, any other bijection y' would suffice, provided that ' and its inverse are effectively computable, However, we have to fix on one particular numbering of programs, and we have chosen that given by . For the rest of this book, y remains fixed, so that for each particular number 1, the meaning of P, does not change. Thus, for instance, Par2y always means the program S(2), T(2, 1). 1.6, Exercise Find (a) BUG, 4,2)), () B (503), (c) the code number of the following program: 13,4), 83), 20), (d) Pro 2. Numbering computable functions Using our fixed numbering of programs, we can now number computable functions and their domains and ranges. We introduce some important notation which is basic to the rest of the book, 2. Definition For each a eN, and n= 1:2 Numbering computable functions n (a) 6" =the n-ary function computed by Py = ff) in the notation of chapter 1 § 3, jomain of Bi" ={(x. +n): Palettes skal = range of 6)" (b) We ES We shall be mainly concerned with unary computable functions in later chapters, so for convenience we omit the superscript (1) when it occurs; thus we write 4 for 6." W, for W.?, and B, for E.". 2.2. Example Let a =4127; from the previous section we know that Paso is $(2), 72, 1). Hence dantx)=1 (all) and OMG mdamtl if aed Thus War=N, Eu: Win Suppose that fis unary computable function. Then there isa program Pysay, that computes f,s0 f= ¢,, where a = y(P). Wesay then thata isan index for [Since there are many different programs hat compute a given function, we cannot say that a isthe index for f;in fact, each computable function has infinitely many indices. We conclude that every unary computable function appears in the enumeration 03 by. and that this is an enumeration with repetitions. Similar remarks apply to n-ary functions and their enumeration. i NY, EG) =N" ifm>d. 2.3. Exercise Prove that every computable function has infinitely many indices. Recall that we denoted the set of all n-ary computable function by @;, 2.4. Theorem G, is denumerable.4 Numbering compuiable functions 8 Proof. We use the enumeration i", 64". 64", ... (which has repeti- tions) to construct one without repetitions. f(0)=0, Let a 4 {fim +1)= n2(b # by. 5 Offa) Then GYfaie Ofte OF » is an enumeration of €, without repetitions. C1 Note, Weare not claiming that f as defined in this proof is computable: in fact, we will be able to show later that this is not the case. It is possible, nevertheless, to give a complicated construction of a total computable function h such that $i"), 64%)... is an enumeration of €, without repetitions. This was proved by Friedberg [1958] 2.8. Corollary is denumerable. Proof. Since € =| J,=1 €q, this follows from the fact that a denumer- able union of denumerable sets is denumerable. Explicitly, for each n let f, be the function used in theorem 2.4 to give ‘an enumeration of 6, without repetitions. Let 7 be the bijection Nx N= No theorem 1.2. Define 4: €>N by Ab fem) = 24m, n= 1), Clearly 0 is bijection, ‘The next theorem shows that there are functions that are not compu- table. The idea of the proof is as important as the result itself. 2.6. ‘Theorem There is a total unary function that i not computable. Proof. We shall construct a total function f that is simultaneously different from every function in the enumeration do, 6s, 625... of Explicitly, define _{du(n)+1 if a(n) is defined, 1 acim aandecd Notice that we have constructed fso that for each nf differs from dy atm if dy(n) is defined, then f differs from by in that fln) # bal): it b(n) isundefined, then f differs from d, in that f(n) is defined3 The diagonal method 9 Since / differs from every unary computable function 4, f does not appeariin the enumeration of ; andis thus notitself computable. Clearly fistotal, 3. Discussion: the diagonal method ‘The method of constructing the function f in theorem 2.6 is an example of the diagonal method of construction, due to Cantor. Many readers will be familiar with this method as used in proofs of the uuncountability of the set of real numbers. The underlying idea is appli- cable in a wide variety of situations, and is central in the proofs of many results concerning computability and decidability To see why the term diagonal is used, consider again the construction of f in theorem 2.6. Complete details of the functions $0, 41, ... can be represented by the following infinite table: We suppose that in this table the word ‘undefined’ is written whenever Salm) is not defined. ‘The function f was constructed by taking the diagonal entries on this table (circled) 010), 6i(1), 212), and systematically changing them, obtaining £0), 0), 2), such that fin) differs from x(n), for each n. Note that there was considerable freedom in choosing the value of f(n); we only had to ensure that it differed from (1). Thus nya {4slD +27" itbs(n) is defined, # : if 6,(n) is undefined, is another non-computable total function,4. Numbering computable functions 80 We can summarise the diagonal method as we shall be using it, in the following way. Suppose that xo, Xi, X2+. - is an enumeration of objects of ‘a certain kind (functions or sets of natural numbers). Then we can ‘construct an object x of the same kind that is different from every Xw using the following motto: “Make x and xudifferatn ‘The interpretation of the phrase differ arn depends on the kind of object involved. Functions may differ at n over whether they are defined, or in their values at n if defined there; with functions, there is usually freedom to construct y so as to meet specific extra requirements; for instance, that {x be computable, or that its domain (or range) should differ from that of ‘each Xn In the case of sets, the question at 1 is whether or not n is a member, We illustrate the diagonal construction when sets are involved. 3.1. Example Suppose that Ao, As, Aa... i8 an enumeration of subsets of N. We can define a new set B, using the diagonal motto, by ne Bit andonlyifné Ay. Clearly, for each n, B¥ Ay. ‘There are important applications of the diagonal method in the next ‘two chapters. 3.2. Exercises 1. Suppose that f(x, y) isa total computable function. For each m, let gm be the computable function given by gnly)=flm,y), Construct a total computable function ft such that for each m, 14 be 2. Let fo, fi... be an enumeration of partial functions from Mito. Construct a function g from N to N such that Dom(g) # Dom(f) for each i 3. Let f bea partial function from NtoN, and let m €N. Construct a non-computable function g such that aix)=flx)— forxsm, 4.(a) (Cantor) Show that the set of all functions from ‘to Nis not denumerable.4 The s-m-n theorem 81 (6) Show that the set ofall non-computable total functions from N to Nis not denumerable 4. The som-n theorem In the final section of this chapter we prove a theorem that has ‘many important uses, especially in conjunction with the main theorem of the next chapter. Suppose that f(x, y) is a computable function (not necessarily total). ‘Then for each fixed value a of x, f gives rise to a unary computable function go, where Bal) = Flay). Since gs is computable, it has an index e, say, so that fla, y)=444y). ‘The next theorem shows that such an index ¢ can be obtained effectively from a. This isa particular case of a more general theorem, known as the s-m-n theorem, which we prove below. (The reason for this name will be explained after theorem 4.3.) For most purposes in this book, the following suffices, 4.1, Theorem (The s-mt-n theorem, simple form) Suppose that f\x, y) i a computable function. There is a toral computable function k(x) such that Flo, y)= ducal) Proof. For each fixed a, k(a) will be the code number of a program Q. which, given initial configuration Ri “ y[olo]fo ‘computes f(a, y)- Let F be a program that computes f. Then for Q, we write down F prefaced by instructions that transform the configuration (*) to R, Ry alyfofo4 Numbering computable functions 82 Thus, define Q, to be the following program TU,2) za) say a times sil) F Now define (a) =the code number of the program Q, Since F is fixed, and from the fact that our numbering y of programs is effective, we see that k is an effectively computable function. Hence, by Church's thesis, k is computable. By construction bx) =Fla, y) foreacha. ‘The s-m-n theorem is sometimes called the Parametrisation theorem because itshows that an index for a computable function (such as g, in the discussion above) can be found effectively from a parameter (such as a) on which it effectively depends. Before giving the full s-m-n theorem we give some simple illustrations of the use of theorem 4.1 in effectively indexing certain sequences of computable functions or their domains or ranges. 4.2. Examples 1. Let f(x, y)=y". By theorem 4.1 there is a total computable k such that dio(y) = y". Hence, for each fixed n, k(n) is an index for the function y". y ify isa multiple of x 2 Lefts yo={ lundefined otherwise. ‘Then fis computable, so let k be a computable function such that Seco()) =Flas y). Then, for each fixed xin (9) is defined iffy isa multiple of » iffy is in the range of dim ‘So we have an effective indexing of the sequence of sets (nN) as () the domains of computable functions, (ii) the ranges of computable functions.4 The s-m-n theorem 83 One obvious way to genertlise theorem 4.1 is to replace the single variables x,y by m- and n-tuples x and y respectively. We can also reflect the fact thatthe function k defined in the proof of theorem 4.1 depended effectively on a particular program for the original function f. Thus, instead of considering a fixed computable function f(x, y) we consider & general computable function 8:""(x,y),and the question of effectively finding, for each ¢ and x, a number z such that ora y= 629) 4.3. Theorem (The s-m-n theorem) Foreach m,n = 1 there isa total computable (m-+1)-ary function Sle, x) such thas OL x, y= bea) Proof. We generalise the proof of theorem 4.1 For any i= 1 let Qli,x) be the subroutine xi su 2 bx times sti) that replaces the current contents of R, by x. Then for fixed m, n define sit(e,) to be the code number of the following program: Tim m-+n)) This part of the program transforms any configuration R, Ry T2,m-+2) Taymer)| Let} ] o 1 of Qa.) into 00.5) Ri RiRui Rein i Kr eee | tm] vn Yan { O Qn, x0) P, From this explicit definition, and the effectiveness of y and y"', we get that sis effectively computable, hence computable, by Church's thesis. 0)4. Numbering computable functions 84 ‘The notation sf for the function given by theorem 4.3 has given rise to the standard description of this result as the s-m-n theorem, We will also ‘use this name to describe the simpler version given in theorem 4.1. tis not hard to see that the function s% as defined above is in fact primitive recursive, With a little thought its also possible to see that for ‘each m there is a function s™ (also primitive recursive) that suffices in theorem 4.3 for all n. See the exercises 4.4(5) below. 44. Exercises 1. Show that there is @ total computable function k such that for each n, k(1) is an index of the function (x). 2, Show that there isa total computable function k such that for each n, Wan) = the set of perfect nth powers. 3. Let n = 1. Show that there is a total computable function s such that WI) ise syad yet yat st Yea 4, Show that the functions sy defined in theorem 4,3 are all primitive recursive. 5, Show that for each m there is a total (m +1)-ary computable function s such that for all x Px, y= bP cold) where x, y are m-and n-tuples respectively (Hint. Consider the definition of s7(e, x) given in the proof of theorem 4.3. The only way in which n was used was in determi- ning how many of the rj, ray... to transfer to Rinsiy Rms2s ++ Now recall that the effect of P, depends only on the original contents of Ri, ..-,Rwirov where p is the function defined in chapter 2§ 2: p(P.) is independent of n.) Show further that there is such a function 5” that is primitive recursive.5 Universal programs In this chapter we establish the somewhat surprising result that there are universal programs; ie. programs that in a sense embody all other programs, This results one ofthe twin pillars that support computability theory (the other isthe s-m-n theorem); both rest on the numbering of programs given in chapter 4 Important among the applications of universal programs is the construction of specific non-computable functions and undecidable predicates, a topic pursued in chapter 6. We give a foretaste of such applications in § 2 of this chapter; we also use a universal program to construct a total computable function that is not primitive recursive, as promised in chapter 3. The final section of this chapter is devoted to some illustrations of the use ofthe s-m-n theorem in conjunction with universal programsto show that certain operations on the indices of computable functions are effective (a foretaste of the topic of chapter 10). 1. Universal funetions and universal programs Consider the function Y(x, y) defined by WO y)= dey). ‘There is an obvious sense in which the single function y embodies all the unary computable functions do, 1, 63... sinee for any particular m, the function g given by aly) = a0, y) is just the computable function $,,. Thus we describe was the universal function for unary computable functions. Generally, we make the following definition.5 Universal programs 86 Ll. Definition The universal function for n-ary computable functions is the (n+1)-ary function Uf) defined by WOE 15-2 kd PE Oy We write dy for wi. oe) ‘The question arises, is vx (or, generally, Uff’) a computable function? Ifso, then any program P that computes i would appear to embody all other programs, and P would be aptly called a universal program. At first, perhaps, the existence of a universal program seems unlikely. Neverthe- Jess, it is not hard to see that dy is indeed computable. The pointis that a universal program P does nor need to contain all other programs P, in itself; P only needs the ability to decode any number e and hence mimic Pe 1.2. Theorem For each, the universal function is computable. Proof. Fix n.and suppose that we are given an index e and an n-tuple x ‘An informal procedure for computing ¢(e, x) is as follows “Decode the number ¢ and write out the program P.. Now mimic the computation P.(x) step by step, at each step writing down the configura~ tion of the registers and the next instruction to be obeyed (as was done in example 1-2.1). If and when this computation stops, then the required value y{"(e, x) is the number currently in Ri.” ‘We could conclude immediately (using Church's thesis) that Ji (e,x) is computable. Because of the importance of this theorem, however, we prefer to outline the beginnings of a formal proof and then make a rather less sweeping appeal to Church's thesis. (For the sake of completeness of our exposition we shall provide the rest ofthe formal proof in an appendix to this chapter.) ‘The plan for a formal proof is o show first how to use a single number to code the current situation during a computation; then we show that there is a computable function expressing the dependence of o on (a) the program number e, (b) the input x, (c) the number of steps of the computation that have been completed. We will see that this suffices to prove the theorem. Let us return, then, to the computation P,(x) considered above. As we have seen in examples, the current situation during @ computation is completely specified by (i) the current configuration of the registers1 Universal functions and universal programs a7 ‘isos ap... and (ti) the number j of the next instruction in the compu- tation. Since only finitely many of the numbers r, are notzero, the current configuration can be specified by the single number o=2"3%...= 7] pi. (Recall that p; is the ith prime number.) We call this number the configuration code or just the configuration if there is no ambiguity. Note that the contents r; of R, can be easily recovered from c; in fact 1 =(c), (using the function of theorem 2-4.15(d)) ‘The complete description of the current situation can now be coded by the single number o = 7(c, ), which we call the current state of the computation P, (x). (Here 7 is the pairing function used in the proof of theorem 4-1,2.) We will make the convention that if the computation has stopped, then j=0 and c is the final configuration, Note that ¢ = m(¢) and j= axa) where 7, m2 are the computable functions defined in theorem 4-1.2, Now ¢, j, « change during the computation; their dependence on the program number ¢, the input x and the number r of steps completed is expressed by defining the following (m + 2)-ary functions: (1) ale, x, 4) =the configuration after 1 steps of P(x) have been completed (=the final configuration if P:(x)l in ¢ or fewer steps) the number! of the if P(x) has next instruction for not stopped 2) plana) P@)when steps aftersor have been completed, fewer steps, o if P.(a)| in ror fewer steps (3) ole.) the state of the computation P.(x) after steps = mlenle,%, 1) inl@2, 9). ‘The aim now is to show that , (and hence cy and j,) are computable functions. To see why this is sufficient, suppose that this has been done. Clearly, if the computation P,(x) stops it does so in stl jn(e, x, )=0) steps; then the final configuration is ¢,(e, x, t(jn(€s%, £)=0)), and so we * Wemean here the number j such thatthe nex instruction Fis the fh instruction ‘of P,; we do not mean the code number 80)5 Universal programs 88 have WP Cex) =(enles a tial. 25) = Os Thus, if cy and j, are computable, so is Yj’ (using substitution and ‘minimalisation) and our proof is complete. ‘We now use Church’s thesis to show that o (and hence cy and jy) are computable. We have the following informal algorithm for obtaining oa(e,x, t+ 1) effectively from a (e, x,t) and e: “Decode a, (e,%,£) to find the numbers ¢ = ca(e, 4,1) andj = fale, 9). If 7=0, then on(ex,t+1)=o,(e,%,1). Otherwise, write out the configuration coded by ¢, © [er | es | es (im | 0 | 0 say, and by decoding ¢ write out the program P.. Now find the jth instruction in P, and operate with it on the configuration (*), producing a ‘new configuration with code c’ say. Find also the number j’ of the new next instruction (with /’= Of the computation has now terminated). Then we have onle,x, t+ 1)= mle’, /?. ‘This shows informally that ¢, (¢, x, 1) iscomputable by recursion in 4 since for *=0.we have orale, 4, 0)= w(2"3"... pits 1) to start the recursion off. Hence, by Church's thesis, o, is computable, and our theorem is now proved. Note, Since this theorem is so basic to further development, we provide in the appendix a complete formal proof that 4 (and hence ¥) is ‘computable. This then provides further evidence for Church’s thesis, (Our formal proof also gives us the extra information that ois actually primitive recursive.) From the proof of this theorem we obtain: 13. Corollary For each n= 1, the following predicates are decidable. (a) Sa(e,x, ¥, = "Pe(x) Ly in tor fewer steps", (0) Hy(e,x, 1) =*P_(2)} in tor fewer steps’ Proof. (a) Seles, ¥s = "jn(6,%5 1) =0 and (Cy(e, 4, )). = y"- (b) Hye, x, = Inle31 Universal functions and universal programs 89 The significance of the next corollary is discussed in the first note below. 1.4, Corollary (Kleene’s normal form theorem) There isa total computable function U(x) and for each n= 1a decidable predicate T,(e, x, 2) such that (a) d£(x) is defined if and only if Bz Ty(e, x, 2), (0) 82°G@)=Ulus Tale, 2)). Proof. To discover whether 4" (x) is defined, and the value if itis, we need to search for a pair of numbers y,¢ such that Sy(e, xy, £). We have the w-operator that enables us to search effectively for a single number having given property. To use this in searching for apair of numbers, we can think of a single number z as coding the pair of numbers (z), and (z)2. ‘Then, as z runs through N, the pair ((z);, (z)s) runs through Nx. So we define Tale, x, 2)=Sy(@,5 (2) (2a) For (a), suppose that ¢{"(x) is defined; then there are y, ¢ such that Sn(e, X, Ys 1), 80 putting z = 2"3' we have T,(e, x, 2). Conversely, if there is z such that T,,(e, x, z), then from the definition of T,, Pe(x)l; ie. 6¢" (x) is defined. For (6), it is clear from the definition of T,, that if {"’(x) is defined, then for any z such that T,,(e, x, z), we have ${"'(x) =(z),. So if we put U(z)=(z); then OP'(e)=Uluz Talex, 2). 0 Notes 1, From the appendix to this chapter it follows that the functions ¢ and j, are primitive recursive. Hence, the predicates S,, H,, Ts in corollaries 1.3 and 1.4 are also primitive recursive. Thus, in particular, the Kleene normal form theorem shows that every computable function (or partial recursive function) can be obtained from primitive recursive functions by using at most one application of the 4-operator. The theorem gives, moreover, a standard way of doing this. 2. ‘The technique of searching for pairs of numbers by thinking of a Single number z as coding the pair (z)s, (z)2 (as used in the proof of corollary 1.4) is often used in computability theory. We give an exercise needing this technique below (exercise 1.5(1)). ‘The technique can also be used in searching for sequences (asta, 54) for any n> 1.5 Universal programs 90 15. Exercises 1. (i) Show that there is a decidable predicate Q(x, y,z) such that (a) yeE, if and only if 32 Q(x », 2), (}) ify By and Qlx, 2), then 4 ((2)))=y. (i) Deduce that there isa computable function g(x,y) such that (a) g(x, 9) is defined if and only ify ¢ Ee. () if ye, then glx, y)e Ws and dx(g(x, y))=ysiee. a(x ye 6). (ii) Deduce that if f is a computable injective function (not necessarily total or surjective) then f~' is computable, (cf. exer- cise 2-5.4 (1)). 2, (ef. example 3-7.1(2)) Suppose that f and g are unary comput- able functions; assuming that T; has been formally proved to be decidable, prove formally that the function f(x) defined by a -{! ifx eDom(f)or x ¢Dom(g), "(undefined otherwise, is computable. 2. ‘Two applications of the universal program ‘We illustrate now the use of the computability of universal functions in diagonal constructions. This kind of application will be explored more thoroughly in the next chapter. 24. Theorem The problem “és is total” is undecidable. Proof. Let g be the characteristic function of this problem; ie. =f, toto B10 if bis not total. ‘We must show that g is not computable. To achieve this, we use the diagonal method to construct a total function fthatis different from every computable function, yet such that if g is computable, then so is /. Explicitly, define f by ya {200% if6e isto, if isnottotal Clearly, f is total and differs from every computable function ¢.. Now, using g and dy we can write fas follows: ule x) +1 ifgte)=1, foo-{9 itew)=0,2 Two applications of the universal program 1 Now suppose that g is computable; since vu is computable, then, by Church's thesis, so is f, which is a contradiction. Hence g is not computable. 0 (Our second application here fulfils the promise made in chapter 3 § 3, 2.2. Theorem There isa toral computable function that is not primitive recursive. Proof. We give an informal proof. Recall that the primitive recursive functions are those functions that can be built up from the basic functions by @ sequence of applications of the operations of substitution and recursion, Thus each primitive recursive function can be specified by 2 plan that indicates the basic functions used and the exact sequence of ‘operations performed in its construction. To describe such a plan it is convenient to adopt some notation such as the following: Sub(f; g1, 825+. ++ 8m) denotes the function obtained by substituting Bis+++1 8m into f (assuming that fis m-ary, and gy,..., gm are n-ary for some 7); Recif, g) denotes the function obtained from f and g by recursion (assuming that f is n-ary and g is (n +2)-ary for some n).. If we write S for the function x-+1, then we have, for example, the following plan for the function f(x) =x". We use letters gy,..., gs to Then from (a) and (6) we have (6) () aio Wor Gi) if ye E,, then by(buiai(y)) = Hence, if 6x is injective, then dx.) =47' and Exy.) = Ws. Effectiveness of recursion. Let x= (++) and consider the (n+3)-ary function f defined by Fler, e220) ~ O22), New ene y + D= 42's yofleren 89) ‘Then using the universal functions yi!’ and yi"! to rewrite the expressions on the right, this is a definition by recursion from computable functions, so fis computable. Moreover, for fixed ¢:, 2 the function g(x, y)=flei,e2,% y) is the function obtained from oi! and 6!" by recursion. By the som-n theorem there isa total computable function ries, €2) such that bial y) = fle, €25% ¥)- Hence r(e1, ¢2) isan index for the (n+1)-ary function obtained from 6%) and 6!" by recursion. In the notation of theorem 2.2 bien Recto) dis" forall e1, es ‘The following exercises give more examples of the use of the s-m-n theorem in showing that operations are effective on indices. 32. Exercises Show that there is a total computable function k(e) such that for any ¢, if4, is the characteristic function for a decidable predicate (M(x), then di, is the characteristic function for ‘not M(x)’. Show that there is a total computable funetion k(x) such that for every x, Busi = We . Show that there is a total computable function s(x, y) such that for all x, y, Euan = Be Ey . Suppose that f(x) is computable; show that there is a total computable function k(x) such that for all x, Waia)=f-"(W).Appendix. Computability of 0» 95 5. Prove the equivalent of example 5 above for the operations of substitution and minimalisation, namely: (a) Fix m,n21; there is a total computable function s(¢,€1,-++ém) Such that (in the notation of theorem 2.2) Pikeernren) = SUb(HL" 5 4), 6's «++» Ben) (b) Fixn = 1; there isa total computable function k(e) such that for alle, (2) = my (Ex y) =O), (We could extend the notation of theorem 2.2 in the obvious way and write #2, =Min(d,""").) Appendix Computability of the function 7, In this appendix we give a formal proof that the function a defined in the proof of theorem 1.2 is computable (in fact, primitive recursive) thus completing « formal proof of the computability of the universal function Theorem. The function or, is primitive recursive. Proof. For the definition of e;, and the functions c, and j, coded by a, refer to the proof of theorem 1.2. ‘We define two functions ‘contig’ and ‘nxt’ that describe the changes in 6. and j, during computations, Suppose that at some stage during computation under P, the current state is 7 = 27(c,j), and suppose that P, has instructions. We can describe the effect of the th instruction of P, on the state o by defining {the new configuration Jafterthe jthinstruction if 10, z,and this occurs as the jth instruction in a program, 4) we h2) 0 otherwise (The ‘next instruction for the computation’ here is as defined in chapter 1 +1 on, if J, is a jump instruction 3(ms, m2, q) we may have If these four functions are primitive recursive, then remembering that = alc.) where ¢= ml) and j= mala) we have ch(x(a), gale, malo) if 1 aaa) 0, x= 242024, ght then 6(i,x) is the ith index k such that «(k, x) thus, if 1s/s/(x), Hence wyse(Z alka)=i) if sisla)andx>0, 0 otherwise. (iv) From the definition: ali.x)= Blix) 0,1) a(i+1,x)=(b(i+1,2)+b(4, x))=1 (=) From the above explicit formulae, using the techniques of chapter 2, these functions are all primitive recursive (6) The functions In(e) and gn(e, j) are primitive recursive. Proof. From the definitions of the coding function : In(e)= He +1), ante, =a(e+1), where | and a are the functions in (5). (7) There are primitive recursive functions u, i, ay Bi, U2, ¥s Such that: if 2 = B(Z(m)), then u(z) =m, if z = B(S(m)), then u(z) =, if z = B(T(m,, ma)), then w:(z) =m, and u2(z) = ma, if = Bm, ma q)), then v)(2)= mn, v3(z)= ma, ban = and vs(z)=4.5 Universal programs 98 Proof. From the definition of 8, and writing (z/4) for qt(4, z), take u(z)=(2/4)+1, us(z)=m(z/4)+1, us(z)= mal2/4)+1, ve(z) = m(ai(z/4))+ 1, vale) = ma(ai(2/4)) +1, vs(z)= male/4) +1, (8) The following functions are primitive recursive: Gi) zero(c, m)= the change in the configuration ¢ effected by instruction Z(m), =atipin, (ii) suc(c, m)= the change in the configuration ¢ effected by instruction S(m), Pm (ii) transfer(e, m, n)= the change in the configuration ¢ effected by instruction T(m, n), = atin’ epn). (9) The function ch(c, z) (defined in (3) above) is primitive recursive. Proof zerolc, u(z)) itrm(4, z)=0 (ie. z is the code of a zero instruction), suc(e, u(z)) iftrm(4, z)=1 Ge.z is the code of a chic, 2) =! successor instruction), transfer(c, wi(z), us(z)) ifrm(4, z)=2 (ie. is the code of a transfer instruction), © otherwise.Appendix. Computability of o, 99 (10) The function v(c, j, z) (defined in (4) above) is primitive recursive. Proof. We have p+. ifrm(4, 2) #3 eis the code of an arithmetic instruction), wehe) Oe # Cee ifrm(4, 2)=3 (ie. z isthe code of a jump instruction) waz) if (ox2) = (ager) From this definition by cases, we see that » is primitive recurs We have now shown that the functions (1)-(4) above are primitive recursive, so the proof of the theorem is complete. 06 Decidability, undecidability and partial decidability In previous chapters we have noted several decidable problems, butso far we have encountered only one explicit example of undecidability: the problem ‘4, is total’ (theorem 5-2.1). It is of considerable interest to identify decidable and undecidable problems; the latter, particularly, indicate the limitations of computability, and hence demonstrate the theoretical limits to the power of real world computers. In this chapter the emphasis is largely on undecidability. In § 1 we give a survey of undecidable problems arising in the theory of computability itself, and discuss some methods for establishing undecidability. Sections 2-5 are devoted to a sample of decidable and undecidable problems from other areas of mathematics: these sections will not be needed in latet chapters and may be omitted. In the final section we discuss partial decidability, a notion closely related to decidability Letus recall from chapter 1 that a predicate M(x) is said to be decidable if its characteristic function cw, given by 1. ifM(x) holds, 0. if M(x) does not hold, catx)={ is computable, This is the same as saying that M(x) is recursive (see chapter 3 § 2). The predicate M(x) is undecidableifitis not decidable. In the literature all of the following phrases are used to mean that M(x) is. decidable. M(x) is recursively decidable, M(x) has recursive decision problem, M(x) is solvable, M(x) is recursively solvable, M(x) is computable, ‘An algorithm for computing cy is called a decision procedure for M(x).1 Undecidable problems in computability 101 1. Undecidable problems in computability Most proofs of undecidability rest on a diagonal construction, as in the following important example. 11. Theorem “xe W, (or, equivalently, “du(x) is defined’, or “P.(x)1', or “Wu x) is defined’) is undecidable, Proof. The characteristic function f of this problem is given by 1 ifxe Wy TO" 10 tne We Suppose that f is computable; we shall obtain a contradiction, Specifically, we make a diagonal construction ofa computable function ¢ such that Dom(g)# W,(=Dom(¢,)) for every x; this is obviously contradictory. ‘The diagonal motto tells us to ensure that Dom(g) differs from W, atx; so we aim to make xeDom(g) ¢ x¢ Ws Let us define g, then, by - fre W, ec itfin)=0), 80)" undefined ifsc W, (ie. if (2) 1) Since fis computable, then s0 is g (by Church's thesis); so we have our contradiction, (To see this in detail: since g is computable take m such that g= dm: then me Wm €2 meDom(g) <> me Wma a contradiction). We conclude that fis nat computable, and so the problem ‘x ¢ W,” is undecidable. Note that this theorem does nor say that we cannot tell for any particular number a whether 4,(a) is defined. For some numbers this is quite simple; for instance, if we have written a program P that computes a total function, and P=P,, then we know immediately that $_(a) is defined. What the theorem says is that there is no single general method for deciding whether d(x) is defined; ie. there is no method that works for every x. Ann easy corollary to the above result is 12. Corollary There is a computable function h such that the problems ‘x € Dom(i)’ and ‘x€Ran(hy' are both undecidable.6 Decidability, undecidability and partial decidability 102 Proof. Let a tre, We)" \ondefined it ze We ‘Then h is computable, by Church's thesis and the computability of the universal fonction dy (ot, formally, we have that h(x)=x 1(duls,2)) ‘which is computable by substitution). Clearly we have x ¢Dom() ¢> weW, 49 xeRan(h), s0 the problems ‘x Domi)’ and “x ¢ Ran(h) are undecidable. © Another important undecidable problem is derived easily from theorem 1.1: 1.3. Theorem (the Halting problem) The problem “d,(y) is defined! (or, equivalently ‘Px(y)V" or ‘y € W,”’) is undecidable. Proof. Arg informally, if the problem ‘¢,(y) is defined’ is deci- able then so is the problem ‘6, (x)is defined’, which iif anything easier. But this contradicts theorem 1.1. Giving this argument in full detail, let g be the characteristic function for ‘#,(y) is defined’; i.e. ie vf if d4(y) is defined, BSL it .(y)is not defined. If g is computable, then so is the function f(x) = g(x, x); but f is the characteristic function of ‘x ¢ W,", and is not computable by theorem 1.1 Hence g is not computable; so “#,(y) is defined’ is undecidable. 2 ‘Theorem 1.3 is often described as the Urisolvabiliy of the Halting problem (for URM programs): there is no effective general method for discovering whether a given program running ona given input eventually halt. The implication of ths forthe theory of computer programming is ‘obvious: there canbe no perfectly general method for checking programs to see if they are fre from possible infinite loops. ‘The undecidable problem ‘re W.” of theorem 1.1 is important for several reasons. Among these is the fact that many problems can be shown to be undecidable by showing that they are at least as dificult as this one. We have already done this ina simple way in showing thatthe Halting problem is undecidable (theorem 1.3): this process is known as reducing one problem to another1 Undecidable problems in computability 103 Speaking generally, consider a problem M(x). Often we can show that a solution to the general problem M(x) would lead to a solution to the general problem ‘xe W,’. Then we say that the problem ‘xe W," is reduced to the problem M(x). In other words, we can give a decision procedure for “x € W," ifonly we could find one for Mr). In this case, the decidability of M(x) implies the decidability of ‘x © W.’, from which we conclude immediately that M(x) is undecidable. The s-m-n theorem is often useful in reducing “xe W,’ to other problems, as illustrated in the proof of the next result. 14. Theorem The problem “6, =O" is undecidable. Proof. Consider the function f defined by ° itxe Wa FO)" Vndefined ifxe W. We have defined f anticipating that we shall use the s-m-n theorems thus we are thinking of x as a parameter, and are concerned about the functions g, where g.(y)~ (sy). We have actually designed f so that an0o re W, By Church’ thesis (or by substitution using @ and dy) fis computable; so there is a total computable function k(x) given by the s-m-n theorem such that f(x, y)= decxi(¥);1.€. duix) = Se Thus from the definition of f we see that O xeW, © bu Hence, a particular question Isx ¢ W.? can be settled by answering the question Is 4,4)= 0? We have thus reduced the general problem ‘x e W,” to the general problem “é, = 0'; the former isundecidable, hence sos the latter, as was to be proved Let us present the final part of this argument in more details its the first example ofits kind, Let g be the characteristic function of", ft it,=0, 0 itd #0. ‘Suppose that g is computable; then so is the function h(x) = g(k(x)). But from (*) above we have {2 {train Osho. r6 ty 0 if diay AO ie. re We. atx) hw6 Decidability, undecidability and partial decidability 104 So by theorem 1.1 h is nor computable. Hence g is not computable, and the problem ‘d, =0" is undecidable. C1 From theorem 1.4 we can see that there are inherent limitations whenit ‘comes to checking the correctness of computer programs; this theorem shows that there can be no perfectly general effective method for check- ing whether a program will compute the zero function. By adapting the proof of theorem 1.4 we can see that the same is true for any particular computable function (see exercise 1,8(1i) below). ‘The following easy corollary to theorem 1.4 shows that the question of whether two programs compute the same unary function is undecidable. Again there are obvious implications for computer programming theory. 13. Corollary The problem ‘dr, = 6,” is undecidable, Proof. We can easily see that this isa harder problem than the problem Let ¢ be a number such that ¢.=0; if f(x, y) is the characteristic function of the problem 4, =¢,, then the function g(x) = f(x, c) is the characteristic function of “d, = 0". By theorem 1.4, g is not computable, so neither is f. Thus “d, = 4," is undecidable. ‘We use the s-m-n theorem again to reduce the problem ‘x ¢ W,’in the following results. 1.6. Theorem Lete be any number. The following problems are undecidable. (a) (the Input or Acceptance problem) ‘ce W,” (equivalently, “P(e or ‘ce Dom(¢,)"), (8) (the Output or Printing problem) ‘c « E,’ (equivalently, ‘ce Ran(,)’). Proof. We are able to reduce ‘re W,’ to these problems simul- taneously. Consider the function f(x, y) given by fou={, veel undefined otherwise. (With the s-m-n theorem in mind, we are concerned about the functions ‘& where ge(y)=/lx, y): we have designed f so that ceDom(s,) €1 Undecidable problems in computability 105 x€W, © ceRan(g.).) By Church's thesis / is computable, and so the s-m-n theorem provides a total computable function k such that 0%, y)~bacu(y). From the definition of f we sce that 2 We > Wie) = Buin =N,50.¢€ Waco and € Bria and 2€ We > Wie) Exc) D, 80 € Waue) nd C Easy ‘Thus we have reduced the problem ‘x ¢ W;’ to each of the problems ‘ce W," and ‘cE,’ ‘Completing the proof of (a) in detail, we see that if g is the charac- teristic function of ‘ce W,’, then 1 ifxe Wy eer-(9 ieee. This function is not computable (theorem 1.1), so g cannot be compu table. Hence ‘c e W,” is undecidable. A detailed proof of (6) is similar. ‘We conclude this section with a very general undecidability result, from which theorems 1.4 and 1.6 follow immediately. It is another use of the s-m-n theorem to reduce ‘x e W.' 1.7. Theorem (Rice’s theorem) Suppose that Bs %,, and B @, €;. Then the problem “d, € 2" is undecidable. Proof. From the algebra of decidability (theorem 2-4.7) we know that “b.€" is decidable iff ‘4, ¢ €\B" is decidable; so we may assume without any loss of generality thatthe function fo that is nowhere defined does not belong to & (if not, prove the result for €:\). ‘Choose a function g ¢ &. Consider the function f(x, y) defined by 80) ifxe W, 0) "Vundefined —itxe W.. ‘The s-m-n theorem provides a total computable function k(x) such that fla, y) buio(y)- Thus we see that FEW. > buy Bie. dune Bs XE We D dun fori duet &. So we have reduced the problem ‘x ¢ W,’ to the problem ‘d, € 2” using the computable function k. Inthe standard way we conclude that'd, € 3" is undecidable.6 Decidability, undecidability and partial decidability 106 Theorem 1.4, for example, is obtained immediately from Rice's theorem by taking @={0}, and theorem 1.6(a) by taking @ {g¢€1:c €Dom(g)}. Rice’s theorem may be similarly applied in several of the exercises below. 18. Exercises 1. Show that the following problems are undecidable. (a) ‘xe E,’ (Hint. Either use a direct diagonal construction, or reduce ‘x € W,” to this problem using the smn theorem), (b) ‘W. = W,' (Hint, Reduce ‘d, is total’ to this problem.), (6) ‘(x)= 0", (d) “d(y) = 0", (e) ‘xeE,, (/) “d,s total and constant’, (g) ‘W.= 2", (h) ‘Eis infinite’ (i) ‘db. =", where g is any fixed computable function, 2. Show that there is no total computable function f(x,y) with the following property: it P.(y) stops, then it does 50 in f(x, y) or fewer steps. (Hint. Show that if such a function exists, then the Halting problem is decidable.) Decidabitity and undecidability in other areas of mathema- tics In many areas of mathematics there arise general problems for which the informal idea of decidability is meaningful. Generally such problems involve finite objects from a particular field of study. The idea ‘of decidability of some property involving these objects can always be made precise using a suitable coding by natural numbers. Mauch research has been directed towards identifying both decidable and undecidable problems in a variety of mathematical situations: in the next sections we give a small sample of the results that have been obtained, 2. ‘The word problem for groups" Suppose that G is a group with identity element 1, and that Gis generated by a set of elements $={g1, 82 81-..)SG. A word on $ is * The reader with no knowledge of group theory should omit this section,3 Diophantine equations 107 any expression such as g3'g’gigge involving the elements of S and the sr0up operations. Each word represents an element of G, and to say that G is generated by S means that every element of G is represented by some word on S The word problem for G (relative to) is the problem of deciding for which words w on S is it the case that w There are many groups with decidable word problem: for example any finite group (with $ finite, of course). For many years mathematicians searched for an example of a finitely presented group with undecidable word problem. Eventually it was shown by Novikov in 1955 and Boone in 1957 that such groups do exist. Proofs of the Novikov-Boone Theorem are beyond the scope ofthis survey: the reader is referred to expositions in Rotman [1965] or Manin [1977]. Group theory, and modern algebra in general, abounds with interes- ting decidable and undecidable problems; a great many of them involve properties of words or generators akin to the basic word problem for rou, 3. Diophantine equations Suppose that p(x, t2,...%,) is a polynomial in the variables Xiy.++4Xq With integer coefficients. Then the equation Pia kaye for which integer solutions are sought is called a diophantine equation. Diophantine equations do not always have solutions: for instance the equation x7-2=0, Hilbert’s tenth problem, posed in 1900, asks whether there is an effective procedure that will determine whether any given diophantine equation has a solution. It was shown in 1970 by Y. Matiyasevich that there is no stich procedure; his proof was the culmination of earlier work by M. Davis, J. Robinson and H. Putnam, Actually Matiyasevich established rather more than the unsolvability of Hilbert’s tenth problem; the full Matiyasevich theorem and its appli- cation to Hilbert’s tenth problem are discussed in § 6. For complete details consult Davis [1973] or Manin [1977], or Bell & Machover (1977), * A group Gis finely presented if theresa finite sto generators S anda finite set 2B of relations ofthe form w = 1 (where sa word on ) such ha (al relations| in B are true in G, and (i) all other reltions holding in G ean be deduced from ‘those in B by using the proup axioms alone6 Decidability, undecidability and partial decidability 108 Sturm’s algorithm To redress the emphasis on undecidability in the previous two sections, we now mention a theorem of Sturm that gives us positive results. for computability and decidability in connection with the zeros of poly- nomials. 4.1, Sturm’ theorem ‘Letp(x) bea real polynomial, and letpo, Pis- of real polynomials given b) (a) po=®, Po =P? (6) ps=p' (the derivative of p), {¢) for 00 such that all the zeros of p lie in the interval ]~M, M[. In fact, if p(x)=ao+aix+...+a,x", the number + ans) suffices. Then by Sturm’s theorem the number of zeros of p is 6(-M)— ‘6(M) which may be calculated effectively. For (6), suppose that we are given a polynomial p and rationals a, b. To decide whether p has a zero in [a, 6}, first calculate p(a) and p(d); if neither of these is zero, calculate 8(a)~6(6) and apply Sturm’s theorem. Of course, Sturm’s theorem can be used to show that many other questions about polynomials over @ are computable or decidable. 43. Exercise Show that there is an effective procedure, given a polynomial p and rational numbers a, 6, for finding the number of zeros of p in [a, 6]. (Remember that a or & may be zeros of p.) 5. Mathematical loge Early investigations into the idea of effective computability were very much linked with the development of mathematical logic, because decidability was regarded as a basic question about any formalisation of ‘mathematics, We shall describe some of the results that have been obtained in this area, in general terms that do not assume any acquain- tance with mathematical logic. (The reader interested to learn the basics Of this subject may consult one of the many introductory texts, such as Margaris [1966],) The simplest logical system reflecting something of mathematical reasoning is the propositional calculus. In this calculus compound state~ ‘ments are formed from basic propositions using symbols for the logical connectives ‘not’, ‘and’, ‘or’, and ‘implies’. It is quite easy, once the6 Decidability, undecidability and partial decidabitity 110 propositional calculus has been carefully defined, to see that it is deci~ able. By this we mean that there is an effective procedure for deciding whether astatement o of the calculus is (universally) valid; ie. true in all possible situations, The method of truth tables gives an algorithm for this that will be familiar to many readers. ‘A logical system that has greater expressive power than the pro- positional calculus is the (first-order) predicate calculus: using the Tanguage of this calculus it is possible to formalise a great deal of mathematics. The basic statements are formed from symbols represen- ting individual objects (or elements) and predicates and functions of them. The compound statements are formed using the logical symbols of, the propositional calculus together with W and 3. There is a precise notion of a proof of a statement of the predicate calculus, such that a statement is provable if and only if tis valid.* In 1936 Church showed that provability (and hence validity) in the predicate calculus is undecidable, unlike the simpler propositional calculus. (This result was regarded by Hilbert as the most fundamental undecidability sesult for the whole of mathematics.) We can use the URM to give an easy proof of the undecidability of validity, although this calls upon a certain familiarity with the predicate calculus, We advise the reader who does not have a rudimentary know- ledge of predicate logic to omit the proof that we now sketch. 5.1. Theorem Validity in the first-order predicate calculus is undecidable. Proof. (Not advised for strangers to the predicate calculus.) Let P be a program in standard form having instructions [;,..., J, and let u = p(P) (as defined in chapter 2 § 2). We use the following symbols of the predicate calculus. (0 a symbol for an individual, "a symbol for a unary function (whose value at x is x’) Ra symbol for a (u+1)-ary relation, Xi9X29++ Xm ¥ Symbols for variable individuals, ‘The interpretation we have in mind is that 0 represents the number 0, ' represents the function x+1, and R represents the possible states of @ computation under P. Thusif we write 1 for 0',2 for 0", ete. the statement Rr. Fuk) 2 ‘This is desrited by saying thatthe notion of provablty is complete, and isthe content of Gisdels completeness theorem.5 Mathematical logic au where r1,... KEN means that the state n[nf-[.[o]o next instruction I, ‘occurs in the computation. Now for each instruction 1, we can write down a statement +, of the predicate calculus that describes the effect of Jon tates, using the symbol ‘for ‘and’ and - for ‘implies’: (a) if = Z(n) let 7 be the statement Wie, WE Ps Xs en DR Ose Han (6) If =S(n) let =; be the statement Wie, Wout Ps oe Xan Mie DPR oo Xl ees Keno (c) IF, =T(m, n) let 7 be the statement Wig, Wi ROK, Kap in RO ee Xe Ma (d) If 1,=3(m,n, q) let =; be the statement Wa 6 Wau! ROG5 5 May HI (Oks =u ROR oo Xie 1 Ohm FH ROG 2 Xue PDD. Now for any a eN let @, be the statement (on ti ns. Ate AR(@, 0,..-,0,1)) PBK Bx RO, he SED), where 7 is the statement VxWy((x' = y'>x=y) 4x’# 0). (This ensures that in any interpretation, if m, n €N and m=n then m =n.) The statement (a, 0, ...,0, 1) corresponds to a starting state alolo + next instruction Js, and any statement R(X:,...., X,,8+1) corresponds to a halting state (since there is no instruction /,,,). Thus we shall see that () Pla)l ¢ is valid. Suppose first that P(a)|, and that we have a structure in which 70, ..., and R(a,0,...,0, 1) hold. Using the statements 7p,..., 7, we find that ‘each of the statements R(ry,..., rusk) corresponding to the successive states in the computation also holds. Eventually we find that a halting Statement R(bs, ..., bu, 8+ 1) holds, for some by... by €Ny and hence Bra... Bx, RU, «Xap $1) holds. Thus or is valid.6 Decidability, undecidability and partial decidability 112 Conversely, if a is valid, it holds in particular in the structure N with the predicate symbol R interpreted by the predicate R, where Ralaiy.+++ue k) = At Some stage in the computation P(a) the registers contain a, 25...» @y)0,0,...and the next instruction is ‘Then 7,....7, and R(a, 0,.-., 0, 1) all hold in this structure, hence so does 3x1. 3x, RUXiy «+, Xe» $+ 1). Therefore P(a)t. If we take P to be a program that computes the function u(x, x), the equivalence (*) gives a reduction of the problem ‘x € W, to the problem sg is valid’, Hence the latter is undecidable. C1 The field of mathematical logic abounds with decidability and undeci- dability results. A common type of problem that arises is whether a statement is true in all mathematical structures of a certain kind. It has been shown, for example, that the problem ‘a is a statement that is true in all groups’ is undecidable (here « isa statement of the first-order predicate language appropriate to groups), whereas the problem ‘a is a statement that is true in all abelian groups’ is decidable. (We say that the first-order theory of groups is undecidable whereas the first-order theory of abelian groups is decidable.) It was shown by Tarski [1951] that the problem ‘ois true in the field of real numbers’ is decidable. On the other hand, many problems connected with the formalisation of ordinary arithmetic on the natural numbers are undecidable, as we shall see in chapter 8. For further examples and proofs of decidability and undecidability results in logic the reader should consult books such as Tarski, Mostowski & Robinson [1953], or Boolos & Jeffrey [1974]. 6. Partially decidable predicates Although the predicate ‘xe W," has non-computable charac- teristic function, the following function connected with this problem is computable: 1 tre Ws f00)-(ondetned itva We If we continue to think of 1 asa code for Yes, then any algorithm for fis a6 Partially decidable predicates. 113 procedure that gives answer Yes when x € W,, but goes on for ever when xe W, does not hold. Such a procedure is called @ partial decision procedure for the problem ‘x WV,", and we say that this problem or predicate is partially decidable. Many undecidable predicates turn out to be partially decidable: let us formulate the general definition, 6.1. Definition A predicate M(x) of natural numbers is partially decidable ifthe function f given by poet it M(x) holds, undefined if. M(x) does not hold, is computable. (This function is called the partial characteristic function for M) If M is partially decidable, any algorithm for computing fis called partial decision procedure for M. Note. In the literature the terms partially solvable, semi-computable, and. recursively enumerable* are used with the same meaning as partially decidable, 62. Examples 1, The Halting problem (theorem 1.3) is partially decidable, since its partial characteristic function 1 if) 15) Vundefined otherwise, is computable, by Church's thesis (or by observing that f(x, y)~ Aue»). 2. Any decidable predicate is particlly decidable: simply arrange for the decision procedure to enter a loop whenever it gives output 0. 3. For any computable function g(x) the problem ‘x €Dom(g)’ is, partially decidable, since it has the computable partial charac- teristic function 1(g(x)). (Cf. corollary 1.2.) 4. The problem ‘x« W,” is not partially decidable: for if fis its partial characteristic function, then xeDom(f) ¢ x¢ W, ‘Thus Dom(f) differs from the domain of every unary computable function: hence f is not computable. “Th 00 fo the use ofthis term will he explained in the next chapter.6 Decidability, undecidability and partial decidability 114 We proceed to establish some of the important characteristics of partially decidable predicates. First we have the alternative charac- terisation that is given essentially in example 6.2(3) above. 63. Theorem A predicate M(x) is partially decidable if and only if there is a ‘computable function g(x) such that M(x) if xeDomig). = 2H oo Fe MV Proof. It M(x) is partially decidable with computable partial charac- teristic function f(x), then from the definition we have M(x) iff x Dom({). The converse is given by example 6.2(3) above. The following characterisation of partially decidable predicates shows how they are related to decidable predicates. 64. Theorem A predicate M(x) is partially decidable if and only if there isa decidable predicate R(sx, v) such that M(x) iff 3yR(x, ). nen) Oo RT, Proof. Suppose that R(x, y) is a decidable predicate and that M(x) iff yR(x, y). By corollary 2-5.3 the function g(x)~ zyR(x, y) is compu- table; clearly M(x) & xeDom(g), 30 M(x) is partially decidable by theorem 6.3. For the converse, suppose that M (x) is partially decidable, with parti decision procedure given by a program P. Define a predicate R(x, y) by R(x, y) = Plx)L in y steps. By corollary 5-1.3, R(x, y) is decidable, Moreover, M(x) © Plx)) 2 Rix, y) as required. Note. From the appendix to chapter 5 it follows that the predicate R in this characterisation may be taken to be primitive recursive (see the note 1 following corollary 5-1.4) ‘The characterisation given by theorem 6.4 indicates an important way to think of partially decidable predicates. It shows that partial decision procedures can always be cast in the form of an unbounded search for a6 Partially decidable predicates 1s number y having some decidable property R(x, y). This search is most naturally carried out by examining successively y=0, 1,2,... to find such a y. The search halts if and when y is found such that R(x, y) holds; ‘otherwise the search goes on for ever. We can use theorem 6.4 to establish some further properties of partially decidable predicates, that aid us in their recognition. 65. Theorem If M(x y) is partially decidable, then so is the predicate ayM(x, y). Proof. Take a decidable predicate R(x, y,z) such that M(x, y) iff BzR(x, y, 2). Then we have ByM(x, y) & ByAzR(x, y,2). ‘We can use the standard technique of coding the pair of numbers y, z by the single number w= 23"; then the search for a pair y, z such that Rix, y,z) reduces to the search for a single number w such that RUx, (Wy (wa) ie. AyM(x, y) € BuR(, (uw), (ua). ‘The predicate S(x, u)= R(x, (us, (u)2) is decidable (by substitution) and, so by theorem 6.4 3yM(x, y) is partially decidable. Theorem 6.5 is described by saying that partially decidable predicates are closed under existential quantification. Its repeated application gives 6.6. Corollary IFM(sx, y) is partially decidable, where y = (y,... 5 ¥m)ythen sois the predicate By, ... BymM(%, Yay -+ +s Yn). Let us now consider some applications of the above results, 6.7. Examples 1. The following predicates are partially decidable. (a) x€E)" (n fixed). (The Printing problem: cf. theorem 1.6.) (b) W, # (Ct. exercise 1.8(18).) Proofs (a) xe By” eo By... 32, 30(Py(2i,-.., 29) Lx int steps). The Predicate in the brackets on the right is decidable; apply coro- Mary 6.6. (6) W.# ¢> 3y3r(P,(y)] in t steps); again the predicate in brackets is decidable, so corollary 6.6 applies,6 Decidability, undecidabitity and partial decidability 116 2. Provability in the predicate calculus is part for those who have read § 5), Proof. We proceed informally; in the predicate calculus a proof is defined as a finite object (usually sequence of state~ ‘ments) in such @ way that the predicate lly decidable (this is Pr(d, 0) ='d is @ proof of the statement a” is decidable. Then we have cris provable <> 3d Pr(d,o), hence ‘a is provable’ is partially decidable. 6.8. — Diophantine predicates (cf. § 3) Suppose that p(tiy.+.5%m Yiv++++Ym) is a polynomial with integer coefficients. Then the predicate M(x) given by M(x)= ys. Byia( PC Yas - +++ Ym)=0) is called a diophantine predicate, because of its obvious connection with diophantine equations. (The quantifiers 3y:,...,3¥m are taken as ranging over N.) Example The predicate ‘x is a perfect square’ is diophantine, since itis equivalent to 3y(x—y*=0). From corollary 6.6 we have immediately 6.9. Theorem Diophantine predicates are partially decidable, Proof. The predicate p(x, y) =0 is decidable; apply corollary 6.6. Clearly, diophantine predicates are partially decidable predicates that can be cast in a relatively simple form, and for a long time it was not known whether any undecidable diophantine predicates existed. This question is closely connected with Hilbert’s tenth problem (§ 3), as we shall see. It was a most remarkable achievement, therefore, when Mati- yasevich proved in 1970: 6.10, Theorem Every partially decidable predicate is diophantine. ‘The proof of this result by Matiyasevich rested heavily on earlier work of Davis, Robinson and Putnam, and is far too long to present here. Full6 Partially decidable predicates 47 proofs are given in Davis [1973], Bell & Machover [1977] and Manin [1977]. The major part of the proof consists in showing that diophantine predicates are closed under bounded universal quantification; ic. if ‘M(x, y) is diophantine then so is the predicate V2>0 such that x"+y"=2") (d) ‘There is a run of exactly x consecutive 73 in the decimal expansion of 2" (For those knowing some group theory) Show that the word problem for any finitely presented group is partially decidable. A finite set 5 of 3x3 matrices is said to be mortal if there is a finite product of members of S that equals the zero matrix. Show that the predicate ‘S is mortal’ is partially decidable. (It has been shown that this problem is nor decidable; see Paterson [1970]) Suppose that M(x) and N(x) are partially decidable; prove that the predicates ‘M(x) and N(x)’, ‘M(x) or N(x)’ are partially decidable. Show that the predicate ‘not M(x)’ is not necessarily partially decidable. Suppose that M(x, y) is partially decidable. Show that (a) ‘By 1), although in the text we shall (as is common practice) restrict the use of the term to subsets of N. There is no loss of generality in doing this, because recursive subsets of N" can easily be coded as recursive subsets of N. See exercise 1,4(2) below for details. 1.2. Examples 1. The following sets are recursive. @N, (b) E (the even numbers), (c) any finite set, (d) the set of prime numbers. 2. The following sets are not recursive. (a) {x: $e is total} (theorem 5-2.1), (b) (x: x W,} (theorem 6-1.1), (c) (x26, = 0} (theorem 6-1.4). The algebra of decidability (corollary 2-4.7) gives us the following properties of recursive sets immediately. 1.3. Theorem If A, B are recursive sets, then so are the sets A, ANB, AUB, A\B. Proof. Direct translation of corollary 2-4.7.. Further facts about recursive sets will emerge in § 2, 14, Exercises 1, Let A, B be subsets of N, Define sets A@B and A@B by A@B=(e:xeA}utetlixeB} A@B=(rlx,y)ix€A and y eB), where is the pairing function (x, y)= theorem 4-1.2. Prove that (a) AQ@B is recursive iff A and B are both recursive, (0) If A,B # 2, then A®B is recursive iff A and B are both recursive. "(2y+1)=1 of2 Recursively enumerable sets 123, 2. (a) Let B CNand let n > 1; prove that if is recursive then the predicate M(xi,..-5) given by MOGs cesta) = 2539. phe is decidable. () Let ASN’; define A to be recursive if the predicate. ‘xeA’ is decidable. Prove that A is recursive iff asm 2 y+ 9) Ab is recursive 2, Recursively enumerable sets ‘We turn now to the subsets of N that correspond to partially decidable predicates. These constitute an important class, if only because of the many situations in which they occur. 21. Definition Let A be a subset of N. Then A is recursively enumerable if the function f given by 1 ifrea, (0)=(ondetaed itveA is computable (or, equivalently, if the predicate ‘x A’ is partially decidable). The phrase recursively enumerable is almost universally abbreviated re. Notes 1. The terms semi-recursive sets and semi-computable sets are also used todescribe r.2. sets; indeed, from the above definition these names would appear more appropriate than recursively enumerable. We will, neverthe~ less, adhere to the standard name recursively enumerable, which stems from the fact that these sets may also be defined as sets that can be enumerated by a recursive (or computable) function, This alternative characterisation is given in theorem 2.7 below. 2. As with recursive sets, the idea of r.e. sets can be extended in the ‘obvious way to subsets of N" (n> 1), but there is no loss of generality in confining attention (as we do in the text) to r.e. subsets of N. See exercise 2.18(9) below. 22. Examples 1, Let K ={x:x ¢ W,}; then K is an rc. set that is not recursive. (example 6-6.2(1). Its complement K is not re. (example 6-6.2(4)). 2. Any recursive set i re, (example 6-6.2(2)7 Recursive and recursively enumerable sets 124 3. The set {x:W, # 2) is re. (example 6-6.7(1(b))) 4. If f is a computable function, then Ran(f) is r.e. (example 6-6.1(1a); cf. theorem 2.7 below). Note. K is the standard notation for the set {x: x € W,} (example 1 above), which plays a prominent role in the study of rc. sets. ‘Most of the results for partially decidable predicates in chapter 6 $6 translate immediately into the language of r.e. sets. We begin with 23. Theorem A setis re. if and only if itis the domain of a wnary computable function. Proof. Theorem 6-6.3. ‘We conclude from this theorem that the enumeration Wo, Ws, Way is an enumeration (with repetitions) of all r.e. sets. If A= W,, then e is called an index for A. From theorem 6-6.4 we obtain the next characterisation of r.e. sets. 2.4. Theorem The set A is re. ifand only if there isa decidable predicate R(x, y) such that xeA iff ByR(x,y). (From the note following the proof of theorem 6-6.4 this predicate R may be taken to be primitive recursive.) We also have the following immediately from theorem 6-6.5. 2.5. Theorem Suppose that M(x, Ys.-.-» x) iS partially decidable; then the set fe Byi.-- ByeM Ut yas eee Yah is nee ‘The following link between re, sets and recursive sets is an immediate application of theorem 6-6.11 26. Theorem ‘The set A is recursive if and only if A and A are re.2 Recursively enumerable sets 1s Proof. This is immediate from theorem 6-6.11, but it is instructive to give formal proof of the non-trivial half of the proof. Suppose then that Rand S are decidable predicates such that xeA © IyR(x,y) x4 © 3ySix,y) (we are using theorem 2.4). Now define a function f(x) by Fix) = wy(R(x y) oF $x, By the results of chapter 2, fis computable; further, since for every x, either x€A or xe A, f(x) is always defined, and we have xEA & R(x flr). Thus ‘xe A’ is decidable, so A is recursive. O ‘We now turn to the characterisation of r.e, sets that gives them their name. 2.7. Theorem Let ASN. Then the following are equivalent: (a) Aisr. (b) A= or A isthe range of a unary toral computable function, (c) Ais the range of a (partial) computable function. Proof. We shall prove the chain of implications (a) > (4) = (c) > (a) (a)> (6) Suppose that A#@ and that A=Dom(j), where f is computed by a program P. Choose an element a € A. Then A isthe range of the following total binary function: x if Plx)L in steps, BONG otherwi Clearly gis computable. To complete the proof we construct a unary total computable funetion h having the same range as g. Let f(z) = a(2)is(2hd- Clearly Ran(h) = Ran(g)= A. (6) > (cis trivial (c) > (a) Suppose that A=Ran(h) where A is an nary computable function. Then EA 6 By BVA »). ‘The predicate in brackets on the right is partially decidable (theorem 6-6.13) so applying theorem 2.5 we see that A iste.7 Recursive and recursively enumerable seis 126 (The reader may have noticed that various parts of this theorem have been given, more or less explicitly, in examples and exercises earlier in this and other chapters.) Notice that it is from theorem 2.7(6) particularly that the name recursively enumerable comes: a non-empty r.e. set is a set that can be enumerated as A ={h(0), h(1), 4(2), ...} where h isa recursive (i.e. total computable) function. In fact, by using the results of chapter 5 (and appendix) itis easily seen that the enumerating function h in the proof of (a) > (b) is primitive recursive. Note also that theorem 2.7 tells us that the enumeration Eo, Ey, E>, of the ranges of unary computable functions is another enumeration (with repetitions) of all re, sets. In informal terms, theorem 2.7 shows that rc. sets are the same as effectively generated sets. We would call a set A effectively generated if there is an informal effective procedure for compiling a list of the members of A. Such a procedure would from time to time (not necessarily at regular intervals) output a number to be added. to the list, The procedure may go on ad infinitum (and certainly must if A is infinite). To see that a set A generated in this way is re., simply put 700) Ast number listed by the procedure, fn) =(n+1)th number listed by the procedure, where fin) is defined iff there is an (n+ 1)th number listed. Then clearly f is computable, and A= Ran(/) is 1. ‘We can illustrate this with an example. 2.8. Example ‘The set {x:there is a run of exactly x consecutive 7s in the decimal expansion of =} is re. (cf. exercise 6-6.14(1d)). The following is an informal procedure that generates this set of numbers. ‘Run an algorithm that computes successive digits in the decimal expansion of 7. Each time a run of 7s appears, count the number of consecutive 7s in the run and add this number to the list.” ‘The characterisation of theorem 2.7 gives usa straightforward diagonal proof that total computable functions cannot be recursively enumerated, 29. Theorem The set {x:by is total) is not re.2 Recursively enumerable seis 127 Proof. (Cf. the suggested proof of this result given in exercise 6- 6.14(70).) Suppose to the contrary that f is a total unary compu- table function that enumerates this set; Le. dyoy days Gray «18a list of ail unary computable functions. Then we can easily make a diagonal construction of a total computable function g that differs from every function in this list, The diagonal motto says ‘make g differ from dyn) at nn’, $o we put 8) = dala) +1. Then g is computable and total, but ¢¥ yim for every m. This is a contradiction. ‘There is one important result about partially decidable predicates that ‘we have so far omitted to transfer to the setting of re. sets, namely the connection with diophantine predicates. First we make a definition, 2.10. Definition A set AGN is diophantine if there is a polynomial (x, Yay +++ Yu) With integer coefficients such that EA ih Sys. Bya pCa yas ees Ya) =O). Of course, diophantine sets are r.e., and Matiyasevich’s theorem (6-6.10) may be expressed (as it often is) as: 2.41. Theorem (Matiyasevich) Alll re. sets are diophantine. This is an appropriate place to mention a surprising (but easy) consequence of Matiyasevich’s theorem, 2.12, Theorem A set is re. if and only if it is the set of non-negative values taken by some polynomial p(x, -.« 5%») with integer coefficients (for values Of X15. + vn from N). Proof. Suppose that A is the set of non-negative values taken by DRiysvey Hels then ¥EA > 3x1... Bte(pltinee ssa) =H), 80 A is clearly re. Conversely, if A is re. then by Matiyasevich’s theorem there is a polynomial q(x, ys,..-» Ym) such that EA © yy... Byml (ts Fy ++ Yn) =O).7 Recursive and recursively enumerable sets 128 ‘Then consider the polynomial p(x, y) given by psy) p(x; y) is non-negative if, and only if, q(x, y)=0, and then it takes the value x. Thus A is the set of non-negative values taken by p(x, y) as XYiye+y 3m Pun through N.C tat (The restriction of x), .., x, 10 Nin the statement of this theorem is, somewhat arbitrary; itis an easy exercise to see that the theorem is valid when x1,..-,%, are allowed to range over Z.) ‘One application of this result that has aroused considerable interest among mathematicians isto the set of prime numbers: this set, being rc., is the set of positive values taken by a polynomial with integer coefficients, a result thought to be most unlikely before Matiyasevich came on the scene. ‘A refinement of theorem 2.12 shows that there is a single universal polynomial, which generates all re, sets; ic. a polynomial PC2,%, Yis-+ Yon) With the property that for any re. set A there is a number z such that © BY. Bm PLE, 4 Yay ++ Yn) =O) Tosee this, simply note that the Halting problem ‘xe W, "is diophantine and take z to be an index for A. At this stage we should summarise the various characterisations of re. sets that we now have available. The following are all equivalent condi- tions on a set A of natural numbers: (1) ‘xe A’ is partially decidable (we have taken this as our basic definition), (2) Ais the domain of a unary computable function; ie. A = W, for some ¢ (theorem 2.3), (3) For some decidable predicate R(x, y), xe A By Rix») (theorem 2.4), (4) For some partially decidable predicate M(x, yi, X€A © By... ByeM(x, y,--- 5 Ya) (theorem 2.5), (5) ILA 4, A isthe range of a total unary computable function (theorem 2.7), (6) A is the range of a computable function (theorem 2.7), (7) A is diophantine (theorem 2.11), (8) A is the set of non-negative values taken by a polynomial with integer coefficients (theorem 2.12). Yad2 Recurisvely enumerable sets 129 Naturally, when working with re. sets one chooses the characterisation that is most convenient for the purpose in hand. We illustrate this in the proof of the next theorem. 2.13. Theorem IA and B are re., then so are ANB and AUB. ‘Proof. For A7B use characterisation (2). Suppose that A = Dom(/) and B= Dom(g) with f, g computable. Then AmB = Domi fg), and fg is computable For A UB use characterisation (5). If A = @ or B = @ there is nothing to prove. So suppose that A = Ran) and B = Ran(g) where f,g are total computable. Define kt by hQx)=flr), hQx+1)=gt0. Then h is computable and clearly Ran(i)= AUB. {Ivis instructive to find proots for this theorem using each of the other characterisations of re. sets.) ‘Our next theorem gives another link between re. sets and recursive sets, 2.14. Theorem An infinite set is recursive if and only if it is the range of a total increasing computable function, ie. if it can be recursively enumerated in increasing order. Proof. Suppose that A is recursive and infinite; then A is enumerated by the increasing function f given by £(0)=ny(ye A), fin+1)=nyly eA and y>f(n)) Morcover, fis computable by minimalisation, recursion and the recur- siveness of A. Conversely, suppose that A is the range of the computable total increasing function f; ie. (0) a(n). Since A=Ran(f) is infinite, g is totally defined. By construction, Ran(g) suite ee dint th 2€K > buas=f (hence dyn)€ a) Forif z €X, there is such that P(z)1 in steps. Then g(z,')~ ya) i undefined for 1’ = r. Hence dis fnite. On the other hand, if 2# K, then 8(2,1)=fl) for all 1,50 duay=f- _ Now (*) means that z © K ¢> s(z)€A, which implies that K is re. @ contradiction, Hence there must be a finite 0 f with 8 of For the reverse implication, suppose that f is a computable function, such that there isa finite function @€f with #S/, but fé sf, Define a computable function g(z,1) by fo itreDom(a)orz eK, undefined otherwise 0 al = ‘The s-m-n theorem provides a total computable s(z) such that (2, #)~ (0). From the definition of g and the fact that @< / we see that 2EK > buy=f (hence by)€ 5A)7 Recursive and recursively enumerable sets 132 and 2€K > b.)=f|Dom(8)=6 (hence $,(2)€ af). But this means that z¢K © s(z)€ A, again showing that K is r.e., a contradiction. Thus ff as required. 0 We leave it as an exercise for the reader to see how the Rice-Shapiro theorem generalises Rice’s theorem (exercise 2.18(12) below), 218. Exercises 1, For any a EN, let °W. ={x:6,(x) }. Show that “W, is re. (all a). Does the enumeration “Wo, “Wi, “W2,... include all r.c. sets? 2. Show that the set fx: is not injective} is ne. 3. Show that there are total computable functions k ! such that for every x, We = Eqn and E, = Wi 4. Suppose that A is an r.e. set. Show that the sets ea Ws and Usea Es are both re. ‘Show that eax Ws isnot necessarily r.. as follows. For any ¢ let K, = {x:P,(x)J in ¢ steps}. Show that for any ¢, K; is recursive; moreover K = Une K, and K = (hen Re 5. Let f be a unary computable function, and suppose that Ac Dom(/), and let ¢=/|A. Prove that g is computable iff A is r.e. 6. Let f be a unary function. Prove that f is computable if the set {(2°3!:xDom(f)}is re, 7. (Cf. theorem 2.14.) Let A be an infinite re, set. Show that A can be enumerated without repetitions by a total computable function Which of the following sets are recursive? Which are re.? Which have re. complement? (a) (exeE), (8) (e:x isa perfect square), (c) {x:0, is injective}, (d) {xthere is a run of atleast x consecutive 7s in the decimal expansion of z), —(e) {x:Pra(x)t} (rm is fixed). 9. (Cf. Exercise 1.4(2).) (a) Let B CN and let n> 1; prove that if B is r.e, then the predicate M(xy,....,%,) given by MGs.) =253".. pheB is partially decidable.3. 3 Productive and creative sets 133 (b) Let ACN’; define A to be re. if the predicate ‘re A’ is partially decidable. Prove that A is r.c. iff (283%... pir Oise tad EAL iS re. (c) Prove that AGN" is re. iff A=@ or there is a total computable function f:N=N" such that A=Ran(f). (By a computable function f irom N to N* we mean an n-tuple f= (fivs+eofn) Where each fi is a unary computable function and 102) = (fale, = fal))») 10, Suppose that f is @ total computable function, A a recursive set and B an re. set. Show that f-'(A) is recursive and that f(A), #(B) and f-"(B) are re, but not necessarily recursive. What extra information about these sets can be obtained if f isa bijection? 11, Use the Rice-Shapiro theorem to show that the following prob- lems are not partially decidable: (a) *W. = ©’, (8) *W. is finite’, (c) Wz is infinite’, (d) b, = 0, (e) “dy #0" 12. Prove Rice’s theorem (theorem 6-1.7) from the Rice-Shapiro theorem (theorem 2.16). (Hint, Suppose that °d, € @" is deci dable; then both B and %:\B satisfy the conditions of Rice~ Shapiro: consider the cases fae @ and foe B.) 13. (a) Let Ko= (x: G(x) = O} and Ky ={x:,(x)= 1}. Show that Ko and K; are r.e., and that they are recursively inseparable, i.e. Kon K,= © and there is no recursive set C such that Kos C and Kic C; in particular neither Ko nor K; is recursive. (Hint. ‘Suppose that there is such a set C and let m be an index for its ‘characteristic function; consider whether or not m ¢ C.) (b) Show that two disjoint sets A, B are recursively inseparable (in the above sense) iff whenever Ac W,, BS Wy and Wa Ws= 2 then there is a number xe W,UW;. (Note. Recursive inseparability for a pair of disjoint sets corresponds to non- recursiveness for a single set; pairs of recursively inseparable sets that are also r.. correspond to r.e. sets that are not recursive.) Productive and creative sets (Our chief concern in this section is to discuss a special class of re sets called creative sets. These are r.e. sets whose complement fails to be re, in a rather strong way. Thus we begin by considering a class of non-r.e, sets, among whose complements creative sets are to be found. ‘Suppose that A is any set that is not re.; then if W, is an r.e. set contained in A, there must be a number y¢A\ W,, This number y is a witness to the fact that A # W,. Itturns out that for some non-r.¢. sets it is7 Recursive and recursively enumerable sets 134 possible to find such a witness in an eflective way. Consider, for example, the non-r.c, set K = {x:x¢ W,}. If We K, we cannot have xe W, (for then xeK, 80 W,2K); hence x¢K\W,. So x itself is a witness that W, # K. ‘The name productive is used to describe non-r.e. sets for which a witness can always be computed in this way. 3.1, Definition A set A is productive if there is a total computable function g such that whenever W, A, then g(x)€A\ W,, The function g is called a productive function for A. This i illustrated by fig. 7a. Example. The set Ris productive, with productive function g(x Many examples of productive sets are obtained from the following theorem, which incorporates the idea of reducibility that was discussed in the previous chapter. 3.2. Theorem Suppose that A and B are sets such that A is productive, and there is @ total computable function f such that x€A iff flx)eB. Then B is productive. Proof. Let g be a productive function for A. Suppose that W. < B. Then f-'(W.)S"(B) =A; moreover, f-"(W,) ise, $0 there is z such that f-"(W,) = W,, Now W. < A, and so g(z)€A\ W., from which we see Fig. Ta. A productive set +)3 Productive and creative sets 135 Fig. 7b, Theorem 3.2. a > sale) ofgi2 that f(g(z))¢B\ W,; ie. f(g(2)) isa witness to the fact that W, # B (fig. 7b). ‘We now need to obtain the witness f(e(=)) effectively from x. A simple application of the s-m-n theorem provides a total computable function k(x) such that Wi) =/"'(1¥4) (apply the s-m-n theorem to the function {6,(/(y))). Then putting 2 = k(x) we see from the above reasoning that if W, < B then f(g(k(x)))¢ B\ W,. Hence B is productive, with productive function fig(k(x)). 3.3, Examples The following sets are productive: (a) (eb. #0), (b) (x:cé Wa} (c a fixed number), (e) {x:c@ Ey} (c a fixed number). (For each of these sets apply theorem 3.2 using K and the functions obtained in theorem 6-1.4 (for (a)) and theorem 6-1.6 (for (b) and (c)).) ‘The above examples of productive sets and many more may be ‘obtained from the following general application of theorem 3.2, based on ‘our proof of Rice's theorem. 3.4, Theorem Suppose that B is a set of unary computable functions with foe B and @ # €;. Then the set B ={x:6, € B) is productive. Proof. Choose a computable function g# ®. Proceeding exactly as in the proof of Rice's theorem (6-1.7) obtain a total computable function7 Recursive and recursively enumerable sets 136 (x) such that daore ixeK, Paw ifreK. Le.x eX iff k(x)e B. By theorem 3.2, B is productive. 0 35. Example The set {x:d, is not total} is productive, immediately from theorem 3.4. Our chief interest in productive sets is when they occur as the comple- ment of an re. set 36. Definition Aset A is creative if it isr.c. and its complement A is productive. The simplest example of a creative set is of course K. Using theorem 2.6 we can say that a creative set isan r.¢, set that fails to be recursive in @ very strong way. We will see in chapter 9 that there is a sense in which creative sets are the r.e. sets having the most difficult decision problem. 3.7. Examples The following sets are creative (a) {x:¢ € W,}| (the complements of these sets were (6) (x: ec E,}J shown to be productive in examples 3.3). (c) The set A={x: d(x) =0}, Clearly A is r.e.; to obtain a productive function for A, use the s-m-n theorem to construct a. total computable function g such that bal) =0 € d.(y) is defined. Then g(x)€A € g(x) W,; 80 if W, SA we must have g(rje A\W,. Thus g is a productive function for A, Many examples of creative sets of indices are provided from the following application of theorem 3.4, 3.8. Theorem Suppose that sf ©%, and let A=(xid_€ ol}. If A is ne. and A#@ orN, then A is creative. Proof. Suppose that A is re, and A¥@,N. If foe. then A is Productive, by theorem 3.4; this is a contradiction. Thus f.x€ sf, so A is Productive (theorem 3.4), hence A is creative. O3 Productive and creative sets 137 The examples 3.7(a), (b) could be obtained by immediate application of this theorem: similarly we have: 39. Example The set A= (x: Ws # 2} is creative; this et is obviously re. and corresponds to the set of ={fe €1:/+ fa}. Many of the exercises at the end of the section may be done with the aid of theorem 3.8 Allexamples of non-recursive re. sets that we have encountered so far are creative. (The reader might care to prove this for the examples that we have not dealt with explicitly.) The question then arises as to whether all non-recursive re, sets are creative, The idea that this might be the case is reinforced by theorem 3.8, and further examples in the exercises below. It turns out, however, that this conjecture is false: by a special construction we can obtain re. sets that are neither recursive nor creative. Section 4 will be devoted to that task. ‘The construction to be made in the next section is inspired by theorem 3.11 below, which will show that a productive set (and hence the complement of a creative set), although not itself re., does contain an infinite re, subset. (The secret of constructing ane. set A that is neither recursive nor ereative will be to ensure that A does nor have this property.) ‘The proof of the theorem will be facilitated by first isolating the following technical result. 3.10. Lemma Suppose that g isa total computable function. Then there isa total computable function k such that for allx, Ways)= We Uig(x)} Proof. Using the s-m-n theorem, take k(x) to be a total computable function such that tueis)={ ifye Wory=six), “ undefined otherwise. O 3.11. Theorem A productive set contains an infinite re, subset Proof. Let A be a productive set with productive function g, The idea is to enumerate without repetition an infinite set B = {yo, yi,--.}< A inthe following way.7 Recursive and recursively enumerable sets 138 (1) Take ep such that Wie=@; since W,,2x;in that case put f(x) = ¢,(z). (Formally we have fle)=be(uz(bAz)>2x)), demonstrating clearly that f is computable.) Put A=Ran(/); then A is re. We now verify that A is simple. Suppose that B is any infinite rc. set, Then there i foal computable function ds such that B = E,, Since B is infinite, the construction ensures that f(b) is defined and f(b)e Ey = B. Hence Be A. “To see that A is infinite, note that if f(x) is defined, then flx)>2x Thus, for any n, the members of A that are inthe set(0, 1,2, 2hare among (0)-..,flr—1), This means that A contains more than 1 elements, for any n. Hence Ais infinite, ‘The construction of a simple setis but the first and one of the easiest of a wide variety of constructions that yield re. sets with all kinds of special properties. These are beyond the scope of this book; the interested reader should consult a text such as Rogers [1967], where he will find r.c. sets rejoicing in names such a hypersimple, hyperhypersimple, pseudocrea~ tive, and maximal. (See also exercise 4.4(3) below for an example of an re. set that is neither recursive, creative nor simple.) 44, Exercises 1. Suppose that A and B ate simple sets. Show that the set A@B is ‘simple. (For the definition of @ see exercise 1.4(1).)7 Recursive and recursively enumerable seis 142 . Suppose that fis a total injective computable function such that Ran({) is not recursive. (Exercise 2.18(7) showed that such functions abound.) Show that the set A={u:By(y>x and f(y) f(y1)>fly2)>-.- To see that A does rot contain an infinite re. set B, suppose to the contrary that BA, Then show that the problem z ¢ Ran(f) is decidable as follows. Given z, find n € B such that f(n) > 2; now use the fact that mé A to devise a finite procedure for testing whether z € Ran(f).) . Show that if A is simple, then A @Nisre., but neither recursive, creative nor simple (see exercise 3.13(6)), . Let A, B be simple sets, Prove that A@Bi is not simple but that A@Bis simple.8 Arithmetic and Gédel’s incompleteness theorem ‘The celebrated incompleteness theorem of Gadel [1931] is one of many results about formal arithmetic that involve an interplay between computability and logic. Although full proofs in this area are beyond the scope of this book, we are able to outline some of the arguments discovered by Gadel and others. We shall highlight particularly the part played by computability theory, which in many cases can be viewed as an application of the phenomenon of creative and productive sets. In§§ 1 and 2 we present some results about formal arithmetic that lead up to the full Gédel incompleteness theorem in § 3. In the final section the question of undecidability in formal arithmetic, already touched upon in §1 is taken up again. Our presentation in this chapter does not assume any knowledge of formal logic. 1, Formal arithmetic ‘The formalisation of arithmetic begins by specifying a formal logical language Z that is adequate for making statements of ordinary arithmetic of the natural numbers. The language L has its own alphabet, ‘which includes the symbols 0, 1, +, x, = (having the obvious meanings), and also symbols for logical notions as follows: ~ (‘not’), « (‘and’), v Cor’), (implies), ¥ for all), 3 (‘there exists’) (In this chapter we will reserve the symbols V, 3 for use in L, and write the phrase ‘for all’ and “‘there exists’ when needed in informal contexts.) In addition, L has symbols x,y, 2, for variables, and brackets (and), and there may be other symbols besides. ‘The statements (or formulas) of L are defined to be the meaningful finite sequences of symbols from the alphabet of L. For instance, the statement ayyx(1+1)=%) is the formal counterpart of the informal statement ‘x is even’. Itis helpful8 Arithmetic and Gédel’s theorem 144 to abbreviate the expression 141 by 2, (1+1)+1 by 8, andso on forall natural numbers, Then the false informal statement is even’ would be expressed formally in L by the statement | Bylyx2=5) We can similarly express in L formal counterparts of many informal | statements of ordinary arithmetic: for ‘x > y" we would write Be(42=0) aly +z=x)). (The statement “(2 = 0) is often abbreviated by 2# 0.) For ‘x is prime” we would write | | (#0) a(x# 1) a ¥yWelx=yxz-(y=1v2=1)), Let us denote by / the set of all possible meaningful statements of the language L. Then divides into two important sets, namely ordinary arithmetic of N, F =the set of all statements that are false in the ordinary arithmetic of N Mathematicians would like to discover as much as possible about the set J. A natural question from the point of -w of computability is (1.1)(a) Is F recursive, or even recursively enumerable? Another question, important for the mathematician and philosopher alike is (1.1)(6) Is there a simple-minded subset of 7 (a set of axioms) from which all other statements in J can be proved? We shall discover that the answer to both of these questions is no. Question 1.1(a) above can be made precise by means of a standard coding procedure. It is quite routine to specify an effective enumeration of the set ¥, without repetitions, using a procedure similar to that used to ‘enumerate programs in chapter 4. Let us assume that this has been done, and let us denote by 6, the (n+ 1)th statement of Yin this enumeration, so that P= {005 1, +}. The effectiveness of this enumeration means that given n we can cflectively find and write down the statement @,, and conversely, given any statement o in / we can effectively compute the code number n such that o = by ‘J = the set of all statements that are true in the }1 Formal arithmetic 14s ‘This coding of statements is now used to code any set of statements by the set of numbers X= (0:62), recursive recursive re. re. We say that 2 is productive} if X is) productive creative creative ete. ete. ‘This gives the question 1.1(a) above a precise meaning. One of the key results that makes computability an extremely useful tool when investigating formal arithmetic is the following, due to Godel; we present it without any proof. 12. Lemma Suppose that M(x, ..-+%q) is a decidable predicate. Then itis possible 10 construct a statement o(Xi,.++4%q) of L that is a formal counterpart of M(xyy «+. %x) inthe following sense: for any dy... dq EN Maryse) holds if o(81,.-+4 8) EF. Consider now the creative set K. By theorem 7-2.4 there is a decidable predicate R(x, y) such that xeK © thereis y such that R( y) Applying lemma 1.2 to the predicate R(j; y) let us fx on one particular formal counterpart of this predicate, which we denote by v(x, y). Then for any m€N the statement Ayoq(n.y) is a formal counterpart for ‘n€K", and 73ycg(n, y) is a formal counterpart of ‘n# K". Let us therefore write neK for 3yza(n.y) and nek for —3yax(n,y). ‘Then using lemma 1.2 we have immediately 13. Lemma Forany neN (a) neKiffneKe T (6) neK iff neKeT We are almost ready to answer the question 1.1(a) above; we shall need the following lemma.8 Arithmetic and Gédel’s theorem 146 14, Lemma There is a total computable function g such that for all n By) is nek Proof. This is immediate from the effectiveness of the coding of statements, since given n we can effectively write down the statement neK(=73yon(n,y). Now we have, in answer to question 1.1(a): 1.3. Theorem Fis not res in fact F is productive. Proof. Let T = {n:0,¢T}; taking g as in lemma 1.4 we have neR @neK @ neKe F (by lemma 1.3). gin)e T(by lemma 1.4), So, since & isnot re., neither isT. In fact, by theorem 7-3.2 we see that T is productive. O 1.6. Exercise Show that # is productive, 2. Incompleteness A simple version of Gédel's incompleteness theorem follows easily from theorem 1.5. We must first describe the setting ofthis famous result. Consider the second question (1.1(6)) posed in § 1. This question is made precise by using the idea of a formal system. A formal system (sf, 2) (for the language L) consists of a set of < ¥ (the axioms) and an explicit definition 9 of the notion of a formal proof of a statement in ¥ from these axioms, satisfying the conditions: (2.1) (a) Proofs are finite objects (hence capable of being coded), (6) The explicit definition 2 of proof is such that if sf is recursive then the relation ‘p is a proof of the statement o from the axioms of” is decidable. ‘We can now interpret the question 1.1(b) as asking whether there is a formal system for L such that (2.2) (a) of is recursive (so we are taking simple-minded in a fairly wide sense), (b) The provable statements are precisely those in 7.2 Incompleteness 147 ‘the condition (6) poses a problem for the philosopher who may be trying to define the very notion of arithmetic truth by means ofa formal fystem. For him, this condition is meaningless, and must be replaced by fonditions reflecting some of the properties to be expected of truth, such as (2.2)(0")Consistency: there is no statement g such that both « and are provable, (2.2) Completeness: for any statement g, either & is provable or “0 is, provable. A simplified version of Gédel’s theorem shows that there is no formal system of arithmetic satisfying the conditions 2.2(a) and (b). This is easily derived from theorem 1.5, andis given below. The full theorem of Gédel [1931] together with its improvement by Rosser shows that there is no formal system of arithmetic (of a certain minimal strength) satisfying conditions 2,2(a) and (6'), (b"). In other words, any consistent formal system of arithmetic having a recursive set of axioms is incomplete. This will be proved in §3 ‘We shall need the following lemma to establish the simplified Gadel theorem, 23. Lemma In any recursively axiomatised formal system the set of provable statements is re. Proof. Let P+ be the set of statements in that are provable. Since roofs are finite, they can be effectively numbered; then if sf isa recursive set of axioms the predicate M(x, y)='y isthe number of a proof of 4, from the axioms sf” is deci ble, by (2.1)(4). Then 6, isprovable <> there is y such that M(x, y) holds. Hence, by theorem 7-2.4, Prisre. O Now we have 24. Theorem. (The simplified Gédel incompleteness theorem) Suppose that (sf, 2) is a recursively axiomatised formal system in which all provable statements are true. Then there is a statement «that is true but not provable (and consequently 0 is not provable either).8 Arithmetic and Gédel’s theorem 148, Proof. By lemma 2.3, the set P+ of provable statements is r.e., and we are given that Ps c J. Now 7 isnot re. (theorem 1.5) 0 we immediately have a statement o ¢ T\P+; ie. o is true but not provable. Clearly “wis not provable either (otherwise —w would be true). (Using the productiveness of 7 (theorem 1.5) we could strengthen this theorem to say that the statement o can be obtained effectively from a specification of the formal system (which would yield an index for Ps).) To aid an understanding of the proof of the full Gadel theorem in § 3 it is useful to examine the inner workings that were hidden when we applied theorem 1.5 in the above proof to obtain the statement. Let us say that a statement is refutable if its negation is provable. Consider the sets of numbers Pr* and Ref* given by Pr? ={n:neK is provable}, Ref =(n:neK isrefutable) ={n:m€K is provable) ={n: Gym) PPh (where g is the computable function given by lemma 1.4 and used in the proof of theorem 1,5), The assumption that provable statements are true ‘means in particular that Pr* < K and Ref* & K. Now Ref ise. (from the fact that n ¢ Ref* ey) € Px, and Pr is re.) so there is @ number m such that Ref* = Woy. By the productiveness of K we have immediately that me K\Ref*, i.e. mé K, and me K is not provable. Taking o to be the statement mé K wwe thus see that ois true but not provable (and ~vc is not provable, as before). The argument is illustrated by fig. 82. (For comparison with the Fig, 8a. Simplified Godel incompleteness (theorem 2.8),3 Gidel’s incompleteness theorem 149 proof of the full Gédel theorem in the next section, note that the non-provability of —o can be seen as a consequence of the fact that Pr'cK: for me K (as above), so méPr*, ic. meK is not provable Then, by the rules of formal proof —méK (i.e. “@) is not provable.) Notice now the intended meaning of the statement ¢ thus obtained: a jsthe formal counterpart of the statement mé K, je. me Wy. Butwe have md Wm 69 me Ref* <2 MEK is not provable 2th Thus o is a formal counterpart of the statement ‘g is not provable’; ie. speaking rather loosely, «says ‘I am not provable’. Thisis reminiscent of the paradox of the liar, involving the informal statement A='Lam lying’ Informal reasoning about A results in the paradox Aistrue iff A isnot true. Ifthe same informal reasoning is applied to the informal statement ‘Lam not provable’ the paradox is avoided by the conclusion that provable is not the same as true. This informal conclusion is rigorously justified by the proof of theorem 2.4. 3. Géder’s incompleteness theorem We proceed in tis ection to show how the idea behind the proof ‘of theorem 2.4 can be refined so as to avoid any reference to truth, For the moment we fix on a particular formal system of arithmetic known as Peano arithmetic. The axioms for this system consist of a recursive subset of ¥ known as Peano’s axioms: these reflect the simple properties of the successor operation ont, and the recursive definition of Addition and multiplication in terms of it, together with an axiom scheme reflecting the principle of induction on N. The notion ofa formal proof is taken as that defined for the first-order predicate calculus. Full details of Peano arithmetic (sometimes called forma! number theory) may be found in any textbook on mathematical logic. For our purposes, the important fact we need to know about Peano arithmetic is given by the following Jemma, to which a substantial part of Gédel's proof is devoted. 3.4. Lemma Let M(x, ..., x) be a decidable predicate, and let o(Xi..--+%x) be the statement of L that is the formal counterpart of M(x1y.+++%q) aS8 Arithmetic and Gédel’s theorem 150 siven by lemma 1.2. Then M is represented in Peano arithmetic in the following sense: for any a1,..+5 dq €N (a) if M(ai,..., dq) holds, then o(a1,....,@,) is provable, (6) if M(ais-.++4_) does not hold, then “v(@iy.-+58n) i provable. (For a proof refer to a textbook such as Mendelson [1964}) Consider now the statement n€K (i.e. 3yara(X, y)) that we took in § 1 asa formal counterpart of the statement ¢ X. Then from lemma 3.1 we can obtain 3.2. Corollary For any natural number n, ifn €K then ne is provable in Peano arithmetic Proof. Suppose that n © K.Then there is a natural number m such that R(n, m) holds, so by lemma 3.1 we have that a(n, m) is provable. The rules of the predicate calculus are such that we can immediately find a proof of 3yaa(n, y); ke. neK is provable. For part o his proof, Gadel needed an extra technical condition called ce-consisiency: a formal system is said to be w-consisten if there is no statement r{y) such that all ofthe following are provable: Ayz(y), 170), 9711), 1712), (w-consistency is a stronger condition than consistency (2.2)(b")) ‘We can easily derive the converse of corollary 3.2 from lemma 3.1, with the assumption of w-consistency. 33. Lemma Suppose that Peano arithmetic is w-consistent; then for any natural number n, if ne K is provable then ne K. Proof. Suppose that né K;; then for every m €N we have that R(n, m) does not hold, so by lemma 3.1, T9(n, m) is provable. Thus, if ne K is provable but né K, all of the following are provable Byoa(n,y), TRIN, 0), VeRLN, 1), in contradiction of w-consistency for the statement 7(y)= ain, y).3 Gédel’s incompleteness theorem 151 We can now present a proof of 34. Theorem (Gidel’s incompleteness theorem [1931]) There is a statement o of L such that (a) if Peano arithmetic is consistent, then ois not provable, (b) if Peano arithmetic is w-consistent, then “a is not provable. Proof. (a) Recall the sets Pr* = {n: n€K is provable}, Ref* ={n: neK isrefutable}, that we defined in the discussion at the end of the previous section, By corollary 3.2 we have K ¢ Pr*; consistency implies that Pr* Ref? = 2, and so Ref K. We can now argue as before: Ref is r.e.,so take m such that Ref* = W,,. The situation is illustrated by fig. 85, which should be compared with that in fig. 8a. By the productiveness of K, we have that me K\Ret*; in particular, mé Ref* means that m¢ K is not provable. Hence (a) is established, by taking « to be the statement mK. (b) The condition of w-consistency implies (by lemma 3.3) that Pr*< K, and hence Pr* = K, Thus, with w-consistency, fig. 8b modified to become fig. 8c. Thus mé K means that mé Pr*; i.e. me K is not provable. The rules of the predicate calculus tell us, immediately that To (ie. mm K) is not provable. 0 Notes 1. The statement ¢ produced by Gédel’s theorem is called an undeci- dable or an undecided statement of Peano arithmetic. As discussed at the Fig. 86, Gédel incompleteness (theorem 3.4(a)). w8 Arithmetic and Godel’s theorem 152, Fig. 8c. Gédel incompleteness (theorem 3.4 (b)) ‘end of § 2, « has the informal meaning ‘I am not provable’, and is, on an intuitive level, true 2. Clearly Godel’s theorem applies to any recursively axiomatised formal system in which all decidable relations can be represented (in the sense of lemma 3.1). In particular, this is true for any such system that is stronger than Peano arithmetic. In consequence, there is no way to avoid the incompleteness phenomenon by adding new axioms: for example o- or “a. The resulting formal system would have a new undecided statement. 3. Note that the undecided statement o can be constructed explicitly from a specification of Peano arithmetic, since from such a specification, we could effectively find an index m for Ref*. This constructive aspect of Gédel’s theorem is a consequence of the fact that K is creative. An analysis of the proof would show that we can demonstrate the mere existence of an undecided statement using any non-recursive r.e. set A in place of K. 4, Although not entirely clear from our presentation, the proof of part (a) of Gédet’s theorem is a finitist proof: that is, it shows explicitly how, zziven a formal proof of the statement a, to construct a proof of a (thus demonstrating inconsistency). We cannot make the same remark about (b), because w-consistency is not a finitist notion. In 1936 J. B. Rosser saw how to eliminate the assumption of w= consistency in part (b) of Gédel’s theorem. We shall now see that Rosser's refinement of Gédel's method can be viewed as an application of the effective recursive inseparability of the r.c. sets Ko={xids(x)=O}and Ky ={r:¢s(x)= 1)3 Gidel’s incompleteness theorem 153 (that we discussed in exercise 7-3.13(9)), in place of the use of the creative set K. (Our treatment below does not assume familiarity with this exercise.) ‘We begin by describing some statements of that are formal counter- parts of the statements n € Koand n ¢ Ki; these are slightly more complex than the formal version of n ¢ K used earlier. Select decidable predicates ‘Ro(x, y) and Ral y) such that ne Ko © thereis y such that Ro(, y) and n eK, @ thereis y such that Ri(n, y) Now clearly Kom Ki = ©, so we also have (*) me Ko © there is y such that (i) Rom, y) and (ii) for all z = y, Ry(n, 2) does not hold, and there is a similar equivalence for m € K,. Now take statements ony. ox, representing Ro, R; in Peano arithmetic as given by lemma 3.1. Rosser’s trick was (essentially) to use the following statement (based on (*) above) (4) Bylorasin, y) a¥2Sy(T08\(M, 2))) ‘as the formal counterpart of n ¢ Ko, rather than the simpler statement Byor(n, y). Letus write n¢ Ko for the statement (**) above. Similarly we write me Ky for the statement By(om(n, y) AV2 to be the statement p< Ko- "Although the proof of the theorem as stated is complete, let us now see how the numper p (hence the statement r) can be explicitly constructed From an explicit specification of Peano arithmetic, we can effectively find an index p such that 1 itnerr*, bole “I ifmeRet**, undefined otherwise We can now see that pé Pr** U Ref*, as follows: (i if pePr*, then dp(p)=1, so peKy hence peRef*, contradicting consistency. Hence pe Pr**. (ii) if pe Ref, then dp(p) =0, 80 p € Ko, henee pe Pr°*, ano- ther contradiction. Hence pé Ref” (The faet that p can thus be obtained explicitly uses essentially the effective recursive inseparability of Ko and Ki (see exercise 7- 3.130)) 3 Notes 1. The statement 7 construeted in this theorem corresponds to the undecided statement o of theorem 3.4; its easily seen that “7 also has the informal interpretation ‘I am not provable’, and is intuitively true. 2, The Gédel-Rosser theorem applies to any recursively axiomatised formal system of arithmetic in which all decidable relations can be represented and for which lemma 3.5 can be established. (Lemma 3.5 always holds for systems in which statements 3.6 (a), (b) can be proved: such systems are called Rosser systems.) Again, there is thus no possibility of avoiding incompleteness by adding new axioms. 3. The Gadel-Rosser theorem is a completely finitist theorem: the proof (when given in full detail) shows how to demonstrate inconsistency explicitly if we were given a proof of either 7 or 77. 4: Undecidabilty We have already seen that the set J of true statements of arithmetic is not recursive (theorem 1.5): this soften described by saying that Fis undecidable. In general, when considering sets of statements the terms decidable and undecidable are often used to mean recursive and ‘We can ask particularly of any formal system of arithmetic, isthe set Pr of provable statements decidable? The answer i invariably no, and there8 Arithmetic and Gdel’s theorem 156 are various ways to see this. We confine ourselves to one of the many results in this area, using the ideas of the previous section. 41. Theorem Suppose that (st, 2) is an w-consistent formal system of arithmetic in which all decidable predicates are representable (in the sense of lemma 3.1). Then the set of provable statements is creative. Proof. The assumption of the theorem means that Gédel’s theorem 3.4 applies, so in particular we have from the proof of theorem 3.4 K =Pr*={n:neK is provable). Now let Pr={n: dy is provable}; we can find a computable function h such that MEK is Oko» and then neK @ nePr @ h(n)ePr, So by theorem 7-3.2, Pris creative. 0 4.2. Corollary If Peano arithmetic is w-consistent then the provable statements form a creative set. (This is the case in particular if all provable statements are true.) ‘The counterpart to theorem 4.1 and corollary 4.2 using Rosser’s ideas is given in the following exercise. 43. Exercise Suppose that (sf, ) is a consistent recursively axiomatised formal system for which lemmas 3.1 and 3.5 hold. Let Pr** and Ref** be the sets defined in the proof of theorem 3.6. (a) Show that Pr* and Ref** are effectively recursively inseparable. (b) Let Pr={n: 6, is provable} and Ref = {n: “8, is provable}. Prove that Pr and Ref are effectively recursively inseparable. (Hint, Extend the idea of theorem.7-3.2 to pairs of effectively. recursively inseparable sets.) ‘The presentation of the results in this chapter is derived largely from the books of Kleene [1967] and Smullyan [1961]. For further discussion of incompleteness and undecidability in arithmetic and related areas, the reader is referred to Bell & Machover [1977], Boolos & Jeffrey(1974], or Rogers [1971]9 Reducibility and degrees Inearlier chapters we have used the technique of reducing one problem to another, often as means of demonstrating undecidability. We did tis, for instance, in the proof of theorem 6-1.4 by showing that there is a total computable function k such that xe W, € dxi.=0, ie. wo used the function & to transform or reduce each instance of the general problem “x€ W,"to an instance of the general problem ‘4, = 0°. In this chapter we consider two ways of making the idea of redueibility precise, and for each wwe discuss the associated notion of degree (of difficulty) that arises. Itis more convenient to deal with reducibilty between sets rather than between problems, remembering that any problem is represented by a set ‘of numbers. The informal idea of set A being reducible toaset B can be expressed in various ways: for instance (a) ‘Given a decision procedure for the problem ‘x € B’, we can construct one for ‘x € A’. (b) ‘For someone who knows all about B, there is a mechanical procedure (that uses his knowledge of B) for deciding questions about A. (c) ‘Questions about A are no harder than questions about B.” (a) “The degree of difficulty of the problem ‘x ¢ A” isno greater than that of the problem ‘x ¢B.” It turns out that there are several non-equivalent ways of making this idea precise. The differences between these consist in the manner and extent to which information about B is allowed to be used to settle questions about A. In §§ 1-3 we shall investigate one of the simplest notions of reducibility, called many-one reducibilty, which includes all of ‘our earlier uses ofthe informal idea. Inthe final sections we shall discuss a ‘more general notion known as Turing reducibility9 Reducibitity and degrees 158 1. Many-one reducibility LL. Definition The set A is many-one reducible (abbreviated m-reducible) to the set B if there is a total computable function f such that for all x xed iff fieeB. We shall write this A tis posible to have. notion ofm-complet sets for lasesother than the cass of ‘reset its then necessary to Keep the reference or. here.9 Reducibility and degrees 166 (6) Aism-complete iff A=mK iff Ais re. and K Sq A, (c) Om consists exacily of all m-complete sets. Applying this we have the following: 3.3. Examples ‘The following sets are m-complete. (a) (zc W,} (example 1.2(15)), (b) any non-trivial rc. set of the form (x:4_€ @} where Bc @, (the proofs of theorems 7-3.4 and 3.8 show that K'<»such aset), (©) (e:@s(0)=0)) @) exer) eerie 1.700). ‘The reader may have realised that m-reducibility appeared implicitly in the statement of theorem 7-3.2, which implies immediately that 3.4. Theorem Any m-complete set is creative. Proof. If A is m-complete, then K =A, 80 K Re ‘The URMO, with y in its oracle and obeying the instruction O(n) may be envisaged as shown in fig. 95. ‘A program is, as before, a finite sequence of instructions. The URMO operates under a URMO program P in the same way as the URM, with the following additional stipulation: after obeying an oracle instruction [, in P the next instruction is I, We emphasise that ina URMO program P no particular function x is mentioned. Thus the meaning of P varies according to the function supplied in the oracle. However, a computation under P can be carried out only when @ particular function y is supplied, so we write P* to denote the program P when used with the function y in the oracle. Thus we write PH(ay,...54n) for the computation by P, with x in the oracle, and with initial configura- tion a3, 425... dq, 0,0,...5 and we write Pr(a)ib to mean that the computation P*(a) stops with the number b in register R. if definitions (parallel with definition Fig. 9 Oracle ee at mR RR R ‘With resulting configuration nlele .)4 Relative computability 169 42. Definition Let x be a unary total function, and suppose that f is a partial funetion from N° to N. (a) Let P be a URMO program. Then P URMO-computes f relative 10 x (or f is y-computed by P) if, for every aN" and ben, PY(a)ib iff fla) (b) The function f is URMO-computable relative to x (or just x-compuiable) if there is a URMO program that URMO- computes it relative to x. We write ‘* to denote the class of all y-computable functions. We are now in a position where we could define Turing-reducibility. However, to aid a better understanding of this concept when we come to it, we shall first outline a little of the development of the theory of relative computability. Most methods and results from unrelativised computability have counterparts in relative computability. Thus in many of the theorems that follow we supply only a sketch proof or a reference to the unrelativised version of the same result, Throughout this section x stands for a total unary function. 43. Theorem (a) xe", () @c#, (c) ifxis computable, then % =, (d) €* isclosed under substitution, recursion and minimalisation, (e) if bis a total unary function that is y-computable, then Ce. Proof. (a) Use the URMO program O(1) (b) Any URM program is a URMO program. () Inview of (6), we need only show that @ < Suppose that f is y-computable and that y is computable. Proceeding informally, we can compute any value of f as follows: use the ‘algorithm for f, and whenever a value of x is requested simply compute it using the algorithm for x. Tis is an effective pro- cedure, so by Church's thesis / is computable. (We leave the reader to provide @ formal proof of this result; see exercise 4.1013),)9 Reduciblity and degrees 170 (d) The proofs are idemtical to those of theorems 2-3.1, 2-4.4 and 2-5.2. (e) The proof is similar to that for (c) (which is really a special case of (e)). Other approaches 10 relativised computability Any alternative approach to computability can be modified to provide a corresponding, notion of relative computability. A relativised version of the Fundamen- tal result (theorem 3-1.1) can then be proved, and this leads to the formulation of Church's thesis for relativised computability. We mention here only the relativised notion of partial recursive function: 44. Definition The class J” of x-partal recursive functions is the smallest class of functions such that (a) the basic functions are in 3”, (b) xe", {c) ®* is closed under substitution, recursion and minimalisa- tion. The phrases partial recursive in x or partial recursive relative to x are also used with the same meaning as x-partiat recursive. ‘The notions y-recursive (or recursive in, oF relative to, x) and y-primitive recursive (oF primitive recursive in oF relative to, x) are defined in the obvious way. Corresponding to theorem 3-2.2 (and proved in the same way) we have 4.5. Theorem For any x, RY = €", Numbering program: and functions URMO programs can be effectively numbered or coded by an easy adaptation of the method used in chapter 4 for URM programs. Let us assume that this has been done, so that we have a fixed effective enumeration (without repetitions) Qo, O1, Qa, of all URMO programs.’ Then we write 4" for the n-ary function y-computed by Qn, Bach URM program P appears in this ist: in most cases, however, its number here wilt he diferent from that assigned tit in chapter 44 Relative computability 1 bh for os, W4 for Domi¢3), Ek, for Ran(o) ‘The s-m-n theorem (4-4.3) has a relativised counterpart with identical proof: 4.6. Theorem (The relativised s-m-n theorem) For each m, n= 1 there isa total computable (m + 1)-ary function le, x) suck that for any x BER ¥)~ bIBieni(P)- Note. The function 57 here differs, of course, from the function given the same name in theorem 4-4.3. Note, however, that si" here is still computable (not merely x-computable) and does not depend on x. Universal programs for relative computability Relativisation of the proof of theorem 5-1.2 gives immediately: 4.7. Theorem For each n, the universal function Wi" for n-ary x-compuiable functions given by PS (ex) =O2" (x) fs y-compurable Remark. & careful examination of the full formal proof of theorem S-1.2 would show that there is a URMO program Qu, independent of x, that computes wi" for any x. ne.sets The relativised notions of recursive and rc a-recursive and x: sets are given by: 4.8, Definition Let A be a set (a) A is x-recursive (or recursive in x) if ca is x-computable, (b) Ais y-re. (or re. in x) if the partial characteristic func ( ifxea, undefined ifxe A, is x-computable. fle9 Reducibility and degrees 72 ‘The following selection of basicresults about y-recursive and y-r.e. sets is proved by the addition of the prefix y- at the appropriate places in the proofs of the corresponding unrelativised results in chapter 7: 4.9. Theorem (a) For any set A, A is x-recursive iff A and A are x-r. (6) For any set A, the following are equivalent (i) Ais x-re, Gi) A=W, for some m, i E's, for some m, (iv) A= © or A is the range of a total x-computable function, (W) for some x-decidable predicate R(x, y), xeA © ByRix,y) (R is y-decidable if its characteristic function is y-computable).. (€) Let K* ={x:x € Wi}; then K* is yore, but not x-recursive, Computability relative to a set For any set A, we define computability relative to A (or just A-computability) to mean computability relative to ay the characteristic function of A. Thus we write P* for P* (if Pisa URMO program), €A fore, On for O54, Wa for Wie, Ed for Ess, K* fork, A-recu fe for ca-recursive, Ante. for cate ete, In the next section we shall define Turing reducibility in terms of computability relative to a set. For a set A, we can summarise the basic idea that we have presented in this section, in a nutshell, as follows: A-computability is computability for anyone who knows all about A. To. be a little more precise, we should expand this to: for anyone who can answer any question of the form ‘x ¢ A. This excludes knowledge of ‘infinite’ facts about A, such as whether A has infinitely many even members.4.10. 10. 4 Relative computability 173 Exercises Let x, ¥ be total unary functions, and suppose that 6? i total. I, 2 necessarily total? Suppose that xi,2,---+Xe are total unary functions. Define Ae to be the smallest class of functions containing the basic functions and y1,..., xx and closed under substitutions, recursion and minimalisation, Formulate a definition of the set <@*™ of functions computable relative to x3, Xx Such that, ere gh", (Hint, Either define @ machine having & oracles, or find a single unary funetion yy such that d=" = aR) Provide a full formal proof of theorem 4.3(c): if x is compu table, then € = © Show that there isa total computable function k (independent of, 2x) such that Wijasy = WS UWS for al indices a 5. Verity theorem 4.9, Let A be any set (a) Show that for any re. set B, there is an index such that B=We, (6) Show that if A is recursive , then W2 is re. for all (c) Show that if A is recursive, then K* is re. but not Let A, B, C, be sets. Prove that (a) if A is B-recursive and B is C-recursive, then A is C- recursive, (6) if A is Bere. and B is C-recursive, then A is Cre., (c) if Ais B-recursive and B is C-r.e., then A is not necessarily Cre (Relativisation of theorem 1.6.) Let A be any set, Show that for any set B, Bis Are. @ BSqK* ). Show that there is a single number d such that K*=W forall sets A. (a) We say that a set A is y-simple if (i) A is x-re., ii) A is infinite, (ii) A contains no infinite y-r.e. subset. Show that there is a x-simple set. (b) Formulate the definition of a y-creative set. Show that a -simple set is not y-creative.9 Reducibility and degrees 174 5. Turing reducibility and Turing degrees Using relative computability we make the following definitions: 5.1, Definitions (a) The set A is Turing reducible (or just T-reducible) to the set Bif Ais B-recursive (equivalently, if ca is B-computable). Thisis written As1B, (6) The sets A, B are Turing equivalent (or T-equivatent) if ASB and B=rA. (The use of the word equivalent is justified in theorem 5.2() below.) We write this A =rB. Let us consider informally the meaning of Turing reduciblity. Suppose that A <1B and that P is a URMO program that computes ca relative to 2B. Then for any x, P®(x) converges and Pe) ifxed, PP)|0 fee. During any completed computation P(x) there will have been a finite number of requests to the oracle for a value cp(n) of cp, as dictated by P and the progress of the computation. These requests amount to a finite number of questions of the form n €B". So for any x,"x €Ais settled in a mechanical way by answering a finite number of questions about B. Thus we see that Turing reducibilty accords with the informal notion of reducbility discussed at the beginning of § 4 Some of the basic properties ofthe relations = and = are given in the next theorem 5.2. Theorem (a) =r is reflexive and transitive, (0) =r is an equivatence relation, (©) fA=mB then A=rB, (d) A=rA forall A, (¢) if A is recursive, then A: again, we think of a degree as a collection of sets all having the same degree of difficulty. SA. Definitions (a) Let A be a set; the equivalence class dy(A)={B:B=rA} is called the Turing degree of A, abbreviated the T-degree of A. () Any T-degree containing a recursive set is called a recursive Tedegree. (c) Any T-degree containing an r.e. setis called an re. T-degree. The notions of Turing reducibility and Turing degree are widely accepted as the most basic among all other similar notions. Hence the term reducible without qualification is often used to mean Turing reducible; similarly, Turing degrees are often referred to merely as degrees, or degrees of unsolvability. We shall adopt this practice in the remainder of our chapter. As before, the letters a, b,¢, etc. are used for degrees. ‘The relation = on sets induces a partial ordering on degrees, as with Sa:9 Reducibility and degrees 176 5.5. Definition Let a, 6 be degrees, (a) ab if for some (equivalently, for all) Aca and Bed, AS=rB; ()) a x and fy) , there is an r.e. degree b such that bla. 5.15. Sacks’ Density theorem For any rc, degrees a <6 there isan r.e, degree e with a0 there are r.e, degrees 6, ¢ such that b 0 such that 0 is the greatest lower bound of a and b. (6) There are re. degrees a, & having no greatest lower bound (either among all degrees or among re. degrees). ‘Turning to non r.e. degrees, a surprising result is 5.18 Theorem (Shoenfield) There is a non-r.e. degree a <0 A minimal degree is a degree m > 0 such that there is no degree a with 0 Om, there isan re, m-degree bsuch that bla. Proof. Let Aca; A iste. so by theorem 5.14 take an re. T-degree ¢ such that dy(A)|e. Let B be an re. set in ¢, and let b=d.(B). Then if @Sqb OF bSma, by theorem 5.6(c) we have dr(A)=e or e Fy3the letters &, ¥,.... will invariably denote operators in this chapter. We shall confine our attention to totally defined operators : Fy > F,; ie. such that the domain of @ is the whole of Fn. ‘The chief problem when trying to formulate the idea of a computable (or effective) operator &:F;-» F;, say, is that both an ‘input function f and the ‘output’ function (f) are likely to be infinite objects, and hence incapable of being given in a finite time. Yet our intuition about effective processes is that in some sense they should be completed within a finite To see how this problem can be overcome, consider the following operators from Fy to FI Recursive operators 183 (6) @2()= g, where g(x) =Syexfl. ‘These operators are certainly down to earth and explicit. Intuitively we might regard them as effective operators: but why? Let fe Fi and let i= ®i(f)s notice that any particular value gi(x) (if defined) can be calculated in finite time from the single value f(x) of f; if we set g2= :(f), then to calculate g2(x) fi defined) we need to know the finite number of values /(0), f(1),...,f(x). Thus in both cases any defined value of the output function (,(f) or 2(/)) can be effectively calculated in a finite time using only @ finite part of the input function f. This is essentially the definition of a recursive operator given below. ‘One consequence of the definition will be the following: suppose that ‘(/\(x) = y is calculated using only a finite part @ of f; then if g is any other function having @ as a finite part we must expect that (g(x) = also. To frame our definition precisely there are some technical considera- tions. First, let us agree that by a “finite part’ of a function f we mean a finite function @ extended by /. (We say that @ is a finite function if its domain is a finite set.) For convenience we adopt the convention @ always denotes a finite function in this chapter. ‘The above discussion shows that the definition of recursive operator will involve effective calculations with finite functions. We make this precise by coding each finite function @ bya number # and using ordinary computability. A suitable coding for our purposes is defined as follows: suppose that 0c F,. The n-tuple x = (xis...) 8 coded by the number pir’; then define the code 8 for @ by pic"! provided that Dom(6)4 2, it Dom(a)= 2 (in which case 8 = fa). ‘There isa simple effective procedure to decide for any number z whether 2 =4 for some finite function 9; and if so, to decide whether a given x belongs to Dom(9}, and calculate 6(x) if it does. Now we have our definition: Ll. Definition Let ©: F_>F,. Then @ is a recursive operator if there is a computable function (z, x) such that'for all fe Fy and xeN", yeN10 Effective operations on partial functions 184 O(Plx)~y iff there is finite 0 f such that (4, x)~y. (Note that o is not required to be total.) 1.2. Example ‘The operator (/)=2/ is recursive operator: to see this define b(z.x) by 20(x) itz = Gand xe Dom(@), #2)" Lundefined otherwise. By Church’ thesis, 6 is computable: now for any f, x, y we have (Px) ~y $2 x= Domif) and y =2ftx) ¢> there is @< f with x F, be an operator. (a) @ is continuous if for any fé Fy, and all x, O( f(x) =y iff there is finite @Fq be a recursive operator, with computable funetion 4 as required by the definition. Suppose that (/)(x) = y, and let Of such that 4(6,x)=y. Since @<8, it follows immediately that (0x) = y. Conversely if 6 f and ®(8)(x)~ y, there is 8, < @ such that 6(d;, x)= yi but then @/, 50 we have that (f(x)=y. Hence @ is continuous. Monotonicity follows directly from continuity: suppose that f< g and P(N(a)~y. Take @Sf such that P(O)(x)~y; then 9c, so by continuity, ®(g)x)=y.1 Recursive operators 185 The use of the term continuous to describe the property 1.3(a) is justified informally as follows. Suppose that : FF, satisfies 1.3(a) and fF. Then given any x1,... 34 for which @(f)(x,) (1=/=k) are defined, using 1.3(a) we can obtain a finite @=/ such that P(6)(x:) = (fix) (1Si F, by D(/)=gef. Obviously ® is continuous, and 4 (6, x) ~ g(6()) is computable. (d) (The Ackermann operator). Let ®: F,-> #2 be given by O(N10,y)=y +1, (Pix +1,0)=Fle 1), D(x +1, y+ 1)= Fs fle #L, yD). To see that # is continuous, note that (f)tx, y) depends on at ‘most two particular values off. For recursiveness, itis immediate by Church's thesis that the funetion @ given by $6.0, y)=y41 (6, x+1,0)~6(x,1) OO x+1, y+ 1)~ Ox, Ax +1, 9) is computable. (e) (The p-operator.) Consider @: Fyu1>Fqy given by P(filx)=ny( fix, y)=0). It is immediate that this operator is continuous, and that the funetion @ given by $16.) =ny(O(x, ») = 0) is computable.1 Recursive operators 187 ‘When the definition 1.1 of arecursive operator : FF; isextended to the case n=0, we have what is called a recursive functional. The members of Fo are O-ary functions; ie. constants. Just as F, (n= 1) includes the function that is defined nowhere, Fo includes the “undefined” constant, which is denoted by @. Thus %=Nu{o}, and an operator ©: Fy, Foisa recursive functional if there is a computable function (x) such that for any f¢ Fy, and y € Ns O(f\~y iff 30/0 Sf and 6(4)=y). We write 0(f)=a if P(/) is undefined; this emphasises that @ is still ‘thought of as being a total operator. We should point out that in some texts the term partial recursive functional F,,-> F, is used to describe recursive operators, including the case n =0. In such contexts the word partial describes the kind of object being operated on rather than the domain of definition of the operation. ‘We shall not discuss here the extension of the ideas of this section t0 partially defined operators and the corresponding partial recursive opera~ tors ©: Fy» Fq. The reader is referred to Rogers [1967] for a full discussion of these and related matters. 17, Exercises 1, Show that the following operators are recursive, (a) O(=F (fe Fu, (b) O(f)=g (fe Fah where g isa fixed computable function in Fy (c) @(f)=feg (fe Fx) where ¢ isa fixed computable function in S, define (d) Let he Fs be a fixed computable fun DF. Fas BY 0 thle y)=0, {fix+1,y)+1 if h(x, y)is defined and +0, ‘undefined otherwise (The significance of this operator will be sen Inter.) 2. Prove that if @ is «recursive operator and/ is computable then so is Of). 3. Decide whether the following operators @:F1>F: are (i) monotonic, (i) continuous, (i) recursive ffix) if Domi) isfinite, (2) 9.8) ndetaed item) nine Pls)8. 10 Effective operations on partial functions 188 0 if f(x) is defined, lundefined otherwise. Oit fix)eK] (©) @(Alx) fit faye K lundefined otherwise. fundefined if Dom(f) is finite, Yo if Dom({) is infinite. Suppose that ®:F,,— F, and W:F, +> F, are recursive opera- tors. Prove that W°@:F, » F, is recursive, Show how to extend the definition of recursive operator to include operators ®: Fp, Fy... Fm, > Fy and prove appropriate versions of theorems 1,4 and 1.5 for your definition. Prove that the following operators are recursive: (a) ®: FXG, >F, given by Hf, g)=fog (ct. question 1c above); (b) Fy. % Fysr> Fass given by 6) ene{ if f(x) is defined, (d) G(P\x)~4 0 if ht, y)=0, PUFA) y)={ fle+1, y)+1 if h(x, y)is defined and is not 0, undefined otherwise (cl. 1d above) (For those who know some topology.) (a) Prove that an operator is continuous in the sense of definition 1.3(a) iff it is continuous in the positive information topology. (b) Prove that the following are equivalent for Vc &, {) Vis open in the positive information topology, ii) fe V iff 30(6Sf and 8€ V), Let @: F,+F, and V: F, > F, be continuous operators; prove that Vo: F_ > F, is continuous. Let P(N) denote the class of all subsets of N; formulate a definition of a recursive operator @: (NN) > P(N) that parallels the notion of a recursive operator from #;-F;. Frame and Prove theorems corresponding to theorems 1.4 and 1.5. (Hint, The question of membership x€ (A) should depend effectively on @ finite amount of positive information about membership of the set A.) (Effective operators P(N)-+ P(N) are called enumeration operators and are discussed in full in Rogers [1967].)2 Effective operations on computable functions 189 2. Effective operations on computable functions In chapter 5 §3 we considered that certain operations on computable functions should be called effective because they can be given by total computable functions acting on indices. For instance, in example '5-3.1(2) we saw that there is a total computable function g such that for all €€N, (6-)° = bee ‘We shall see in this section that any recursive operator ®, when restricted to computable functions, yields an effective operation of this kind on indices. This is the first part of a theorem of Myhill and Shepherdson. They proved, moreover, that all such operations on indices of computable functions arise in this way. We shall prove the two parts of the Myhill-Shepherdson result separately, taking the easier part first. 2.1, Theorem (Mybill-Shepherdson, part 1) Suppose that ¥: F > Fy is a recursive operator. Then there is a total computable function k such that vis" Proof. Let ¥ be a computable function showing that ¥ is a recursive operator according to definition 1.1. Then for any ¢ we have ohn (ee). VSL” )ix)= y @ 3019 SH” and YG, x)~y). ‘We shall show that the function g defined by gle) = LV) is computable, by showing that the relation g(e, x) ~y is partially deci- dable. To this end, consider the relation R(z, e, x, y) given by Rlz,e,x, y) = 46(z =0 and 6.62” and YG, x)=y). ‘Then R is partially decidable, with the following informal partial decision. procedure. (1) Decide whether z = 4 for some 8; if so obtain x,..., IN" and ys, +» 9x such that Dom(@) (1sisk);then (2) for compute #2""(x,):if, for 11k." defined and equals ye then (G) compute u(z, x) and if defined check whether it equals y. IER(z, ¢,, y) holds, this is a mechanical procedure that will tell uso in finite time, as required. ty vos Re} and BC) = Yi (x) is10 Effective operations on partial functions 190 Since R(z,eay) is partially decidable, so is the relation 32 R(z,¢, x, y) (by theorem 6-6.5): but Bz Riz, €, x, y) € Wd," )(x)~ y (from the definition of R) gle,x)~y (from the definition of g), ‘Thus g(e, x) ~ y is partially decidable, so by theorem 6-6.13 g is comput- able. Now the s-m-n theorem provides a total computable function h such that phthie)=elex) = Worx), from which we have #'%) = Wié!"). Notice that the function h given by this theorem for a recursive operator VF,» F; is extensional in the following sense. 2.2. Definition A total function h:N->1N is extensional if for all a, if 6, then ya Now we can state the other half of Myhill and Shepherdson’s result. 23. Theorem (Myhill-Shepherdson, part It) Suppose that h is an extensional total computable function. Then there isa unique recursive operator Y such that W\d,)= dy foralle. Proof. Atte heat of our proof Hes an application of the Rice Shapiro. | theorem (theorem 7-216. | Leth be an extensional total computable function. Then h defines an operator Wo: 6; > €, by Vode) = dies ‘ois well defined since his extensional. We have to show that ther unique recursive operator Wi: = F that extends Vo First note that Yo(0) is defined for ll ite since fnite functions are computable, Thus any recursive operator extending Ys, being continuous, must be defined by (24) Wifilx)=y = 30(8 cf and ¥(8)(x)= y). So such @ Vit exists, 6 unique. To prove the theorem we must now show that (i) (2.4) does define an operator ¥, Gi) Wenends Ye |2 Effective operations on computable functions 191 ii) V is recursive, We first use the Rice-Shapiro theorem to show that Yo is continuous in the following sense: for computable functions f (2.5) Vol f\lx)=y €9 34(Sf and Wol6\(x)=y)- To see this, fix x, y and let sf ={fe€y: Yolfx)~y) Then the set A= (e:de€ sf) = (0: dy(t)~ y) isr.€.;50 by the Rice-Shapiro theorem, if fis computable then fed @ 36(0S/and Gest), which is precisely (2.5). Now we establish (i), i), (ii) above. (i) Let f be any partial function; we must show that for any x, (2.4) defines W(f\(x) uniquely (if at all). Suppose then that @),62¢/ and ‘Wo(0,)ix) —y1 and Yo(02)(x) ya: Take a finite function 0.2 91, 2 (Say, @ = f|Dom(9,)s Dom(6s)); by (2.5) yi= ol @sNx) = Vo(O))~ WolG}(4) = y2- ‘Thus (2.4) defines an operator ¥" unambiguously. (i) This is immediate from (2.5) and the definition (2.4, (Gi) We show that V satisfies the conditions of theorem 1.5. Clearly ¥ is continuous, from the definition. For the other condition we must show that the function y given by WG, x) ~ WAN), W(z, x) is undefined if 2 #6, is computable, Now itis easily seen by using Church's thesis that theres @ computable function c such that for any finite function 4, c(@) isan index for 6; ie. 8 = dey. Thus WG, x)= Hibs) = Sricinh3)o so vis computable, since h and c are, Hence W is @ recursive operator. Remarks 1. The proof of theorem 2.3 actually shows that for any extensional computable there isa unique continuous operator W: Fs F; such that Wg.) = buen all e, and that this operator is recursive. 2. Theorem 2,3 extends in a natural way to cover operators from Fn Fy. The proof is almost identical, using the natural extension of the Rice-Shapiro theorem to subsets of €q; see exercise 2.6(2) below.10 Effective operations on partial functions 192 26. Exercises 1, Suppose that , ¥ are recursive operators > F,; knowing that « ¥’is continuous (exercise 1.7(7)) use the two parts of the Myhill-Shepherdson theorem together with the first remark above to show that eV is recursive. 2 State and prove a general version of theorem 2.3 for operators from €q > €q. 3. Formulate and prove versions of the Myhill-Shepherdson theorem (both parts) appropriate for the operators you have defined (a) in exercise 1.7(5), (6) in exercise 1.7(8), 3. The first Recursion theorem | The first Recursion theorem of Kleene is a fixed point theorem for recursive operators, and is often referred to as the Fixed point theorem (of recursion theory). We shall see later that it isa very useful result B.A. The first Recursion theorem (Kleene) Suppose that ©: Fy. -> F» is a recursive operator. Then there is a computable function fe that is te least fied point of ®; Le (a) © fe)= fo () 7 O1g)=6, then foe. Hence, if fg is total, it is the only fixed point of @. Proof. We use the continuity and monotonicity of & to construct the least fixed point fp as follows. Define a ‘sequence of functions {f,} (nN) by fo fo (the function with empty domain), fun = O(f)- Then fo foSfis and il fu fur, by monotonicity we have that f..y Pf) S OUFnat)= fea. Hence fy & fury for all n, Now let fo= U fw by which we mean Folx)~y iff In such that fy(x)~y. We shall show that fo is a fixed point for & For all. n,3 The first Recursion theorem 193, hence furr= OU) = OUfo)s thus foS (fa). Conversely, suppose that (fe)(x)=y; then there is finite @< fo such that ®(6)(x) =; taken such that @ < fx; then by continuity 0 f.)(x That i, fues(t)= y: Hence falx)~ y. Thus ®(fo)< fox and so fe as required. ‘To see that fo isthe least fixed point of ®, suppose that (gg; then clearly fo fo &, and by induction we sce that fx 0; ° itx=0, (c) CC flx,y)) ifx>0. 2. (McCarthy) Show that the function m(x) given by 91 ifx 100, x10 otherwise, is the only fixed point of the recursive operator ® given by {ive if x= 100, xpi tn x-10 otherwise.10 Effective operations on partial functions 196 3. Suppose that @ and ¥ are recursive operators F; x Fi > Fi (in the sense you have defined in exercise 1.7(5)), Show that there is a least pair of functions f, g such that f= O(h8) a= (he) and f, g are computable. 4, Suppose that ©: %, x Fn» Fy is a recursive operator (in the sense you have defined in exercise 1.7(5)). For each ge Fy let Gp: F.-> F, be the operator given by Df) = Pf, g) Show that the operator W(g) =least fixed point of ©, is a recursive operator Fu, > Fr 4. Am application to the semantics of programming languages ‘We shall seein this section how the first Recursion theorem helps to resolve @ problem in the semantics of computer programming languages ~ the area that deals with the question of giving meaning to programs. Our discussion is necessarily given in terms of a general and unspecified programming language, but this is adequate to explain the basic idea. Suppose, then, that L is a general programming language. The basic symbols of L will have been chosen with a particular meaning in mind, so that the meaning of compound expressions built from them is also clear. We may then envisage a simple program for a function as follows. Suppose that r(x) is an expression of L such that whenever the variables x ae given particular values a, then z(a) can be unambiguously evaluated to the semantics of L. If we now take a function symbol f of L that does not occur in 7, then (4.1) faa)= 7) isa simple program fora function f, that has the obvious meaning: for any numbers a, f,(a) is obtained by evaluating the expression r(a) according to the semantics of L. Suppose now that 7 is an expression in which the symbol f does occur We indicate this by writing +(x). Then the program (4.1) becomes (42) fla)=rtf.2), Thisis now what is called a recursive program. Situations occur where this isthe most natural and economical way to describe a function that we may desire the computer to compute, Yet the meaning ofthe ‘program (4.2)is not entirely clear. The fundamental problem with any recursive program4 An application to programming languages 197 is: how do we give ita pre until this question is settled. There are basically two approaches that provide an answer to this question; (a) The computational approach. Here the function taken to be defined by a recursive program is given in terms of a method of computing it. This approach reflects the fact that the computer scientist needs to know not only what a program means, but also how to implement it. (b) The fixed point approach gives a meaning to a recursive program by an application of the first Recursion theorem. The fixed point theory also resolves some problems raised by the computational approach, and actually shows that the two approaches may be viewed as complementary rather than competing, Let us now briefly explain these two approaches and sce how first Recursion theorem enters the picture. meaning? It can hardly be called a program The computational approach This is best described by giving some examples. Consider the recursive program _p itr=0 43) fa)= 2flx-1) ifx>0. (We are assuming that in L we can formulate conditional expressions such as this.) Using the equation (4.3) we can formally evaluate the value /(3), for instance, as follows: f(3)=2% f(2) =2 2 f(1)=2x2*2xf(0)=8; here we have made successive substitutions and simplifications using the formal equation (4.3). Hence i fis the function deemed to be given by the program (4.3) we would have f.(3)=8. With more complicated recursive programs there may be more than fone way to use the formal equation f(x) = r(f,) in such an evaluation procedure. Consider, for instance, the recursive program 1 itx=0, flr-1, fle y)) ifx>0. ‘Suppose that we try formally to evaluate f(1, 0). We have (4.5) f4,0)=f(0, £11, 0). But now there is a choice of occurrences of f for which to substitute (4.4) flu y=10 Effective operations on partial functions 198 7(f,x). Choosing the leftmost one and simplifying we have £01, 0)~f(0, FL, 0))=1 (since x =0). If, on the other hand, we substitute for the rightmost occurrence of feach time, we obtain from (4.5) FC, 0)=f(0, £1, 0) ~f00, 0, f41, 0))) =F(0, FO, (0, f(1, 0)))= and in this case no ‘value for f(1, 0) emerges. A computation rule is a rule R that specifies how to proceed when confronted with such a choice of possible substitutions during any formal evaluation procedure. The computational rules we considered for the recursive program (4.4) were ‘leftmost’ (LM) and ‘rightmost’ (RM). ‘There are many other possible rules. For any computation rule R, and recursive program f(x)= 7(f,x) we define the function fn by: f(a) is ‘the value obtained when f(a) is formally evaluated using the rule R. If no value is thus obtained, f,e(a) is undefined. (Thus for the recursive Program (4.4) we have f..4(1, 0)= 1, and f.nyi(1, 0) is undefined.) So we see that each computation rule gives a meaning to any recursive rogram (and, at the same time, a method of implementing it) ‘The above example demonstrates that different computation rules may sive different meanings to any particular recursive program. The problem ‘now for the computer scientist who chooses this computational approach is to decide which computation rule to choose. Moreover, for any rule R, there isthe question of determining in what sense, if any, the function f.. satisfies the equation fa)=r(f.x). The fixed point approach, using the first Recursion theorem, avoids these problems, and in fact sheds light on both of them, as we shall see. The fixed point approach An expression r(f, x) of L gives rise to an operator b:F, > F, by setting Pig)lx)=r(g,x) for any g¢ F,. Morcover, in most programming languages the finite and explicit nature of the expression r(f,.x) ensures that @ is a recursive operator. The first Recursion theorem now tells us that ® has a compu- table least fixed point, which we may denote by f.. Thus we may define the function given by the program (4.2) as f,. This is quite reasonable, because f, is computable, and moreover we know that f,(x)~r(f,.x), which is surely what the programmer intended.4 An application to programming languages 199 ‘There remains the matter of finding good practical procedures for implementing the program (4.2) with its meaning defined in this way. It ‘can be shown that for any computation rule R, f,.e ¢f-; further, there are ‘computation rules R for which f.x = f- for all. Any one of these may be ‘chosen as a practical way of implementing recursive programs. Then we can say that the computational and fixed point approaches are comple- mentary rather than opposed to each other: the fixed point approach, via the first Recursion theorem, gives theoretical justification for the parti- cular computation rule chosen ‘There are further advantages in adopting the fixed point approach (or @ computation rule equivalent to it): there is a variety of useful induction techniques for proving correctness, equivalence, and other properties of recursive programs with fixed point semantics, and these can all be rigorously justified. For a full discussion of this whole topic the reader is referred to the books of Bird [1976] and Manna [1974]. Here we have slightly simplified the framework within which the computer scientist works; in fact the fixed point f, he chooses is least in a slightly different sense (but still given by a version of the first Recursion theorem).11 The second Recursion theorem The first Recursion theorem, together with the Myhill-Shepherdson theorem in the previous chapter, shows that for any extensional total computable function f there is a number n such that bp ‘The second Recursion theorem says that there is such an n even when fis ‘not extensional: we shall prove this in § 1 of this chapter. This theorem (and its proof) may seem a litte strange at first, Never- theless it plays an important role in more advanced parts of the theory of computability. We shall use it in the promised proof of Myhill’s theorem (theorem 9-3.5) and in the proof of the Speed-up theorem in the next chapter. In § 1, after proving the simplest version of the second Recursion theorem, we describe some applications and interpretations of it; § 2 is devoted to a discussion of the idea underlying the proof of the theorem, and other matters, including the relationship between the two Recursion theorems. A more general version of the second Recursion theorem is proved in § 3, and is used to give the proof of Myhill’s theorem. 1. The second Recursion theorem First let us prove the theorem, and then see how we can under- stand it 1.1, Theorem (The second Recursion theorem) Let be. total unary computable function; then there isa numbern such that bpm) = bn Proof. By the s-m-n theorem there is a total computable function s(x) such that for all x OD branienY = Fueald1 The second Recursion theorem 201 (If é.(2) is undefined, we mean the expression on the left of (*) to be undefined; alternatively, we can take the left of (*) to denote wol(be(2)) 9) Now take any m such that s= dq; rewriting (*) we have Spain) =baq¢00(9) ‘Then, putting x =m and taking m = dm(m) (which is defined, since dm is total) we have brm¥) = Oa) as required, 0 In spite of its appearance, for non-extensional functions f this is not a senuine fixed-point theorem: there is no induced mapping, > dyuy of computable functions for which $4 could be called a fixed point. However, we do have an induced mapping f* of programs given by PAUP.) = Pron ‘To expecta fixed point for /* in general would be too much: this would be ‘program P, such that f*(P,) and P, are the same; ve. f(n) =n. Butwhat theorem 1.1 saysis that there isa program P, such that /*(P,) and P, have the same effect (when computing unary functions);i.e. dy.) 4. Thus the second Recursion theorem is loosely called a pseudo-fixed point theorem; and for convenience, any number n such that dj .)= 4. is called a fixed point or fixed point value for f. “The second Recursion theorem is result about indices for computable functions; it may be thought therefore that the proof rests on some special feature of the particular numbering of programs that has been chosen. Inspection of the proof shows, however, that we used only the s-m-n theorem and the computability ofthe universal function; neither of these results depends in any essential way on the details of our numbering Moreover, theorem 1.1 can be used to establish the second Recursion theorem corresponding to any suitable numbering of programs; see exercise 1.10(9) below. There are various ways in which theorem 1.1 can be generalised, although the idea underlying the proof remains the same. In exercise 1.10(7) we have the generalisation to k-ary functions for k>1; in theorem 3.1 it is shown that a fixed point can be calculated effectively from various parameters that may be connected with f. ‘We continue this section with some corollaries and applications of the second Recursion theorem11 The second Recursion theorem 202 1.2. Corollary If fis a total computable function, there is a number n such that Wray Wa and Ey) = Exe Proof. UE dyn) ny then Whny= Wy and Exn) = 13. Corollary If f is a total computable function there are arbitrarily large numbers n such that bn) = bn: Proof. Pick any number k; take a number ¢ such that b.# bon bree bie Define a function g by ¢ =k, fix) ifx>k. Then g is computable; let m be a fixed point for g. If m=k, then en) = be ¥ by, 8 contradiction. Hence n> k, so fin)= gin) and n is a fixed point for. O sor{ (in exercise 1.10(8) we shall indicate how the proof of theorem 1.1 can be modified to obtain an increasing effective enumeration of fixed points for f) The following corollary summarises the way that the second Recursion theorem is often applied, in conjunction with the s-m-n theorem, 1.4. Corollary Let fx, y) be any computable function; then there is an index e such that ly) =fle, y). Proof. Use the s-m-n theorem to obtain a total computable funetion s such that dyco(y)~f(x, y); now apply theorem 1.1, taking ¢ as a fixed point for s. As simple applications of this corollary, we have LS. Examples (a) There is a number n such that 4,(x)= 2x", all x: apply corollary 1.4 with f(m, x)= x";1 The second Recursion theorem 203 (5) there is a number m such that Wy with fasi={ lundefined otherwise, in}: apply corollary 1.4 0 ity=x, obtaining an index m such that ¢,(y) is defined iff y=. ‘The second Recursion theorem received its name because, like the first Recursion theorem, it justifies certain very general definitions “by recur- sion’, Consider, for example, the following ‘definition’ of a function @., in terms of a given total computable function f' b= bp The function 4, is ‘defined’ effectively in terms of an algorithm for computing itself (coded by the number e). In spite of its appearance as a circular definition, we are told by the second Recursion theorem that there are computable functions ¢ satisfying such a definition. Itis often useful in advanced computability theory to be able to make an even more general definition of afunction d, ‘by recursion’ of the kind bx) = gle), where g is @ given total computable function, Again, think of 8, as defined’ effectively in terms of a code for its own algorithm. Then the second Recursion theorem, in the guise of corollary 1.4, makes this kind of definition meaningful also, We shall use this fact in the Speed-up theorem in the next chapter. ‘We continue this section with some further straightforward, but some~ times surprising, consequences of theorem 1.1. First, we show how itean bbe used to give a simple proof of Rice’s theorem (6-1.7). 1.6. Theorem (Rice). Suppose that Bex G, and let A={x:6,€f}, Then A is not recursive Proof. Leta A and be A.If A is recursive, then the function f given by fix {° iftxeA, > ifxea, is computable, Further, f has the property that eA @ f(x) A, forall x (On the other hand, by theorem 1.1, there is a number n such that bin) = by, 80 fine A & me A, a contradiction.11 The second Recursion theorem 204 Another application of the second Recursion theorem shows, as prom- ised in chapter 4 §2, that the ‘natural’ enumeration of computable functions without repetitions is not computable. 1.7. Theorem Suppose that fs a total increasing function such that (a) ifm An, then bm) rin (8) flr) is the least index of the function dua. Then fis not computable. Proof. Suppose that f satisfies the conditions of the theorem. By (a), f cannot be the identity function, so there must be a number k such that fon (nek), whence, by (6) bam Abn (nZk), On the other hand, iff is computable, then by corollary 1.3 there is a number n= k such that 4yi.)= qa contradiction. Applications of the second Recursion theorem such as the following can be interpreted in anthropomorphic terms. Let P be a program. We can regard the code number y(P) as a description of P. We could regard the program P as capable of self- reproduction if for all inputs x the computation P(x) gave as output its ‘own description, y(P). At frst glance, it would seem difficult to construct, a self-reproducing program P, since to construct P we would need to know y(P), and hence P itself, in advance. Nevertheless, the second Recursion theorem shows that there are such programs, 1.8. Theorem There is a program P such that for all x, P(x) ¥(P); ie. P is self-reproducing. Proof. Ifwe write n for y(P), the theorem says that there is a number such that u(x) n (for all x) ‘To establish this, simply apply corollary 1.4 to the function f(m, x) = m O We turn now to psychology! Recall the notation and terminology of chapter 5. There we defined a total computable function oe, x, ) that1 The second Recursion theorem 205 codes the state of the computation P(x) after 1 steps; oe, x, #) contains information about the contents of the registers and the number of the next instruction to be obeyed at stage ¢. It is clear, then, that complete