Course-of-values Recursion - Equivalence To Primitive Recursion

Equivalence To Primitive Recursion

In order to convert a definition by course-of-values recursion into a primitive recursion, an auxiliary (helper) function is used. Suppose that one wants to have

.

To define f using primitive recursion, first define the auxiliary course-of-values function that should satisfy

Thus encodes the first n values of f. The function can be defined by primitive recursion because is obtained by appending to the new element :

,

where append(n,s,x) computes, whenever s encodes a sequence of length n, a new sequence t of length n + 1 such that t = x and t = s for all i < n (again this is a primitive recursive function, under the assumption of an appropriate Gödel numbering).

Given, the original function f can be defined by, which shows that it is also a primitive recursive function.

Read more about this topic:  Course-of-values Recursion

Famous quotes containing the word primitive:

    Cannibalism to a certain moderate extent is practised among several of the primitive tribes in the Pacific, but it is upon the bodies of slain enemies alone; and horrible and fearful as the custom is, immeasurably as it is to be abhorred and condemned, still I assert that those who indulge in it are in other respects humane and virtuous.
    Herman Melville (1819–1891)