La Complexité de la Complétude de Turing en C
Introduction
La question de savoir si le langage de programmation C est Turing-complet suscite des débats parmi les informaticiens. Bien que des discussions aient eu lieu dans le passé, il semble que la réponse soit négative pour des raisons assez subtiles.
Simulation d’une Machine de Turing
Dans la plupart des langages de programmation, il est possible de simuler une machine de Turing. Cela peut être réalisé par :
- La simulation d’un automate fini à l’aide d’un programme utilisant une quantité limitée de mémoire.
- La représentation de la bande par une paire de listes chaînées d’entiers, qui symbolisent le contenu de la bande avant et après la position actuelle. Déplacer le pointeur implique de transférer la tête d’une liste à l’autre.
Bien qu’une implémentation concrète sur un ordinateur puisse manquer de mémoire si la bande devient trop longue, une version idéale pourrait exécuter le programme de la machine de Turing de manière fidèle. Cela pourrait être réalisé avec du papier et un stylo, ou en utilisant un ordinateur doté de plus de mémoire et un compilateur adapté à une architecture avec une plus grande taille de mot.
Limitations de C
Cependant, cette approche ne fonctionne pas avec le langage C, car il est impossible d’avoir une liste chaînée qui puisse croître indéfiniment : il existe toujours une limite au nombre de nœuds.
Comprendre l’Implémentation en C
Pour saisir pourquoi cela est le cas, il est essentiel de comprendre ce qu’est une implémentation en C. C est en réalité une famille de langages de programmation. La norme ISO C définit la syntaxe et la sémantique de cette famille de langages. C présente de nombreux comportements indéfinis et des comportements définis par l’implémentation. Chaque implémentation de C représente un langage distinct, et le terme « implémentation » désigne en fait une variante de langage.
Dans une implémentation donnée de C, un octet peut avoir $2^{texttt{CHAR_BIT}}$ valeurs possibles. Toutes les données peuvent être représentées sous forme de tableau d’octets : un type t a au maximum $2^{texttt{CHAR_BIT} times texttt{sizeof(t)}}$ valeurs possibles. Ce nombre varie selon les implémentations, mais pour une implémentation donnée, il reste constant.
Limites des Pointeurs
En particulier, les pointeurs peuvent prendre au maximum $2^{texttt{CHAR_BIT} times texttt{sizeof(void)}}$ valeurs. Cela signifie qu’il existe un nombre maximum d’objets adressables. Les valeurs de CHAR_BIT et sizeof(void) sont observables, donc si vous manquez de mémoire, vous ne pouvez pas simplement relancer votre programme avec des valeurs plus grandes pour ces paramètres. Vous exécuteriez le programme sous un langage de programmation différent — une autre implémentation de C.
État Limité des Programmes
Si les programmes d’un langage ne peuvent avoir qu’un nombre limité d’états, alors ce langage n’est pas plus expressif que les automates finis. La partie de C qui est limitée au stockage adressable ne permet au maximum que $n times 2^{texttt{CHAR_BIT} times texttt{sizeof(void*)}}$ états de programme, où $n$ est la taille de l’arbre de syntaxe abstraite du programme. Par conséquent, ce programme peut être simulé par un automate fini avec ce nombre d’états. Si C est plus expressif, cela doit passer par l’utilisation d’autres fonctionnalités.
Profondeur de Récursion
C n’impose pas directement une profondeur de récursion maximale. Une implémentation peut en avoir une, mais elle peut aussi ne pas en avoir. Cependant, comment communiquer entre un appel de fonction et son parent ? Les arguments ne sont pas utiles s’ils sont adressables, car cela limiterait indirectement la profondeur de récursion. Par exemple, si vous avez une fonction int f(int x) { … f(…) …}, toutes les occurrences de x dans les frames actives de f ont leur propre adresse, et donc le nombre d’appels imbriqués est limité par le nombre d’adresses possibles pour x.
Utilisation de Stockage Non-Adressable
Un programme C peut utiliser un stockage non-adressable sous la forme de variables register. Les implémentations « normales » ne peuvent avoir qu’un nombre limité de variables sans adresse, mais en théorie, une implémentation pourrait permettre une quantité illimitée de stockage register. Dans une telle implémentation, vous pourriez effectuer un nombre illimité d’appels récursifs à une fonction, tant que ses arguments sont register. Cependant, comme les arguments sont register, vous ne pouvez pas créer de pointeur vers eux, ce qui nécessite de copier explicitement leurs données : vous ne pouvez passer qu’une quantité finie de données, et non une structure de données de taille arbitraire composée de pointeurs.
Conclusion
Avec une profondeur de récursion illimitée et la restriction selon laquelle une fonction ne peut obtenir des données que de son appelant direct (arguments register) et renvoyer des données à son appelant direct (valeur de retour de la fonction), vous obtenez la puissance des automates à pile déterministes.
Il est difficile de trouver une manière d’aller plus loin dans cette discussion. Bien sûr, il serait possible de stocker le contenu de la bande à l’extérieur, via des fonctions d’entrée/sortie de fichiers. Mais cela soulèverait une question différente : celle de savoir si C, associé à un système de stockage infini, est Turing-complet, à laquelle la réponse serait un ennuyeux « oui ».
