Est-ce que C est vraiment complet?

40

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?

TLW
la source
3
Quelles sont les "sémantiques abstraites" de C? Sont-ils définis n'importe où?
Yuval Filmus
4
@YuvalFilmus - Voir par exemple ici , c'est-à-dire C tel que défini dans la norme, par exemple "c'est comme ça que gcc le fait".
TLW
1
Il y a la "technicité" que les ordinateurs modernes n'ont pas de mémoire infinie comme le TM mais sont toujours considérés comme des "ordinateurs universels". et notons que les langages de programmation dans leur "sémantique" ne supposent pas vraiment une mémoire finie, sauf que toutes leurs implémentations sont bien sûr limitées en mémoire. Voir, par exemple, notre ordinateur fonctionne-t-il comme une machine de Turing ? de toute façon, pratiquement tous les langages de programmation "grand public" sont complets.
vzn
2
C (comme les machines de Turing) ne se limite pas à l’utilisation de la mémoire interne de l’ordinateur pour ses calculs, ce n’est donc pas un argument valable contre la complétude de Turing par C.
reinierpost
@reinierpost - c'est comme dire qu'un télétype est clair. Cela signifie que "C + un équivalent de MT externe" est Turing-complet, pas que C est Turing-complet.
TLW

Réponses:

34

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 × sizeof (t)2CHAR_BITt2CHAR_BIT×taille de (t)

En particulier, les pointeurs peuvent uniquement prendre au plus . Cela signifie qu'il existe un nombre maximum fini d'objets adressables.2CHAR_BIT×sizeof (vide *)

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. nn×2CHAR_BIT×sizeof (vide *)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)

Gilles, arrête de faire le mal
la source
On ne comprend pas tout de suite pourquoi l'ensemble d'adresses devrait être fini. J'ai écrit quelques réflexions dans une réponse à la question que vous liez: cstheory.stackexchange.com/a/37036/43393
Alexey B.
4
Désolé, mais selon la même logique, il n’existe aucun langage de programmation complet de Turing. Chaque langue a une limitation explicite ou implicite de l'espace d'adressage. Si vous créez une machine avec une mémoire infinie, les pointeurs d'accès aléatoire auront évidemment aussi une longueur infinie. Par conséquent, si une telle machine apparaît, elle devra offrir un jeu d'instructions pour l'accès séquentiel à la mémoire, ainsi qu'une API pour les langages de haut niveau.
IMil
14
@ IMil Ce n'est pas vrai. Certains langages de programmation ne limitent pas l'espace d'adressage, même implicitement. Pour prendre un exemple évident, une machine universelle de Turing où l’état initial de la bande forme le programme est un langage de programmation complet de Turing. De nombreux langages de programmation réellement utilisés ont la même propriété, par exemple Lisp et SML. Une langue ne doit pas nécessairement avoir le concept de «pointeur d'accès aléatoire». (suite)
Gilles 'SO, arrête d'être méchant'
11
@IMil (suite) Les implémentations sont généralement destinées à la performance, mais nous savons qu'une implémentation exécutée sur un ordinateur particulier n'est pas Turing-complete car elle est limitée par la taille de la mémoire de l'ordinateur. Mais cela signifie que l’implémentation n’implémente pas la totalité du langage, mais seulement un sous-ensemble (de programmes exécutés sur N octets de mémoire). Vous pouvez exécuter le programme sur un ordinateur et, s'il manque de mémoire, déplacez-le vers un ordinateur plus grand, etc., pour toujours ou jusqu'à ce qu'il s'arrête. Ce serait un moyen valable de mettre en œuvre l'ensemble du langage.
Gilles, arrête d'être méchant
6

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.

feersum
la source
Cela pourrait fonctionner. Un problème possible est qu'il repose sur l'allocation d'un nombre illimité de va_listvariables automatiques stack. Ces variables doivent avoir une adresse &stacket nous ne pouvons en avoir qu'un nombre limité. Cette exigence pourrait être contournée en déclarant chaque variable locale register, peut-être?
chi
@chi AIUI une variable n'est pas obligée d'avoir une adresse à moins que quelqu'un essaie de la prendre. En outre, il est illégal de déclarer l'argument précédant immédiatement les points de suspension register.
Feersum
Selon la même logique, ne devrait-il pas intêtre tenu d'avoir une borne à moins que quelqu'un l'utilise ou sizeof(int)?
chi
@chi Pas du tout. La norme définit dans le cadre de la sémantique abstraite intqu’une valeur est comprise entre des bornes finies INT_MINet INT_MAX. Et si la valeur d'un intdépassement de ceux liés, un comportement indéfini se produit. D'autre part, la norme n'exige pas intentionnellement que tous les objets soient physiquement présents en mémoire à une adresse particulière, car cela permet des optimisations telles que le stockage de l'objet dans un registre, le stockage d'une partie seulement de l'objet, en le représentant différemment du standard. mise en page, ou l'omettre complètement si ce n'est pas nécessaire.
Feersum
4

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.

PyRulez
la source
À quoi ressemblerait une implémentation?
reinierpost le
@reinierpost Je suppose que cela représenterait des données utilisant un modèle comptable non standard comptable de PA. Il calculerait des opérations arithmétiques en utilisant un degré PA . Je pense qu'un tel modèle devrait fournir une implémentation C valide.
PyRulez le
Désolé, ça ne marche pas. sizeof(t)est elle-même une valeur de type size_t, donc un entier naturel compris entre 0 et SIZE_MAX.
Gilles, arrête de faire le mal
@Gilles SIZE_MAX serait alors un produit naturel non standard.
PyRulez
C'est une approche intéressante. Notez que vous devez également, par exemple, intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t pour ne pas être standard. En C ++, cela irait à l'encontre des garanties de progrès futurs ... pas sûr de C.
TLW
0

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.

Yves Daoust
la source
N'est-ce pas le point principal de la réponse acceptée? Je ne pense pas que cela ajoute quelque chose de nouveau aux réponses de cette question de 2016.
chi
@chi: non, la réponse acceptée ne mentionne pas l'échange vers la mémoire externe, ce qui pourrait être considéré comme une solution de contournement.
Yves Daoust
-1

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.]

le docteur
la source
7
Je ne pense pas que cela réponde à la question. La question anticipait déjà cette réponse et expliquait pourquoi elle n’était pas valide: "bien que le standard C permette à size_t d’être arbitrairement grand, il doit être fixé à une certaine longueur et quelle que soit sa longueur, il est toujours fini. ". Avez-vous une réponse à cet argument? Je ne pense pas que nous puissions compter la question comme une réponse sauf si la réponse explique pourquoi cet argument est incorrect (ou correct).
DW
5
A tout moment, une valeur de type size_test finie. Le problème est que vous ne pouvez pas établir de limite size_tvalide pour le calcul: pour toute limite, un programme risque de la saturer. Mais le langage C stipule qu’il existe une limite pour size_t: sur une implémentation donnée, elle ne peut croître qu’en sizeof(size_t)octets. Aussi, soyez gentil . Dire que les gens qui vous critiquent «ne peuvent pas penser seuls» est impoli.
Gilles, arrête de faire le mal
1
C'est la bonne réponse. Un tourneur ne nécessite pas de bande infinie, il nécessite une bande "arbitrairement longue". Autrement dit, vous pouvez supposer que la bande est aussi longue que nécessaire pour effectuer le calcul. Vous pouvez également supposer que votre ordinateur dispose de la mémoire nécessaire. Une bande infinie n'est absolument pas nécessaire, car tout calcul qui s'arrête en temps fini ne peut pas utiliser une quantité infinie de bande.
Jeffrey L Whitledge
Cette réponse montre que pour chaque MT, vous pouvez écrire une implémentation en C avec une longueur de pointeur suffisante pour la simuler. Cependant, il n'est pas possible d'écrire une implémentation en C pouvant simuler n'importe quelle MT. Donc, la spécification interdit que toute implémentation particulière soit T-complete. Il ne s'agit pas non plus de T-complete, car la longueur du pointeur est fixe.
1
Ceci est une autre réponse correcte qui est à peine visible en raison de l'incapacité de la plupart des individus de cette communauté. En attendant, la réponse acceptée est fausse et sa section de commentaires est protégée par les modérateurs qui suppriment les commentaires critiques. Au revoir, cs.stackexchange.
xamid
-1

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.

David Richerby
la source
3
Je dirais que, sauf si la définition C exige un tel stockage externe sans limite, cela ne peut pas être accepté comme une preuve de la complétude de Turing. (ISO 9899 n'exige pas, bien sûr, d'être écrit pour l'ingénierie du monde réel.) Ce qui m'inquiète, c'est que, si nous acceptons cela, nous pourrions, par un raisonnement similaire, affirmer que les DFA sont complets, car ils pourraient être utilisés. conduire une tête sur une bande (le stockage externe).
chi
@chi Je ne vois pas comment l'argument DFA suit. L'intérêt d'un DFA est qu'il ne dispose que d'un accès en lecture au stockage. Si vous lui permettez de "passer la tête sur une bande", n'est-ce pas une machine de Turing?
David Richerby
2
En effet, je pique un peu ici. La question est la suivante: pourquoi est-il correct d’ajouter une "bande" à C, de laisser C simuler un DFA et d’utiliser ce fait pour affirmer que C est complet, alors que nous ne pouvons pas faire la même chose avec les DFA? Si C n'a aucun moyen d'implémenter lui-même une mémoire illimitée, il ne devrait pas être considéré comme complet. (Je l'appellerais encore "moralement" Turing complet, au moins, car les limites sont si grandes qu'elles importent peu dans la plupart des cas) Je pense que pour régler définitivement la question, il faudrait une spécification formelle rigoureuse C (la norme ISO ne suffit pas)
chi
1
@chi C'est bon parce que C inclut des routines d'E / S sur fichier. Les DFA ne le font pas.
David Richerby
1
C ne spécifie pas complètement le rôle de ces routines - la plupart de leurs sémantiques sont définies par la mise en œuvre. L'implémentation AC n'est pas nécessaire pour stocker le contenu du fichier, par exemple, je pense que cela peut se comporter comme si chaque fichier était "/ dev / null", pour ainsi dire. Il n'est pas non plus nécessaire de stocker une quantité illimitée de données. Je dirais que votre argument est correct, lorsque vous considérez ce que font la grande majorité des implémentations C et que vous généralisez ce comportement à une machine idéale. Si nous nous en remettons strictement à la définition du mot C, mais en oubliant la pratique, je ne pense pas qu'elle soit valable
chi
-2

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_MAXO(2sjeze_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.

Nathan Davis
la source
6
Qu'est-ce qui printf("%zu\n",SIZE_MAX);imprimerait sur une telle implémentation?
Ruslan
1
@Ruslan, une telle implémentation est impossible, tout comme il est impossible d'implémenter une machine de Turing. Mais si une telle implémentation était possible, j'imagine qu'elle imprimerait une représentation décimale d'un nombre infiniment grand - probablement un flux infini de chiffres décimaux.
Nathan Davis
2
@NathanDavis Il est possible de mettre en place une machine de Turing. Le truc, c'est que vous n'avez pas besoin de créer une bande infinie - vous créez simplement la partie utilisée de la bande par incréments, selon vos besoins.
Gilles, arrête de faire le mal '28
2
@ Gilles: Dans cet univers fini dans lequel nous vivons, il est impossible de mettre en œuvre une machine de Turing.
gnasher729
1
@NathanDavis Mais si vous faites cela, alors vous avez changé sizeof(size_t)(ou CHAR_BITS). Vous ne pouvez pas reprendre à partir du nouvel état, vous devez recommencer, mais l'exécution du programme peut être différente maintenant que ces constantes sont différentes
Gilles 'SO - arrête de faire le mal'
-2

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).

Eugene
la source
1
"La différence de ces deux peut être NaN". Non, ça ne peut pas être. Il n'y a pas de NaN de type entier en C.
TLW
Selon le standard, sizeofdoit retourner un size_t. Vous devez donc choisir une valeur particulière.
Draconis
-4

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.)

xamid
la source
4
Je ne suis pas votre dernier paragraphe. Vous prétendez que l'ajout de restrictions augmente le pouvoir d'expression, mais ce n'est clairement pas vrai. Les restrictions ne peuvent que diminuer le pouvoir d'expression. Par exemple, si vous prenez C et ajoutez la restriction selon laquelle aucun programme ne peut accéder à plus de 640 Ko de stockage (de quelque type que ce soit), vous l'avez transformé en un automate fini fantaisie qui n'est clairement pas Turing-complete.
David Richerby
3
Si vous avez une quantité de stockage fixe, vous ne pouvez pas simuler quoi que ce soit qui nécessite plus de ressources que vous en avez. Votre mémoire ne peut contenir que très peu de configurations, ce qui signifie que vous ne pouvez faire que très peu de choses.
David Richerby
2
Je ne comprends pas pourquoi vous parlez de "machines physiquement existantes". Notez que la complétude de Turing est une propriété d'un modèle de calcul mathématique, et non de systèmes physiques. Je conviens qu’aucun système physique, en tant qu’objet fini, ne peut s’approcher de la puissance des machines de Turing, mais cela n’a aucune pertinence. Nous pouvons toujours prendre n'importe quel langage de programmation, examiner la définition mathématique de sa sémantique et vérifier si cet objet mathématique est complet de Turing. Le jeu de la vie de Conway est puissant, même s'il n'y a pas de mise en œuvre physique possible.
chi
2
@xamid Si vous avez des préoccupations concernant les règles de modération de ce site, allez à Computer Science Meta . Jusque-là, s'il vous plaît soyez gentil . L'abus verbal envers autrui ne sera pas toléré. (J'ai supprimé tous les commentaires qui ne concernent pas le sujet traité.)
Raphael
2
Vous dites que modifier la largeur d'un pointeur ne changerait pas le programme, mais les programmes peuvent lire la largeur d'un pointeur et faire ce qu'ils veulent avec cette valeur. Pareil pour CHAR_BITS.
Draconis