Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Recursive Enumerability 93 4.2 Parameters Next we want to turn our attention to the subject of calculating programs. That is, suppose we want a program that will meet some particular need. Possibly we have a good reason to know that a program exists that meets the need. But we might want more than that; we might want actually to find such a program. For example, we know that every total constant function is computable. (As noted in item 2 in Chapter 2, every such function is primitive recursive.) But even more is true. Given a constant k, we can actually compute an index of the one-place function that is constantly equal to k. See Exercise 4 in Chapter 3. For another example, we have recently seen that the range of any computable partial one-place function [[e]] is an r.e. set, and therefore is W y for some y. That is, there exists some index y of a function whose domain is the set we want. But a stronger fact is true: Given e, we can actually compute such a number y. (We will see a proof of this later.) That is, there is a computable function f such that ran [[e]] = W f (e) for every e. For a third example, suppose we have a two-place computable partial function f . Then, clearly the one-place function g obtained by holding the second variable fixed