Free Trial

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

Share this Page URL

Chapter 4. Recursive Enumerability > 4.2 Parameters - Pg. 93

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