Fast-growing functions in Computability Theory

Patey Ludovic (é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.