Fabien explique le Théorème de l'arrêt à Léon
- Ce que tu voudrais c'est piéger le programme S avec le programme delta
- On va donc faire boucler delta(x) si S(x,x) est égal à 1
- Et faire s'arrêter delta(x) si S(x,x) est égal à 0
- L'argument diagonal va consister à appliquer delta sur delta lui-même
- Donc soit le programme delta de delta boucle, soit il s'arrête.
- Supposons que delta de delta boucle: si delta de delta boucle, S(delta, delta) est égal à 1 mais si S(delta, delta) est égal à 1 alors delta de delta s'arrête Si je boucle je m'arrete, ce qui est absurde. Donc delta de delta s'arrête
- Mais si delta de delta s'arrête , S(delta,delta) est égal à 0 Donc delta de delta boucle
- Si je m'arrête je boucle et si je boucle je m'arrête!
- Contradiction !
