On peut aussi affecter une variable par une fonction (ici en JavaScript, mais le fonctionnement en Python est similaire) :
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 à
L
.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())
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 :
a
vers b
;a
vers c
;b
vers c
;a
vers b
;c
vers a
;c
vers b
;a
vers b
.On constate qu'un programme Python est une chaîne de caractères.
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] []
Pour fabriquer un programme Python, il faut donc une fonction qui renvoie une chaîne de caractères. Par exemple cette fonction récursive :
n-1
disques
du dessus, vers le 3e piquet (celui qui n'est ni le piquet
de départ, ni le piquet d'arrivée).n-1
disques du dessus, depuis le 3e piquet vers le piquet
d'arrivée.Cet algorithme est un exemple du principe diviser pour régner :
n
disques, à n-1
disques,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))
Les interpréteurs et compilateurs travaillent aussi sur des chaînes de caractères (code source).
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
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)
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.
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
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.
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) :
La fonction se_termine
en est un exemple.