J'essayais d'expliquer à quelqu'un que C est Turing-complet et je me suis rendu compte que je ne savais pas si c'était techniquement Turing-complet. (C comme dans la sémantique abstraite, pas comme dans une implémentation réelle.)

La réponse "évidente" (en gros: elle peut traiter une quantité de mémoire arbitraire, de sorte qu'elle peut émuler une machine RAM, donc Turing-complete) n'est pas vraiment correcte, pour autant que je sache, car même si le standard C le permet pour que size_t soit arbitrairement grand, il doit être fixé à une certaine longueur et quelle que soit sa longueur, il est toujours fini. (En d'autres termes, bien que vous puissiez, étant donné une machine de Turing arrêtant arbitrairement, choisir une longueur de size_t telle qu'elle s'exécutera "correctement", il n'y a aucun moyen de choisir une longueur de size_t telle que toutes les machines de Turing s'arrêtant fonctionneront correctement)

Alors: C99 Turing-complete?

Je ne suis pas sûr mais je pense que la réponse est non, pour des raisons plutôt subtiles. J'ai posé des questions sur l'informatique théorique il y a quelques années et je n'ai pas obtenu de réponse allant au-delà de ce que je vais présenter ici.

Dans la plupart des langages de programmation, vous pouvez simuler une machine de Turing en:

• simuler l'automate fini avec un programme utilisant une quantité de mémoire finie;
• simuler la bande avec une paire de listes chaînées d'entiers, représentant le contenu de la bande avant et après la position actuelle. Déplacer le pointeur signifie transférer la tête d'une des listes sur l'autre liste.

Une implémentation concrète exécutée sur un ordinateur manquerait de mémoire si la bande devenait trop longue, mais une implémentation idéale pourrait exécuter fidèlement le programme de la machine de Turing. Cela peut être fait avec un stylo et du papier, ou en achetant un ordinateur avec plus de mémoire et un compilateur ciblant une architecture avec plus de bits par mot, etc. si le programme manque de mémoire.

Cela ne fonctionne pas en C car il est impossible d'avoir une liste chaînée qui puisse s'allonger pour toujours: il y a toujours une limite au nombre de nœuds.

Pour expliquer pourquoi, je dois d’abord expliquer ce que l’implémentation C est. C est en fait une famille de langages de programmation. La norme ISO C (plus précisément une version spécifique de cette norme) définit (avec le niveau de formalité autorisé par l'anglais) la syntaxe et la sémantique d'une famille de langages de programmation. C a beaucoup de comportement indéfini et comportement défini par la mise en œuvre. Une «implémentation» de C codifie tout le comportement défini par l'implémentation (la liste des choses à codifier se trouve dans l'annexe J pour C99). Chaque implémentation de C est un langage de programmation séparé. Notez que la signification du mot «implémentation» est un peu étrange: ce qu’il signifie réellement est une variante de langage, il peut y avoir plusieurs programmes de compilateur différents qui implémentent la même variante de langage.

Dans une implémentation donnée de C, un octet a valeurs possibles. Toutes les données peuvent être représentées sous forme de tableau d'octets: un type a au plus valeurs possibles: . Ce nombre varie selon les implémentations de C, mais pour une implémentation donnée de C, c'est une constante. 2 CHAR_BIT × $2^{\texttt{CHAR_BIT}}$t$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$

En particulier, les pointeurs peuvent uniquement prendre au plus . Cela signifie qu'il existe un nombre maximum fini d'objets adressables.$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$

Les valeurs de CHAR_BITet sizeof(void*)sont observables. Par conséquent, si vous manquez de mémoire, vous ne pouvez pas continuer à exécuter votre programme avec des valeurs plus grandes pour ces paramètres. Vous exécuteriez le programme sous un autre langage de programmation - une implémentation C différente.

Si les programmes dans un langage ne peuvent avoir qu'un nombre limité d'états, le langage de programmation n'est pas plus expressif que les automates finis. Le fragment de C qui est limité au stockage adressable autorise uniquement au plus états de programme où est la taille de l'arborescence de la syntaxe abstraite du fichier. programme (représentant l’état du flux de contrôle), ce programme peut donc être simulé par un automate fini comportant autant d’états. Si C est plus expressif, il doit utiliser d'autres fonctionnalités.$n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$$n$

C n'impose pas directement une profondeur de récursion maximale. Une implémentation est autorisée à avoir un maximum, mais il est également permis de ne pas en avoir. Mais comment pouvons-nous communiquer entre un appel de fonction et son parent? Les arguments ne servent à rien s'ils sont adressables, car cela limiterait indirectement la profondeur de la récursivité: si vous avez une fonction, int f(int x) { … f(…) …}toutes les occurrences des xtrames actives font leur propre adresse et le nombre d'appels imbriqués est donc limité par le nombre des adresses possibles pour x.

Programme AC peut utiliser un stockage non adressable sous la forme de registervariables. Les implémentations «normales» ne peuvent avoir qu'un petit nombre fini de variables qui n'ont pas d'adresse, mais en théorie, une implémentation pourrait permettre une quantité de registerstockage illimitée . Dans une telle implémentation, vous pouvez effectuer un nombre illimité d'appels récursifs à une fonction, tant que ses arguments le sont register. Mais comme les arguments sont register, vous ne pouvez pas leur faire un pointeur et vous devez donc copier leurs données explicitement: vous ne pouvez transmettre qu'une quantité finie de données, pas une structure de données de taille arbitraire composée de pointeurs.

Avec une profondeur de récursion non limitée et la restriction selon laquelle une fonction ne peut obtenir des données que de son appelant direct ( registerarguments) et renvoyer des données à son appelant direct (la valeur de retour de la fonction), vous bénéficiez de la puissance des automates déterministes .

Je ne peux pas trouver un moyen d'aller plus loin.

(Vous pouvez bien sûr faire en sorte que le programme stocke le contenu de la bande en externe, par le biais de fonctions d’entrée / sortie dans un fichier. Mais vous ne voudriez pas demander si C est Turing-complete, mais si C plus un système de stockage infini est Turing-complete . laquelle la réponse est ennuyeux « oui » Vous pourriez aussi bien définir le stockage d'être un oracle de Turing - appel  fopen("oracle", "r+"), fwritele contenu de la bande initiale et fread. retour le contenu de la bande finale)

L'ajout de C99 va_copyà l'API d'argument variadique peut nous donner une porte dérobée à la complétude de Turing. Puisqu'il devient possible de parcourir plusieurs fois une liste d'arguments variadiques dans une fonction autre que celle ayant reçu les arguments à l'origine, vous va_argspouvez utiliser un pointeur sans pointeur.

Bien sûr, une véritable implémentation de l’API à arguments variadiques va probablement avoir un pointeur quelque part, mais dans notre machine abstraite, il peut être implémenté en utilisant la magie.

Voici une démonstration mettant en oeuvre un automate à pile double avec des règles de transition arbitraires:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Remarque: Si va_listest un type de tableau, il existe des paramètres de pointeur masqués vers les fonctions. Il serait donc probablement préférable de changer les types de tous les va_listarguments en wrapped_stack.

Une arithmétique non standard, peut-être?

Donc, il semble que le problème est la taille finie de sizeof(t). Cependant, je pense que je connais un travail autour.

Pour autant que je sache, C n'a pas besoin d'une implémentation pour utiliser les entiers standard pour son type entier. Par conséquent, nous pourrions utiliser un modèle arithmétique non standard . Ensuite, nous sizeof(t)définirions un nombre non standard et nous ne l'atteindrons jamais maintenant en un nombre fini d'étapes. Par conséquent, la longueur du ruban des machines de Turing sera toujours inférieure au "maximum", car le maximum est littéralement impossible à atteindre. sizeof(t)n'est tout simplement pas un nombre au sens habituel du terme.

Ceci est une technicité bien sûr: le théorème de Tennenbaum . Il affirme que le seul modèle d'arithmétique de Peano est le modèle standard, ce qui ne serait évidemment pas le cas. Toutefois, pour autant que je sache, C n’a pas besoin des implémentations pour utiliser des types de données satisfaisant les axiomes de Peano, ni que l’implémentation soit calculable. Par conséquent, cela ne devrait pas poser de problème.

Que devrait-il se passer si vous essayez de générer un entier non standard? Eh bien, vous pouvez représenter n’importe quel nombre entier non standard en utilisant une chaîne non standard.

OMI, une limitation importante est que l'espace adressable (via la taille du pointeur) est fini, ce qui est irrécupérable.

On pourrait préconiser que la mémoire puisse être "permutée sur disque", mais à un moment donné, les informations d'adresse dépasseront elles-mêmes la taille adressable.

En pratique, ces restrictions ne sont pas pertinentes pour la complétude de Turing. La vraie exigence est de permettre à la bande d'être longue et non arbitraire. Cela créerait un problème de blocage d'un type différent (comment l'univers "calcule-t-il" la bande?)

C'est aussi faux que de dire "Python n'est pas complet, parce que vous ne pouvez pas créer une liste infiniment longue".

[Edit: merci à M. Whitledge pour avoir clarifié comment éditer.]

Les supports amovibles nous permettent de contourner le problème de mémoire sans limite. Peut-être que les gens vont penser que c'est un abus, mais je pense que c'est OK et essentiellement inévitable de toute façon.

Corrigez toute implémentation d'une machine de Turing universelle. Pour la bande, nous utilisons des supports amovibles. Lorsque la tête sort de la fin ou du début du disque en cours, la machine invite l'utilisateur à insérer le suivant ou le précédent. Nous pouvons soit utiliser un marqueur spécial pour indiquer l'extrémité gauche de la bande simulée, soit créer une bande non liée dans les deux sens.

Le point clé ici est que tout ce que le programme C doit faire est fini. L'ordinateur n'a besoin que de suffisamment de mémoire pour simuler l'automate, et size_tdoit être assez grand pour permettre d'adresser cette quantité de mémoire (plutôt petite) et sur les disques, qui peuvent être de n'importe quelle taille finie fixe. Etant donné que l'utilisateur est uniquement invité à insérer le disque suivant ou précédent, nous n'avons pas besoin de nombres entiers non liés pour dire "Veuillez insérer le numéro de disque 123456 ..."

Je suppose que la principale objection est probablement liée à la participation de l'utilisateur, mais cela semble être inévitable dans toute implémentation, car il ne semble exister d'autre moyen d'implémenter une mémoire illimitée.

Choisissez size_td'être infiniment grand

Vous pouvez choisir size_td'être infiniment grand. Naturellement, il est impossible de réaliser une telle implémentation. Mais ce n'est pas surprenant, étant donné la nature finie du monde dans lequel nous vivons.

Les implications pratiques

Mais même s'il était possible de réaliser une telle mise en œuvre, il y aurait des problèmes pratiques. Considérez la déclaration C suivante:

printf("%zu\n",SIZE_MAX);

SIZE_MAXSIZE_MAX$O(2^{size\_t})$size_tSIZE_MAXprintf

Heureusement, pour nos besoins théoriques, je n'ai trouvé aucune exigence dans la spécification qui garantisse la printffin de toutes les entrées. Donc, autant que je sache, nous ne violons pas la spécification C ici.

Sur la complétude informatique

Il reste encore à prouver que notre implémentation théorique est Turing Complete . Nous pouvons le montrer en mettant en œuvre "toute machine de Turing à bande unique".

La plupart d'entre nous ont probablement mis en place une machine de Turing en tant que projet scolaire. Je ne donnerai pas les détails d'une implémentation spécifique, mais voici une stratégie couramment utilisée:

• Le nombre d'états, le nombre de symboles et la table de transition d'état sont fixes pour une machine donnée. Nous pouvons donc représenter les états et les symboles sous forme de nombres et la table de transition d'états sous forme de tableau à 2 dimensions.
• La bande peut être représentée comme une liste chaînée. Nous pouvons utiliser une seule liste à double liaison ou deux listes à simple liaison (une pour chaque direction à partir de la position actuelle).

Voyons maintenant ce qui est nécessaire pour réaliser une telle implémentation:

• Possibilité de représenter un ensemble de nombres fixe, mais arbitrairement grand. Afin de représenter n'importe quel nombre arbitraire, nous avons également choisi MAX_INTd'être infini. (Vous pouvez également utiliser d'autres objets pour représenter des états et des symboles.)
• La possibilité de construire une liste chaînée arbitrairement longue pour notre bande. Encore une fois, la taille n’est pas limitée. Cela signifie que nous ne pouvons pas construire cette liste dès le départ, car nous dépenserions toujours pour rien que pour construire notre bande. Cependant, nous pouvons construire cette liste de manière incrémentielle si nous utilisons une allocation de mémoire dynamique. Nous pouvons utiliser malloc, mais il y a un peu plus, nous devons considérer:
  • La spécification C permet mallocd’échouer si, par exemple, la mémoire disponible est épuisée. Ainsi, notre mise en œuvre n’est vraiment universelle que si elle mallocn’échoue jamais.
  • Cependant, si notre implémentation est exécutée sur une machine avec une mémoire infinie, aucun mallocéchec n’est nécessaire . Sans violer le standard C, notre implémentation garantira que malloccela ne faillira jamais.
• Possibilité de déréférencer les pointeurs, de rechercher des éléments de tableau et d'accéder aux membres d'un nœud de liste lié.

La liste ci-dessus est donc ce qui est nécessaire pour implémenter une machine de Turing dans notre implémentation C hypothétique. Ces fonctionnalités doivent être terminées. Cependant, tout le reste peut être autorisé à ne pas se terminer (sauf si requis par la norme). Ceci inclut l'arithmétique, les entrées / sorties, etc.

L'argument principal ici est que la taille de size_t est finie, bien qu'elle puisse être infiniment grande.

Il existe une solution de contournement, bien que je ne sois pas sûr que cela coïncide avec ISO C.

Supposons que vous avez une machine avec une mémoire infinie. Ainsi, vous n'êtes pas lié à la taille du pointeur. Vous avez toujours votre type size_t. Si vous me demandez quel est sizeof (size_t), la réponse sera simplement sizeof (size_t). Si vous demandez s'il est supérieur à 100, par exemple, la réponse est oui. Si vous demandez ce qui est sizeof (size_t) / 2 comme vous pouvez le deviner, la réponse est toujours sizeof (size_t). Si vous voulez l’imprimer, nous pouvons nous mettre d’accord sur certaines sorties. La différence de ces deux peut être NaN et ainsi de suite.

En résumé, assouplir la condition pour size_t a une taille finie ne gâchera pas les programmes existants.

PS L'allocation de sizeof de mémoire (size_t) est toujours possible, vous n'avez besoin que d'une taille dénombrable, alors supposons que vous preniez tous les événements (ou astuce similaire).

Oui, ça l'est.

1. Réponse citée

En réaction au nombre élevé de votes négatifs sur mes (et autres) réponses correctes - par rapport à l'approbation alarmante des fausses réponses - j'ai cherché une explication alternative moins théorique. J'ai trouvé celui- ci. J'espère que cela couvre certaines des idées fausses habituelles, de manière à donner un peu plus de perspicacité. Partie essentielle de l'argumentation:

[...] Son argument est le suivant: supposons que l’on ait écrit un programme de terminaison donné qui peut nécessiter, au cours de son exécution, jusqu’à une quantité de stockage arbitraire. Sans changer ce programme, il est possible a posteriori de mettre en œuvre un composant informatique et son compilateur C offrant suffisamment de mémoire pour permettre ce calcul. Cela peut nécessiter d'élargir la largeur de char (via CHAR_BITS) et / ou des pointeurs (via size_t), mais le programme n'aurait pas besoin d'être modifié. Parce que c'est possible, C est bien Turing-Complete pour terminer les programmes.

La partie délicate de cet argument est que cela ne fonctionne que lorsque vous envisagez de terminer des programmes. Les programmes de terminaison ont cette propriété intéressante qu'ils ont une limite supérieure statique à leur besoin de stockage, ce que l'on peut déterminer expérimentalement en exécutant le programme sur l'entrée souhaitée avec des tailles de stockage croissantes, jusqu'à ce qu'il "s'adapte".

La raison pour laquelle j'ai été induit en erreur dans mes pensées, c'est que je considérais la classe plus large de programmes «utiles» sans fin [...]

En bref, parce que pour chaque fonction calculable, il existe une solution en langage C (due à des limites supérieures illimitées), chaque problème calculable a un programme C, donc C est complet.

2. Ma réponse originale

Il existe une confusion généralisée entre les concepts mathématiques en informatique théorique (tels que la complétude de Turing) et leur application dans le monde réel, c’est-à-dire les techniques en informatique pratique. L'exhaustivité de Turing n'est pas une propriété de machines physiquement existantes ni d'aucun modèle limité dans l'espace-temps. C'est juste un objet abstrait décrivant les propriétés des théories mathématiques.

C99 est complet pour Turing quelles que soient les restrictions d’implémentation, comme pratiquement tous les langages de programmation courants, car il est capable d’exprimer un ensemble de connecteurs logiques fonctionnellement complet et a en principe accès à une quantité de mémoire illimitée. Les gens ont fait remarquer que C restreint explicitement l'accès à la mémoire aléatoire, mais ce n'est pas une chose à ne pas contourner, car ce sont des restrictions additionnelles dans la norme C, tandis que la complétude de Turing est déjà impliquée :

Voici une chose très basique sur les systèmes logiques qui devrait suffire pour une preuve non constructive . Considérons un calcul avec des schémas et des règles axiomes, tels que l'ensemble des conséquences logiques soit X. Maintenant, si vous ajoutez des règles ou des axiomes, l'ensemble des conséquences logiques grandit, c.-à-d. Doit être un sur-ensemble de X. C'est pourquoi, par exemple , la logique modale S4 est correctement contenue dans S5. De même, lorsque vous avez une sous-spécification qui est Turing-complete, mais que vous ajoutez certaines restrictions, celles-ci n'empêchent aucune des conséquences de X, c'est-à-dire qu'il doit exister un moyen de contourner toutes les restrictions. Si vous voulez une langue non complète de Turing, le calcul doit être réduit et non étendu. Les extensions qui prétendent que quelque chose ne serait pas possible, mais le est en réalité, ne font qu'ajouter une incohérence. Ces incohérences dans la norme C peuvent ne pas avoir de conséquences pratiques, tout comme Turing-complétude n’est pas liée à une application pratique.

Simuler des nombres arbitraires en fonction de la profondeur de récursivité (c.-à -d . Avec la possibilité de prendre en charge plusieurs nombres via la planification / pseudo-threads; il n'y a pas de limite théorique à la profondeur de récursivité en C ), ou d'utiliser le stockage de fichiers pour simuler une mémoire de programme illimitée ( idée ) probablement que deux possibilités infinies de prouver de manière constructive la complétude de Turing de C99. Il convient de rappeler que pour la calculabilité, la complexité temporelle et spatiale n’est pas pertinente. En particulier, supposer un environnement limité afin de falsifier la complétude de Turing n'est qu'un raisonnement circulaire, car cette limitation exclut tous les problèmes qui dépassent la complexité présupposée.

( REMARQUE : je n'ai écrit cette réponse que pour empêcher les personnes d'être arrêtées pour acquérir une intuition mathématique en raison d'une sorte de pensée limitée axée sur l'application. Il est dommage que la plupart des apprenants lisent la fausse réponse acceptée car elle a été votée en fonction de défauts fondamentaux de raisonnement, de sorte que plus de gens vont propager de telles fausses croyances. Si vous abaissez cette réponse, vous ne faites que faire partie du problème.)