Page 20

		indexing of the partial recursive functions. We often refer to p as the  n -index of the function Up and typically drop the " n -" prefix when  n  is understood.

		Fix a programming system  n . For each i, define . Recall that a set is recursively enumerable if and only if the set is the domain of some partial recursive function. Thus it follows that is an indexing of the recursively enumerable sets. We sometimes say that i is the v-grammar for .

		An acceptable programming system  n  is a programming system with the additional property that: for all other programming systems  y , there is a recursive function t, such that, for all p,

		One can think of t as an effective translator of  y -programs into equivalent  n -programs (i.e., a compiler). Thus, ' n  is acceptable' means that  n  has the maximality property that, given any other programming system  y  there is an effective way of re-expressing  y -programs as  n -programs. Almost any reasonable formalism for the partial recursive functions (e.g., Turing machines, Algol 60, Fortran, ML, etc.) corresponds to an acceptable programming system, although it is not hard to construct nonacceptable programming systems. We fix one particular acceptable programming system as our standard and let  j  denote it. For ease of notation, we often drop  j  from .

		All acceptable programming systems satisfy the following theorem (stated for  j ) due to Kleene.

		2.1 Theorem (The S-m-n Theorem) For each m, and n> 0, there is a recursive function such that, for all p, x1,. . ., xm, and y1, . . . ,yn in N,

		Moreover, one can take each function to be one-one and monotone increasing in each of its arguments.

		To help see the import of this theorem, consider the m = n = 1 case and think of p as a program with its only input statement as:

		input (a, b)

		Then, intuitively, the program s(p, x) is the modification of p produced by replacing the input statement by: