Retour à la page du séminaire

3/02/2000 : Martin H. Escardo
Lawson computability

(Joint work with Frederic de Jaeger and Gabriele Santini).

Motivated by a question on effective real analysis concerning computability of compact sets of real numbers, we introduced a notion of computability for effectively given domains that is stronger than the usual notion of computability. We refer to the usual and the strong notions as Scott and Lawson computability respectively. In essence, these two notions generalize the distinction between recursively enumerable and recursive set of natural numbers. In the talk I'll introduce the notions and give many concrete examples, starting from the standard ones and then considering the ones that arise in effective real analysis.