Puissance de calcul maximale d'une implémentation C

Si nous nous en remettons au livre (ou à toute autre version de la spécification du langage si vous préférez), quelle puissance de calcul une implémentation C peut-elle avoir?

Notez que «implémentation C» a une signification technique: il s'agit d'une instanciation particulière de la spécification du langage de programmation C où le comportement défini par l'implémentation est documenté. L'implémentation AC ne doit pas pouvoir fonctionner sur un ordinateur réel. Il doit implémenter le langage entier, y compris chaque objet ayant une représentation de chaîne de bits et les types ayant une taille définie par l'implémentation.

Aux fins de cette question, il n'y a pas de stockage externe. La seule entrée / sortie que vous pouvez effectuer est getchar(pour lire l'entrée de programme) et putchar(pour écrire la sortie de programme). De même, tout programme qui invoque un comportement non défini n'est pas valide: un programme valide doit avoir son comportement défini par la spécification C plus la description de l'implémentation des comportements définis par l'implémentation répertoriés dans l'annexe J (pour C99). Notez que l'appel de fonctions de bibliothèque non mentionnées dans la norme est un comportement non défini.

Ma première réaction a été qu'une implémentation C n'est rien de plus qu'un automate fini, car elle a une limite sur la quantité de mémoire adressable (vous ne pouvez pas adresser plus de sizeof(char*) * CHAR_BITbits de stockage, car les adresses de mémoire distinctes doivent avoir des modèles de bits distincts lorsqu'elles sont stockées dans un pointeur d'octets).

Cependant, je pense qu'une mise en œuvre peut faire plus que cela. Autant que je sache, la norme n'impose aucune limite à la profondeur de récursivité. Vous pouvez donc effectuer autant d'appels de fonction récursifs que vous le souhaitez, mais tous, sauf un nombre fini d'appels, doivent utiliser des registerarguments non adressables ( ). Ainsi, une implémentation C qui permet une récursion arbitraire et n'a pas de limite sur le nombre d' registerobjets peut coder des automates déterministes de refoulement.

Est-ce correct? Pouvez-vous trouver une implémentation C plus puissante? Existe-t-il une implémentation C de Turing complète?

unsigned charunsigned char*sizeof(unsigned char*)sizeof(unsigned char *)unsigned char$UCHAR\_MAX ^{sizeof(unsigned\ char*)}$$10^{10^{10}}$

Un programme pourrait stocker une quantité illimitée d'informations sur la pile si rien de ce qui est alloué sur la pile n'a jamais pris son adresse ; on pourrait donc avoir un programme C capable de faire certaines choses qui ne pourraient être faites par aucun automate fini de n'importe quelle taille. Ainsi, même si (ou peut-être parce que) l'accès aux variables de pile est beaucoup plus limité que l'accès aux variables allouées dynamiquement, il transforme C d'un automate fini en automate déroulant.

$UCHAR\_MAX ^{sizeof(unsigned\ char*)}$séquences possibles de valeurs de caractères, tout programme qui a créé un certain nombre de pointeurs vers des objets distincts en plus de cela ne pourrait pas se conformer à la norme C si le code examinait jamais la séquence de caractères associée à ces pointeurs . Il serait cependant possible dans certains cas pour un compilateur de déterminer qu'aucun code n'allait jamais examiner la séquence de caractères associée à un pointeur. Si chaque "char" était capable de contenir n'importe quel entier fini, et que la mémoire de la machine était une séquence infinie d'innombrables [étant donné une machine de Turing à bande illimitée, on pourrait émuler une telle machine bien qu'elle soit vraiment lente], alors il serait en effet possible de faire de C un langage complet de Turing.

Avec la bibliothèque de threads C11 (en option), il est possible de réaliser une implémentation complète de Turing avec une profondeur de récursivité illimitée.

La création d'un nouveau thread produit une seconde pile; deux piles suffisent pour que Turing soit complet. Une pile représente ce qui est à gauche de la tête, l'autre pile ce qui est à droite.

Je pense que c'est Turing complet : nous pouvons écrire un programme qui simule un UTM en utilisant cette astuce (j'ai rapidement écrit le code à la main donc il y a probablement des erreurs de syntaxe ... mais j'espère qu'il n'y a pas d'erreurs (majeures) dans la logique :-)

• définir une structure qui peut être utilisée comme une double liste chaînée pour la représentation sur bande

    typdef struct {
      cell_t * pred; // cellule à gauche
      cell_t * succ; // cellule à droite
      int val; // valeur de cellule
    } cell_t 

Le headsera un pointeur vers une cell_tstructure

• définir une structure qui peut être utilisée pour stocker l'état actuel et un indicateur

    typedef struct {
      état int;
      drapeau int;
    } info_t 

• définissez ensuite une fonction de boucle unique qui simule un TM universel lorsque la tête se trouve entre les limites de la liste à double lien; lorsque la tête atteint une limite, placez le drapeau de la structure info_t (HIT_LEFT, HIT_RIGHT) et retournez:

void simulate_UTM (cell_t * head, info_t * info) {
  tandis que (vrai) {
    head-> val = UTM_nextsymbol [info-> state, head-> val]; // écrit le symbole
    info-> state = UTM_nextstate [info-> state, head-> val]; // état suivant
    if (info-> state == HALT_STATE) {// affiche if accepte et quitte le programme
       putchar ((info-> state == ACCEPT_STATE)? '1': '0');
       sortie (0);
    }
    int move = UTM_nextmove [info-> état, tête-> val];
    if (move == MOVE_LEFT) {
      head = head-> pred; // se déplacer à gauche
      if (head == NULL) {info-> flag = HIT_LEFT; revenir; }
    } autre {
      tête = tête-> succ; // déplacer vers la droite
      if (head == NULL) {info-> flag = HIT_RIGHT; revenir; }
    }
  } // toujours dans la limite ... continue
}

• définissez ensuite une fonction récursive qui appelle d'abord la routine UTM de simulation, puis s'appelle récursivement quand la bande doit être étendue; lorsque la bande doit être étendue en haut (HIT_RIGHT) aucun problème, quand elle doit être décalée en bas (HIT_LEFT) il suffit de remonter les valeurs des cellules en utilisant la liste à double lien:

void stacker (cell_t * top, cell_t * bottom, cell_t * head, info_t * info) {
  simulate_UTM (head, info);
  cell_t newcell; // la nouvelle cellule
  newcell.pred = top; // met à jour la liste double liée avec la nouvelle cellule
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  commutateur (info-> hit) {
    cas HIT_RIGHT:
      empileur (& newcell, bottom, newcell, info);
      Pause;
    cas HIT_BOTTOM:
      cell_t * tmp = newcell;
      while (tmp-> pred! = NULL) {// décaler vers le haut les valeurs
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      stacker (& newcell, bottom, bottom, info);
      Pause;
  }
}

• la bande initiale peut être remplie avec une simple fonction récursive qui construit la double liste chaînée, puis appelle la stackerfonction lorsqu'elle lit le dernier symbole de la bande d'entrée (en utilisant readchar)

void init_tape (cell_t * top, cell_t * bottom, info_t * info) {
  cell_t newcell;
  int c = readchar ();
  if (c == END_OF_INPUT) stacker (& top, bottom, bottom, info); // plus de symboles, commence
  newcell.pred = top;
  if (top! = NULL) top.succ = & newcell; else bottom = & newcell;
  init_tape (& newcell, bottom, info);
}

EDIT: après y avoir réfléchi un peu, il y a un problème avec les pointeurs ...

si chaque appel de la fonction récursive stackerpeut conserver un pointeur valide vers une variable définie localement dans l'appelant, alors tout va bien ; sinon mon algorithme ne peut pas maintenir une liste valide à double lien sur la récursion illimitée (et dans ce cas, je ne vois pas un moyen d'utiliser la récursivité pour simuler un stockage à accès aléatoire illimité).

Tant que vous avez une taille de pile d'appels illimitée, vous pouvez encoder votre bande sur la pile d'appels et y accéder de manière aléatoire en rembobinant le pointeur de pile sans revenir des appels de fonction.

EDIT : Si vous ne pouvez utiliser que le bélier, qui est fini, cette construction ne fonctionne plus, alors voyez ci-dessous.

Cependant, il est très discutable pourquoi votre pile peut être infinie, mais le bélier intrinsèque ne l'est pas. Donc, en fait, je dirais que vous ne pouvez même pas reconnaître tous les langages réguliers, car le nombre d'états est limité (si vous ne comptez pas l'astuce de rembobinage pour exploiter la pile infinie).

Je suppose même que le nombre de langues que vous pouvez reconnaître est fini (même si les langues elles-mêmes peuvent être infinies, par exemple a*, ça va, mais b^kne fonctionne que pour un nombre fini de ks).

EDIT : Ce n'est pas vrai, car vous pouvez coder l'état actuel dans des fonctions supplémentaires, de sorte que vous pouvez vraiment reconnaître TOUTES les langues régulières.

Vous pouvez très probablement obtenir toutes les langues de type 2 pour la même raison, mais je ne sais pas si vous pouvez réussir à mettre les deux, l'état et la constante de pile sur la pile d'appels. Mais d'une manière générale, vous pouvez effectivement oublier le bélier, car vous pouvez toujours mettre à l'échelle la taille de l'automate afin que votre alphabet dépasse la capacité du bélier. Donc, si vous pouviez simuler une MT avec seulement une pile, Type-2 serait égal à Type-0, n'est-ce pas?

J'y ai pensé une fois et j'ai décidé d'essayer d'implémenter un langage non contextuel en utilisant la sémantique attendue; l'élément clé de la mise en œuvre est la fonction suivante:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

$\{a^n b^n c^n\}$

Au moins, je pense que cela fonctionne. Il se peut cependant que je commette une erreur fondamentale.

Une version fixe:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

Dans le sens de la réponse de @ supercat:

Les affirmations d'incomplétude de C semblent être centrées sur le fait que des objets distincts devraient avoir des adresses distinctes, et l'ensemble des adresses est supposé être fini. Comme l'écrit @supercat

Comme indiqué dans la question, la norme C requiert qu'il existe une valeur UCHAR_MAXtelle que chaque variable de type char non signé contiendra toujours une valeur comprise entre 0 et UCHAR_MAX, inclus. Il requiert en outre que chaque objet alloué dynamiquement soit représenté par une séquence d'octets identifiable via un pointeur de type unsigned char *, et qu'il y ait une constante sizeof(unsigned char*)telle que chaque pointeur de ce type soit identifiable par une séquence de sizeof(unsigned char *)valeurs de type unsigned carboniser.

unsigned char*$\mathbb{N}$$\{0, 1\}$sizeof(unsigned char*)$\{0, 1\}^{\operatorname{sizeof}(\mathit{unsigned\ char*})}$$\mathbb{N}$sizeof(unsigned char*)$\mathbb{N}$$\omega$

À ce stade, il faut vérifier que la norme C permettrait effectivement cela.

sizeof$\in \mathbb Z$