Page 19

		Functionals and Operators.

		In this book a functional is a (possibly partial) mapping from either or to N, and an operator is a total mapping from either or .

		Let be a canonical indexing of finite functions.1 is a recursive functional (or, more accurately, an effective continuous functional) if and only if there is an r.e. set A such that, for all and all , . (For all , recursive functionals of type can be defined similarly.) A recursive functional F has the following two topological properties for all and .

		Monotonicity: .

		Compactness: .

		We say that such an F is a total recursive functional if and only if, for all and , .

		We say is a recursive operator if and only if there is a recursive functional such that, for all  a 1, . . .,  a k, x1, . . ., xl,

		In the setting of recursive operators, the analog of both the monotonicity and compactness properties is the following property that holds for all .

		Continuity: , where  s  ranges over finite functions.

		We say  Q  is a total recursive operator if and only if  Q  is a recursive operator such that, whenever  a 1, . . .,  a k are all total, so is .

		Programming Systems.

		A programming system for a class of partial recursive functions is a partial recursive function  n  such that , By convention, if we do not specify a , then is assumed. Intuitively,  n , a programming system for , corresponds to an interpreter for some programming language capable of expressing all the partial recursive functions;  n (p, x) is the result, if any, of running  n -program p on datum x. We typically write  n p(x) in place of  n (p, x). Thus,  n p is the partial recursive function computed by  n -program p and is an effective

		1 The details of this indexing do not matter. All that we care about is that every finite function has an index and that there is a recursive function r such that, for all i, , and is the graph of  s i