I'm currently studying some of the history of computation / computability, in the early days known as recursion theory.

I see Goedel's definition of recursive functions seems significant in his paper, and Church uses his own definition of recursive functions (in particular, primitive recursive functions).

Wikipedia talks about primitive recursive functions and seems to follow Church's definition, but compares it to u-recursive functions as well.

Other definitions online don't seem to correspond with Church's or Goedel's definition.

Can anyone clarify for me exactly who defined "recursion" in what way. Why it was defined that way. How it evolved and why it evolved.

It would very much help me join the dots in this difficult quest towards understanding the foundations of computer science.

  • 1
    $\begingroup$ Check out this by R. Soare. I have not read all of it, but I guess section 2 will help. $\endgroup$
    – Beleg
    May 26, 2018 at 19:43


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.