L'argument diagonal

L'argument diagonal. On considère des fonctions qui, à tout entier $n \geq 0$ , associent $0$ ou $1$ . En voici cinq, rangées dans une liste :


fonctions = [lambda n: 0,
             lambda n: n % 2,
             lambda n: 1 if n < 3 else 0,
             lambda n: 1,
             lambda n: n // 2 % 2]

def diagonale(n):
    return 1 - fonctions[n](n)

Calculer fonctions[i](i) pour $i$ de $0$ à $4$ , puis diagonale(i). Montrer que diagonale est différente de chacune des cinq fonctions de la liste.
Justifier que, pour toute liste (finie ou infinie) $f_{0}, f_{1}, f_{2}, \dots$ de fonctions à valeurs dans ${0, 1}$ , la fonction $D (n) = 1 - f_{n} (n)$ n'est égale à aucune des $f_{i}$ .
Un programme Python est un texte fini. Expliquer comment on pourrait ranger tous les programmes Python dans une liste $P_{0}, P_{1}, P_{2}, \dots$ dans laquelle chacun a un rang.
On note $f_{i}$ la fonction calculée par $P_{i}$ (en convenant que $f_{i} (n) = 0$ si $P_{i}$ ne s'arrête pas sur $n$ ou ne renvoie ni $0$ ni $1$ ). En déduire qu'il existe des fonctions, des entiers naturels dans ${0, 1}$ , qu'aucun programme ne calcule.

Énoncé

Exercices semblables