My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this.

Is this true?

Thanks, friends :)


1 Answer 1


Suppose you have two mutually recursive maps $f, g : \mathbb{N} \to \mathbb{N}$ defined by \begin{align*} f(n) &= \Phi(f, g, n), \\ g(n) &= \Psi(f, g, n) \end{align*} We may replace this with a single recursive map $h : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$, where $h(n) = (f(n), g(n))$, so that $f(n) = \pi_1(h(n))$, $g(n) = \pi_2(h(n))$. Then the above recursive definition may be rewriten as $$ h(n) = (\Phi(\pi_1 \circ h, \pi_2 \circ h, n), \Psi(\pi_1 \circ h, \pi_2 \circ h, n)) $$ The above trick is very general and works in many situations. Regarding primitive recursion, we just have to verify that the passage between $f, g$ and $h$ preserves the primitive recursive nature of functions, which it does because pairing, projections and compositions are primitive recursive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.