1-05. Calculabilité & décidabilité

• Comprendre que tout programme est aussi une donnée.

Un programme informatique est traditionnellement perçu comme un ensemble d’instructions qui permet à un ordinateur d’accomplir une tâche. Mais tout programme est également une donnée qui peut être manipulée par un autre programme.

Exemple simple

		# Le code comme donnée - une chaîne de caractères
		code_source = """
		def addition(a, b):
			return a + b
			
		resultat = addition(5, 3)
		print(resultat)
		"""

		# Exécution du code stocké dans une variable
		exec(code_source)  # Affichera 8
	

Dans cet exemple, code_source est une simple variable contenant du texte (des données), mais ce texte représente aussi un programme Python valide qui peut être exécuté par la fonction exec().

• Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé.
• Montrer, sans formalisme théorique, que le problème de l’arrêt est indécidable.

Définition

La calculabilité est un concept d’informatique théorique qui s’intéresse à déterminer quels problèmes peuvent être résolus par un algorithme.

En d’autres termes, un problème est calculable si on peut écrire un programme qui se termine toujours et donne toujours la bonne réponse

En conséquence  :

• Si un problème est calculable en Python, il l’est aussi en Java, C++, ou n’importe quel autre langage de programmation complet.
• Si un problème est prouvé non calculable, aucun langage de programmation ne pourra le résoudre.

Le problème de l’arrêt

Un problème décidable est un cas particulier de problème calculable dont la solution est binaire (oui/non, vrai/faux…).

Le problème de l’arrêt consiste à déterminer, pour un programme P et une entrée E, si P s'arrêtera en un temps fini lorsqu'il est exécuté avec l'entrée E.

Ce problème est indécidable (oui, ça nous fait une belle 🦵). Et, vous la réclamiez, la voici : la démonstration par l’absurde de cette affirmation. À savoir refaire pour le bac. Après, vous pourrez l’oublier.

Démonstration de l’indécidabilité du problème de l’arrêt 🥁

Cette démonstration a été trouvée par Alan Turing en 1936.

1. Supposons par l'absurde qu'il existe une fonction arrête(P, E) qui résout le problème de l'arrêt :

• arrête(P, E) renvoie True si le programme P s'arrête avec l'entrée E
• arrête(P, E) renvoie False si le programme P ne s'arrête jamais avec l'entrée E

2. Construisons maintenant un nouvelle fonction appelée paradoxe(P) :

		fonction paradoxe(P) :
			si arrête(P,P) : entrer dans une boucle infinie
			sinon renvoyer True
	

Examinons maintenant les résultats renvoyés par l’instruction paradoxe(paradoxe) :

• Si paradoxe(paradoxe) s’arrête, alors ça signifie arrête(paradoxe,paradoxe) est True. Mais dans ce cas, paradoxe(paradoxe) entre dans une boucle infinie et ne s’arrête donc pas.
• Si paradoxe(paradoxe) ne s’arrête pas, alors il renvoie True et donc s’arrête.

Dans les deux cas, on arrive à un résultat absurde. C’est donc que la fonction arrête(P,E) ne peut pas exister.