Several notions of computability have been defined before every one agreed that Turing Machines are the good model of computation, a statement raised to the widely accepted Church-Turing Thesis. However, since then, lots of stronger computability notions have been defined and studied, for the sake of math and because it gives us new insight on some already existing fields.

In this talk, we will see two ways to extend usual computability: by defining a more powerful model, or in a more set theoretic fashion. The first method is used to define Infinite Time Turing Machine, a model where Turing Machines are allowed to compute throught infinite time (that is, throught the ordinals instead of the integers). It has a lot of links with admissibility theory. The second method is used to define alpha-recursion, where alpha is any admissible ordinal. It is an abstract and very general definition of computation. Even if it has a very set-theoretic basis, it reflects the idea of computation and contains the notions of Turing Machine and Infinite Time Turing Machines computabilities. It also includes Higher Computability.

By investigating which properties on the extensions are needed to lift theorems to the new setting, we are able to isolate the important properties of the classical case. We also apply these generalized recursion theories to define randomness, in the same way that we did in the classical case: a string is said to be random if it has no exceptionnal properties, in a computable sense. Our new definition of computation then gives use new definition of randomness.

(No prior knowledge on set theory is assumed.)