|Universiteit Faculteit FNWI English version||21 april 2011, e-mail|
Woensdag 11 mei 2011
AbstractIn this talk two examples will be given.
Alonzo Church was asked to prove for his dissertation that a certain problem was decidable. He could not do it, but came up with the notion of computability.
On a more modest level it will be shown how I tried for my dissertation to make a recursion-theoretic model of the lambda calculus. I did not succeed, but came up with the notions of solvability and the omega-rule in lambda calculus. The latter turned out to be related to Cartesian closed categories having enough points. The former turned out to be essential for understanding Scott's models and Boehm-trees, which is an early example of co-induction.