. §-théorème-de, Étant donné le code d'un algorithme A, on peut bien sûr déterminer si l'algorithme contient une boucle while, ou d'autres propriétés syntaxiques. Mais ce que le théorème de Rice interdit, c'est de déterminer une propriété sémantique, c'est-à-dire une propriété du problème résolu par l'algorithme : est-ce que l'algorithme répond toujours True ? est-ce que l'algorithme termine sur l'entrée "0" ? est-ce qu'il existe au moins une entrée sur laquelle l'algorithme ne boucle pas ? Si A est un algorithme (chaîne de caractères représentant un programme Python), on note ? A la fonction que cet algorithme calcule, Rice Turing avait déjà remarqué dans son article de 1936 que puisqu'on ne peut décider l'arrêt d'un programme, beaucoup d'autres caractéristiques d'un programme ne sont pas non plus calculables, 1953.

, Théorème 3.11 Soit P une fonction de l'ensemble des fonctions partielles dans {0, 1}, non triviale : il existe au moins un algorithme F tel que P(? F ) = 0 et un algorithme V tel que P(? V ) = 1. Le problème suivant est incalculable

, On insiste sur un point : quelque soit la fonction P, le problème est non-calculable ! Même la propriété la plus simple qu

, On va montrer qu'à partir d'un algorithme pour cette fonction P, on peut déduire un algorithme pour le problème de l'arrêt. Puisque ce dernier est incalculable, on arrive à la conclusion qu'il ne peut pas exister d'algorithme pour P. Supposons donc qu'il existe un algorithme propriete tel que propriete(A) renvoie True si P(? A ) = 1 et False sinon. On définit l'algorithme boucle qui boucle sur toute entrée (on peut utiliser while True: pass pour cela)

, Autrement dit, ? algo = ? V . Mais si A ne s'arrête pas sur l'entrée m, algo ne s'arrête sur aucune entrée puisqu'il ne dépasse jamais la ligne x = universel(A,m)

, Puisque P(? V ) = 1 et P(? boucle ) = 0, déterminer la valeur de P(? algo ) permet de savoir si ? algo = ? V ou si ? algo = ? boucle , donc de déterminer si A s'arrête sur l'entrée m. Donc propriete permet de résoudre le problème de l'arrêt. Or c'est impossible

, On peut avoir l'impression que la même preuve fonctionnerait pour les fonctions calculables, pour montrer que le programme universel n'est pas lui-même calculable. L'argument ne fonctionne pas pour les fonctions calculables, car rien n'assure que l'application du programme diagonal à son code termine, Si on définit def diagonal(algo): return not universel

§. Fonctions-d'ackermann-péter and L. , une des premières fonctions qui a été montrée non récursive primitive est la fonction d'Ackermann. On présente une version plus simple due à Péter et Robinson, et appelée. . . fonction d'Ackermann-Péter 28 . Cette fonction étant calculable, on fournit le programme Python correspondant (qu'il est déconseillé de lancer avec des valeurs supérieures à 3

, def AckPeter(m,n): if m == 0: return n+1 if n == 0: return AckPeter(m-1, 1) return AckPeter(m-1, AckPeter(m

, Il est déjà non trivial que la fonction termine sur toute entrée (m, n) ? 2 . Pour le démontrer, on définit un ordre sur les couples : (m, n) ? (m , n ) si m < m ou (m = m et n < n )