Calculabilité

On peut aussi affecter une variable par une fonction (ici en JavaScript, mais le fonctionnement en Python est similaire) :

I/ Type des programmes Python

1) Solution de la tour d'Hanoï

On modélise les aiguilles par des piles a, b, c :

a = list(range(3,0,-1))
b = []
c = []

Les aiguilles sont a, b, c dans l'ordre (de gauche à droite). Ce sont des listes Python mais on les traite comme des piles (on n'utilise que append et pop sur elles).

Une solution de la tour d'Hanoï est une suite de mouvements (d'un seul disque chacun) entre aiguilles. Un mouvement entre les piles L et M consiste à

• Enlever (dépiler) le disque en haut de L.
• Puis mettre ce disque (empiler) sur la pile M.

On note m (comme mouvement) la fonction qui effectue ce mouvement. Elle accepte en arguments la pile dont on enlève un disque, et celle où on le transfère :

def m(L,M):
    M.append(L.pop())

2) Écriture de la solution

Avec 3 disques, on peut vérifier que cette suite d'instructions résout le problème :

m(a,b); m(a,c); m(b,c); m(a,b); m(c,a); m(c,b); m(a,b);

Cela se lit :

1. Bouger un disque de a vers b;
2. Bouger un disque de a vers c;
3. Bouger un disque de b vers c;
4. Bouger un disque de a vers b;
5. Bouger un disque de c vers a;
6. Bouger un disque de c vers b;
7. Bouger un disque de a vers b.

On constate qu'un programme Python est une chaîne de caractères.

3) Exécution du programme

La fonction exec (acceptant en entrée une chaîne de caractères, supposée syntaxiquement correcte en Python) a pour effet d'exécuter le programme Python.

exec("m(a,b); m(a,c); m(b,c); m(a,b); m(c,a); m(c,b); m(a,b);")
print(a,b,c)

[] [3, 2, 1] []

4) Fabrication du programme

Pour fabriquer un programme Python, il faut donc une fonction qui renvoie une chaîne de caractères. Par exemple cette fonction récursive :

• On déplace récursivement les n-1 disques du dessus, vers le 3^e piquet (celui qui n'est ni le piquet de départ, ni le piquet d'arrivée).
• On déplace le disque restant, du piquet de départ vers le piquet d'arrivée.
• On redéplace récursivement les n-1 disques du dessus, depuis le 3^e piquet vers le piquet d'arrivée.

Cet algorithme est un exemple du principe diviser pour régner :

• on ramène la résolution de Hanoi pour n disques, à
• la résolution pour n-1 disques,
• la résolution pour 1 disque ;
(diviser)
• puis la construction de la solution à partir de ces solutions partielles (régner).

La fonction ne résout pas le problème, elle ne fait que renvoyer un programme (suite d'instructions) le résolvant :

def Hanoi(I,J,K,n):
    if n==0:
        return ""
    else:
        return Hanoi(I,K,J,n-1) + "m("+I+","+J+"); " + Hanoi(K,J,I,n-1)

Pour que les disques bougent vraiment, il faut faire quelque chose comme

exec(Hanoi("a","b","c",3))

5) Autres exemples

Les interpréteurs et compilateurs travaillent aussi sur des chaînes de caractères (code source).

II/ Arrêt des programmes

1) Un mini-langage

On considère des programmes qui, à part l'instruction initiale x = 1, ne possèdent que deux instructions :

x += 1;
x *= 2;

On demande une fonction Python, qui, à un entier n, associe un programme écrit dans ce mini-langage et aboutissant à x==n. Par exemple un programme aboutissant à 42 est

x = 1
x *= 2
x *= 2
x += 1
x *= 2
x *= 2
x += 1
x *= 2

2) Solution

En notant i (comme incrémentation) l'instruction x += 1 et d (comme doublement) l'instruction x *= 2, la fonction suivante donne le programme le plus court (algorithme glouton) :

def programme(n):
    assert n==int(n) and n>0
    d = " x*=2;"
    i = " x+=1;"
    if n==1:
        return "x=1;"
    else:
        if n%2:
            return programme(n-1)+i
        else:
            return programme(n//2)+d

Appliquée au nombre 42, cette fonction donne le programme

x=1; x*=2; x*=2; x+=1; x*=2; x*=2; x+=1; x*=2;

et on obtient bien l'affichage de 42 avec

exec("x=1; x*=2; x*=2; x+=1; x*=2; x*=2; x+=1; x*=2;")
print(x)

3) Avec une boucle

Le programme suivant se termine aussi (sur x==8):

exec("x=0\nwhile(x<8): x+=1;")

Pour le prouver, on peut utiliser 8-x comme variant.

Mais celui-là ne se termine pas :

exec("x=1\nwhile(x>0): x+=1;")

Plus précisément, la chaîne de caractères x=0\nwhile(x<8): x+=1; correspond à un programme qui se termine, alors que la chaîne de caractères x=1\nwhile(x>0): x+=1; est un programme qui ne se termine pas.

4) Test de terminaison

On cherche une fonction à valeur booléenne se_termine qui accepte en entrée une chaîne de caractères (supposée représenter un programme Python à la syntaxe correcte) et qui renvoie True si ce programme se termine, et False si le programme ne se termine pas :

def se_termine(programme: string) -> bool:
    ....
    if ....:
        return True
    else:
        return False

III/ Théorème de Turing

1) Utilisation du test de terminaison

En supposant construite la fonction se_termine, Alan Turing a construit en 1936 la fonction suivante :

def T(programme):
    if se_termine(programme):
        x = 1
        while x>0:
            x += 1
    else:
        return True

À partir d'une chaîne de caractères P (représentant un programme Python), la chaîne

programmeT = "T(" + P + ")"

produit une chaîne de caractères dont l'exécution renvoie True si P ne se termine pas, et boucle sans fin si P se termine.

2) Théorème

Que se passe-t-il si on applique la fonction T à la chaîne de caractères programmeT ?

Cela prouve par l'absurde que la fonction se_termine ne peut pas être calculée (en Python) :

Théorème (Turing, 1936) : il n'existe pas d'algorithme permettant de prouver la terminaison de n'importe quel programme (Python)

IV/ Calculabilité

1) Corollaire

Il existe des fonctions non calculables (en Python)

2) Démonstration

La fonction se_termine en est un exemple.