Ludovic Patey (équipe de Logique de l'IMJ, Paris Rive Gauche)

There exists a strong interplay between computational power and the ability to compute fast-growing functions. For example, any function \(f\) such that \(f(e)\) is larger than the halting time of the \(e\)-th program, computes the halting set.

In this presentation, we give a survey of this correspondence in Computability Theory. In particular, we give a characterization of the sets which can be computed by sufficiently fast-growing functions.