16:00
Modular arithmetic in the lambda-calculus
Abstract
The lambda-calculus was invented to formalise arithmetic by encoding numbers and operations as abstract functions. We will introduce the lambda-calculus and present two encodings of modular arithmetic: the first is a recipe to quotient your favourite numeral system, and the second is purpose-built for modular arithmetic. A highlight of the second approach is that it does not require recursion i.e., it is defined without fixed-point operators. If time allows, we will also give an implementation of the Chinese remainder theorem which improves computational efficiency.