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:
“An Englishman, methinks,—not to speak of other European nations,—habitually regards himself merely as a constituent part of the English nation; he is a member of the royal regiment of Englishmen, and is proud of his company, as he has reason to be proud of it. But an American—one who has made tolerable use of his opportunities—cares, comparatively, little about such things, and is advantageously nearer to the primitive and the ultimate condition of man in these respects.”
—Henry David Thoreau (1817–1862)