Connexion élèves

Choisir le(s) module(s) à installer :

Calculabilité et décidabilité

Au delà de tout problème de complexité, de rapidité d'exécution ou de puissance des machines, il existe des limites théoriques à ce que peut faire un ordinateur.
Nous allons aborder dans cette partie un aspect très théorique de l'informatique à travers les limites des problèmes que peut résoudre cette science.
Nous supposerons que tous les modèles de calcul sont "équivalents". Cela nous permettra d’utiliser des programmes en Python sans perdre de généralité du propos : ce que ne pourra pas effectuer un programme en python ne sera pas réalisable ici, par un autre type de langage.
C'est cette généralité qui a été présentée par Church dans sa célèbre thèse
Dans sa célèbre thèse, Alonzo Chruch a défini la calculabilité théorique

Calculabilité

Une fonction calculable désigne une fonction mathématique f pour laquelle il existe un algorithme permettant de trouver f(x) pour tout élément x.
Il va de soit que les fonctions mathématiques que vous connaissez sont toutes calculables : et il n'est pas facile de trouver une fonction non calculable "simple" bien sûr.
Nous allons donc tenter d'ébaucher un raisonnement nos permettant d'entrevoir l'existence de telles fonctions.

Ensembles infinis dénombrables et non dénombrables

Il existe deux types d'ensembles infinis en mathématiques. Pour les ensembles infinis dénombrables, il est possible de "numéroter" chaque élément de l'ensemble.
Par exemple

Ensemble des fonctions et des algorithmes

Nous allons nous intéresser à deux ensembles infinis : L'ensemble des algorithmes est formé de textes écrits dans un certain alphabet.
Si l'on classe ces algorithmes par ordre alphabétique il est possible de les numéroter.
L'ensemble des algorithmes est donc dénombrable.
Il est possible de démontrer que l'ensemble des fonctions n'est pas dénombrable.
De ces deux constations :
  • L'ensemble des algorithmes est dénombrable
  • L'ensemble des fonctions est non-dénombrable
On peut conclure qu'il y a "plus" de fonctions que d'algorithmes, et que donc certaines fonctions ne peuvent être calculées par un algorithme.

Décidabilité

Le problème de la décidabilité est proche de celui de la calculabilité. Cette fois on ne va pas chercher à calculer la valeur d'une fonction mais nous allons tenter de répondre à une question par oui ou par non.
S'il n'est pas possible de trouver un algorithme permettant de répondre par oui ou par non à un problème, nos dirons que ce problème est indécidable

Un classique : le problème de l'arrêt

Nous allons enfin pouvoir traiter complètement un problème de décidabilité :
le problème de l'arrêt.

Énonce du problème

Une des angoisses des codeurs est de savoir si leur programme ne va pas "tomber" dans une boucle infinie.
Il serait donc judicieux d'ajouter à notre environnement de développement, en plus de l'analyse syntaxique une fonction qui teste notre programme et vérifie s'il ne va pas tourner infiniment.
Le problème de l'arrêt, c'est étudier l'existence d'un algorithme capable de dire si un programme va tourner infiniment ou non.
On pourrait imaginer une technique :
On exécute le programme et on attend assez longtemps....10s ? 1h , 10h, 1 an ? et on regarde si il se termine...
Une telle technique ne va bien sur pas fonctionner, il faudrait plutôt inventer une analyse du texte du programme qui dise si le programme va boucler infiniment ou non ...

Démonstration

Construction
Pour savoir si le problème de l'arrêt est décidable ou non, nous donc allons supposer dans un premier temps qu'une fonction permettant de savoir si un programme va tourner infiniment ou non existe.
Nous allons donc raisonner par l'absurde.
Voici donc notre fonction : 

def H(programme,x):
	'''
	programme est une fonction
	x est un paramètre de cette fonction
	La fonction H renvoie:
	True si programme(x) se termine
	False si programme(x) ne se termine pas
	'''
	...
	if ...:
	# si le programme s'arrête sur l'entrée x
		return True
	else:
		return False
Exécution de la fonction H
Comme vous le voyez on a un peu éludé le "cœur" de la fonction H...On verra plus tard.
On remarque ici que programme() est un paramètre de la fonction H.
Un programme peut donc être le paramètre d'une fonction !
Arrivé à ce stade, si l'on veut raisonner par l'absurde, il faut arriver à une situation absurde (logique).
Pour cela nous allons inventer une nouvelle fonction X (entièrement écrite celle là). 
	
def X(programme):
	if H(programme,programme)==True:
		while True:
			continue
	else:
		return True
Deux questions peuvent apparaître alors :
  1. A quoi sert cette fonction ?
  2. Comment peut-on avoir l'idée de construire une telle fonction ?
Pour la question 1. c'est assez simple,cette fonction a pour seul but de nous faire aboutir à une situation absurde
Pour la question 2. c'est assez simple aussi. En 1936, Alan Turing à fondé cette idée qui a été reprise ensuite et simplifiée. Bref cette fonction est le résultat de réflexions de chercheurs cherchant à résoudre le problème de l'arrêt.
Alan TUring en 1938
Essayons tout de même d'analyser le code de cette fonction :
Raisonnement
Voila, nous sommes arrivés à la fin de notre construction. Il va falloir maintenant l'utiliser !
Nous allons tenter de voir ce que renverrait l'appel suivant de fonction X :
			
print(X(X))
Commençons donc notre analyse :
L'appel de X(X) va commencer, dès la première ligne, par le test : 
	
if H(X,X):
Bon , nous ne pouvons pas savoir ce qu'il va se passer à ce niveau, mais une chose est sure, la fonction H ne peut renvoyer que deux choses : True ou False. Examinons donc ces deux possibilités :