Développement : Caractérisation des ensembles Récursivement Énumérables

Détails/Enoncé :

Les assertions suivantes sont équivalentes:

1. $A$ est dans $\mathrm{RE}$,
2. $\exists B\subset \mathbb{N}^2$ primitif récursif tel que $A=\pi^2_2(B)$,
3. $A=\varnothing$ ou $A$ est l’image d’une fonction primitive récursive,
4. $A$ est l’image d’une fonction récursive.

Autres années :