In this post I just ramble a bit through some mathematician's definition of what a recursive function is...
I am excited to tell you that I just released the alpha version of my “Pydont's” book, a book that compiles all my “Pydon't” articles. You can get the book at leanpub: leanpub.com/pydonts.
In Computation Theory it is of interest to study properties about functions, and what functions satisfy said properties. We then consider the set of all functions that satisfy those properties. One of those sets is the set \(R\) of recursive functions, as defined by Kleene. To define \(R\), Kleene gives a series of different primitive functions that are known to be in \(R\) and then defines some operations that preserve functions in \(R\).
For the purposes of what I will be sharing next, I will just enumerate said primitive functions and constructions, so that the reader is aware of what will be used (notice that what comes below is almost identical to what you can see here).
The primitive functions are:
After that, some constructions are considered, such that functions from \(R\) are sent to functions in \(R\). Said constructions are:
When I learned this I was prompted to define some usual functions in terms of this, for example the addition, the predecessor, multiplication, the factorial, etc. I decided to implement these constructs in Python and then build the non-primitive functions in terms of those. The basic constructs can be found here and the other definitions can be found implemented here.
For the more interested reader, I suggest trying to build some of the non-primitive functions before checking the code. Here is a complete list of the functions I implemented:
If you liked this article and would like to support the mathspp project, then you may want to buy me a slice of pizza 🍕.