Mathematics and Computation

A puzzle about typing

While making a comment on Stackoverflow I noticed something: suppose we have a term in the $\lambda$-calculus in which no abstracted variable is used more than once. For example, $\lambda a b c . (a b) (\lambda d. d c)$ is such a term, but $\lambda f . f (\lambda x . x x)$ is not because [...]

On the Bourbaki-Witt Principle in Toposes

With Peter LeFanu Lumsdaine.

Abstract: The Bourbaki-Witt principle states that any progressive map on a chain-complete poset has a fixed point above every point. It is provable classically, but not intuitionistically. We study this and related principles in an intuitionistic setting. Among other things, we show that Bourbaki-Witt fails exactly when the trichotomous ordinals form a set, but does not [...]

HoTT Equivalences

On December 6th 2011 I gave a talk about homotopy equivalences in the context of homotopy type theory at our seminar for foundations of mathematics and theoretical computer science. I discuss the differences and relations between isomorphism (in the sense of type theory), an adjoint equivalence, and a homotopy equivalence. Even though the talk itself was [...]

How to make the “impossible” functionals run even faster

A talk given at “Mathematics, Algorithms and Proofs 2011″ at the Lorentz Center in Leiden, the Netherlands. I explain how to use computational effects to speed up Martin Escardo’s [...]

Embedding the Baire space into natural numbers

A talk given at “Computation with Infinite Data: Logical and Topological Foundations” Dagstuhl seminar 11411. I describe a realizability model based on infinite-time Turing machines in which it is possible to embed the Baire space (infinite sequences of numbers) into the space of numbers.

Also see the post Constructive gem: an injection from Baire space to natural [...]