1
$\begingroup$

The function is fib = λn(IF (n<2) 1 (fib(n-1)+fib(n-2)) (if n<2 then 1, else the sum of the previous two). How do I make it non-recursive? I know it's about making a function H such that H(fib)=H and Y such that H(YH) = fib, but I'm not sure how to do it.

$\endgroup$
  • $\begingroup$ You have to use pairs, [Fib(n+1), Fib(n)] = G([Fib(n), Fib(n - 1)]. Define G with your fixed point operator, then wrap it in a way to extract the proper element of the pair. Or if not using a fixed point operator, you can actually use Church numbering since $nGx = G^n(x)$. $\endgroup$ – DanielV Jun 6 '18 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.