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:
“That primitive head
So ambitiously vast,
Yet so rude in its art,
Is as easily read
For the woes of the past
As a clinical chart.”
—Robert Frost (18741963)