En terminale

• Décidabilité
• Preuve de la non décidabilité du problème de l'arrêt
• Calculabilité
• Exercices

Une propriété est décidable si l'on peut déterminer en un nombre fini d'étapes si elle est vraie ou fausse quel que soit le contexte de départ. (On parle de problème de décision, à réponse oui ou non) Attention, cela ne veut pas dire que la propriété doit être toujours fausse ou vraie. Donnons, pour illustrer la définition, des probèmes décidables.

• Savoir si un nombre est premier est décidable. La réponse sera soit 'vrai', soit 'faux' et un algorithme simple est de diviser ce nombre par les entiers inférieurs à lui même. Il y a donc un nombre fini d'étapes et une réponse qui est soit vrai soit faux.
• Dire si un nombre est pair (on regarde le reste de la division Euclidienne par 2)

Les exemples ne manquent pas. On peut alors se poser la question: "tout est-il décidable?". La réponse est non. Si c'était le cas, cela voudrait dire que l'on pourrait prouver qu'une propriété mathématique est vraie ou fausse avec un algorithme !

Donnons des exemples de problèmes non décidables. Je parcours un réseau aléatoirement, est-ce que je vais atteindre une cible données en un nombre fini d'étapes? Pas forcément, même si la probabilité d'arriver à destination tend vers 1 quand le nombre d'étapes tend vers l'infini!

Un autre exemple plus connu: le problème de l'arrêt d'un programme est-il décidable? Est-ce que je peux écrire un programme qui me dira si un programme va s'arrêter ou non (selon les valeurs d'entrées)? Nous verrons que l'on peut prouver que ce problème n'est pas décidable: il n'existe pas d'algorihtme capable de prédire si n'importe quel programme va s'arrêter ou non. Cela vous plairez bien...n'avez vous jamais fait de boucle infinie?

Je rebondis aussi sur la phrase "écrire un programme qui me dira si un programme va s'arrêter ou non". Cela signifie que je considère que le programme à tester est une donnée du programme testeur. Est-ce choquant? Non, lorsque vous utilisez l'idle de python, vous tapez un programme, qui va s'executer grace au programme de Python (votre programme est déjà une donnée puisque vous l'enregistrez), qui lui même est écrit en C et un programme sert à compiler le C en langage assembleur puis va l'écrire en pur code binaire (suite de 0 et de 1). Autre remarque lorsque qu'un compilateur s'arrête pour vous indiquer une erreur, ou qu'un éditeur de texte destiné à la programmation vous indique qu'il y a une erreur dans votre programme....c'est bien un programme qui vérifié votre programme. Bref des programmes qui ont pour donné des programmes c'est très fréquent !

Retenons pour la preuve de la non décidabilité de l'arrêt qu'un programme peut être une donnée d'un autre programme.

Une fonction f est calculable s'il existe un algorithme (en d'autre terme, une machine de turing) capable de donner la valeur de f(x) pour tout x. Il faut entendre ici le mot fonction au sens large! Par exemple: vérifier qu’un programme s’arrête , prouver qu'une formule logique est un théorème.

• Calculer le PGCD est "calculable" par l'algorithme d'Euclide qui termine forcément en un nombre fini d'étapes.
• Sur un graphe, déterminer la longueur du plus court chemin qui passe par tous les sommets. Dans le cas d'un graphe où les arcs ont des poids positifs, l'algorihtme de Dijkstra donne la solution en complexité en temps O ( a + s log ⁡ s ) {\displaystyle O(m+n\log n)} {\displaystyle O(m+n\log n)} pour un un graphe à a {\displaystyle m} a arcs et s {\displaystyle n} s sommets. Ici, il ne s'agit clairement pas d'un problème de décidabilité!

Pour démontrer que le problème de l'arrêt est indécidable(pour rappel, montrer qu'il n'existe pas d'algorithme capable de dire quand une fonction s'arrête ou pas) , nous allons utiliser le raisonnement par l'absurde. Le raisonnement par l'absurde, suppose vrai ce que l'on veut établir comme faux. Par un raisonnement logique on doit aboutir à une contradiction qui établit que ce que l'on a supposé comme vrai...est forcément faux.

Amusons nous avec un peu de logique. Si je vous dis "je mens"...vous avez un soucis!

• Si je suis effectivement un menteur, alors l'affirmation "je mens" est fausse...donc je ne mens pas?
• Si je ne suis pas un menteur, alors je mens en disant que je suis un menteur, je suis donc un menteur?

Passons maintenant à la preuve du problème de l'arrêt.

Supposons que l'on peut écrire un programme arret(code du programme, paramètre), capable de dire si le programme 'code du programme' va s'areter dans tous les cas ou non si il existe des cas où il ne s'arrête pas.

Ecrivons un programme: absurde(code du programme)

absurde(code d'un programme):
	si arret(code du programme,code du programme):
		faire une boucle infinie ici
	sinon
		arreter le programme

Utilisons ce programme absurde en envoyant comme 'code d'un programme', le programme absurde lui même, on lance donc absurde(absurde).

• si Arret(absurde,absurde) s'arrete, cela indique que absurde(absurde) s'arrête et donc le programme absurde(absurde) entre dans une boucle infinie. Il y a contradiction
• si Arret(absurde,absurde) ne s'arrete pas, cela indique que absurde(absurde) ne s'arrête et donc le programme absurde(absurde) s'arrête. Il y a contradiction

Dans tous les cas, on aboutit à une contradiction, cela implique que le programme absurde ne peut pas exister et que par conséquent, une telle fonction arret ne peut exister.

1. blabla
2. blabla