What is Primitive Recursion?

In this video, I explain what a primitive recursive function is, demonstrate various perspectives on the primitive recursive functions, show that various common functions are primitive recursive, and give an intuition behind a fairly robust (but not fully Turing complete) programming language that corresponds to the primitive recursive functions. Let me know if you have questions or comments below! Sources: Most of this video is from Wikipedia: the resources there on primitive recursive functions and related topics are quite good, and you can also find some examples of using very formal notation to specify primitive recursive functions on the "Primitive Recursive Function" page. The material on pairing functions and the idea behind "isOdd" are from Raphael M. Robinson's "Primitive Recursive Functions" (1947). While the first part of this article is mostly very clear to read, note that the use of the function 0^x is genuinely exponentiation, in the combinatoricist's sense, where 0^0 = 1 and 0^x = 0 for x greater than 0. That is, 0^x is just fancy notation for isZero(x). The BlooP language is due to Douglas Hofstadter: https://en.wikipedia.org/wiki/BlooP_a...