Un petit langage de type C que les machines de turing peuvent simuler

Je recherche un petit langage qui aide à «convaincre» les étudiants que les machines de turing sont un modèle informatique suffisamment général. Autrement dit, un langage qui ressemble aux langues auxquelles ils sont habitués, mais qui est également facile à simuler sur une machine de turing.

Papadimitriou utilise des machines RAM pour ce travail, mais je crains que comparer quelque chose d'étrange (comme une machine de turing) à une autre chose étrange (essentiellement, un langage d'assemblage) ne soit pas trop convaincant pour de nombreux étudiants.

Toutes les suggestions seraient les bienvenues (surtout si elles venaient avec une documentation recommandée)

• Si vos élèves ont fait une programmation fonctionnelle, la meilleure approche que je connaisse est de commencer par le calcul lambda non typé, puis d'utiliser le théorème d'abstraction des crochets pour le traduire en combinateurs SKI. Ensuite, vous pouvez utiliser les théorèmes et u t m pour montrer que les machines de Turing forment une algèbre combinatoire partielle , et ainsi interpréter les combinateurs SKI.$smn$$utm$

  Je doute que cette approche soit la plus simple possible, mais j'aime la façon dont elle repose sur certains des théorèmes les plus fondamentaux de la calculabilité (que vous souhaiterez peut-être couvrir pour d'autres raisons).

  Il semble qu'Andrej Bauer ait répondu à une question similaire sur Mathoverflow il y a quelques mois.

• Si vous utilisez un langage de type C, votre chemin sera beaucoup plus difficile, car ils ont une sémantique plutôt compliquée - vous devrez

  1. Montrer que les machines Turing peuvent simuler une pile et un tas en même temps, et
  2. Montrez comment les variables peuvent être implémentées avec une pile, et
  3. Montrez que les appels de procédure peuvent être implémentés avec une pile.

  C'est une grande partie du contenu d'une classe de compilateurs, honnêtement.

Mon professeur de théorie de la comp au premier cycle a commencé par prouver qu'une machine de Turing à bande unique peut implémenter une machine de Turing à bandes multiples. Cela gère la déclaration de variables: si un programme a six déclarations de variables, alors il peut être facilement implémenté sur une machine de Turing à sept bandes (une bande pour chaque variable et une bande de "registre" pour aider à effectuer des tâches comme l'arithmétique et la vérification d'égalité entre bandes). Il a ensuite montré comment implémenter les boucles FOR et WHILE de base, et à ce moment-là, nous avions un langage de type C de Turing complet. Je l'ai trouvé satisfaisant de toute façon.

Je réfléchis en ce moment à la façon de me convaincre que les machines de Turing sont un modèle général de calcul. Je suis d'accord que le traitement standard de la thèse de Church-Turing dans certains manuels standard, par exemple Sipser, n'est pas très complet. Voici un aperçu de la façon dont je pourrais passer des machines Turing à un langage de programmation plus reconnaissable.

Considérons un langage de programmation structuré en blocs avec ifet des whileinstructions, avec des fonctions et des sous-routines définies non récursives , avec des variables booléennes aléatoires nommées et des expressions booléennes générales, et avec un tableau booléen non borné unique tape[n]avec un pointeur de tableau entier nqui peut être incrémenté ou décrémenté, n++ou n--. Le pointeur nest initialement nul et le tableau tapeest initialement entièrement nul. Ainsi, ce langage informatique peut être de type C ou de type Python, mais il est très limité dans ses types de données. En fait, ils sont si limités que nous n'avons même pas le moyen d'utiliser le pointeur ndans une expression booléenne. En admettant quetapen'est infini que vers la droite, nous pouvons déclarer un dépassement de pointeur "erreur système" s'il nest jamais négatif. De plus, notre langage a une exitinstruction avec un argument, pour sortir une réponse booléenne.

Ensuite, le premier point est que ce langage de programmation est un bon langage de spécification pour une machine de Turing. Vous pouvez facilement voir que, à l'exception du tableau de bandes, le code n'a qu'un nombre fini d'états possibles: l'état de toutes ses variables déclarées, la ligne d'exécution en cours et sa pile de sous-programmes. Ce dernier n'a qu'un état fini car les fonctions récursives ne sont pas autorisées. Vous pourriez imaginer un "compilateur" qui crée une machine de Turing "réelle" à partir d'un code de ce type, mais les détails de cela ne sont pas importants. Le fait est que nous avons un langage de programmation avec une syntaxe assez bonne, mais des types de données très primitifs.

Le reste de la construction consiste à le convertir en un langage de programmation plus vivable avec une liste finie de fonctions de bibliothèque et d'étapes de précompilation. On peut procéder comme suit:

1. Avec un précompilateur, nous pouvons étendre le type de données booléen à un alphabet de symboles plus grand mais fini tel que ASCII. Nous pouvons supposer que tapeprend des valeurs dans cet alphabet plus grand. Nous pouvons laisser un marqueur au début de la bande pour éviter le débordement du pointeur, et un marqueur mobile à la fin de la bande pour empêcher le TM de patiner à l'infini sur la bande accidentellement. Nous pouvons implémenter des opérations binaires arbitraires entre les symboles et des conversions en booléens pour ifet whileinstructions. (En fait, ifpeut également être implémenté avec while, s'il n'était pas disponible.)

2. $k$$k$$i$$i$$k$

3. Nous désignons une bande comme "mémoire" à valeur de symbole et les autres comme "registres" ou "variables" à valeur entière non signés. Nous stockons les entiers en binaire petit-boutien avec des marqueurs de terminaison. Nous implémentons d'abord la copie d'un registre et la décrémentation binaire d'un registre. En combinant cela avec l'incrémentation et la décrémentation du pointeur de mémoire, nous pouvons implémenter la recherche d'accès aléatoire de la mémoire de symboles. Nous pouvons également écrire des fonctions pour calculer l'addition binaire et la multiplication d'entiers. Il n'est pas difficile d'écrire une fonction d'addition binaire avec des opérations au niveau du bit, et une fonction à multiplier par 2 avec décalage à gauche. (Ou vraiment décalage à droite, car il est peu endian.) Avec ces primitives, nous pouvons écrire une fonction pour multiplier deux registres en utilisant l'algorithme de multiplication longue.

4. Nous pouvons réorganiser la bande mémoire d'un tableau de symboles unidimensionnel symbol[n]à un tableau de symboles bidimensionnels en symbol[x,y]utilisant la formule n = (x+y)*(x+y) + y. Nous pouvons maintenant utiliser chaque ligne de la mémoire pour exprimer un entier non signé en binaire avec un symbole de terminaison, pour obtenir une mémoire unidimensionnelle à accès aléatoire à valeur entière memory[x]. Nous pouvons implémenter la lecture de la mémoire dans un registre entier et l'écriture d'un registre dans la mémoire. De nombreuses fonctionnalités peuvent désormais être implémentées avec des fonctions: arithmétique à virgule flottante et signée, chaînes de symboles, etc.

5. Une seule installation de base supplémentaire nécessite strictement un précompilateur, à savoir des fonctions récursives. Cela peut être fait avec une technique largement utilisée pour implémenter des langages interprétés. Nous attribuons à chaque fonction récursive de haut niveau une chaîne de nom et nous organisons le code de bas niveau en une grande whileboucle qui conserve une pile d'appels avec les paramètres habituels: le point d'appel, la fonction appelée et une liste d'arguments.

À ce stade, la construction a suffisamment de fonctionnalités d'un langage de programmation de haut niveau pour que la fonctionnalité supplémentaire soit davantage le thème des langages de programmation et des compilateurs plutôt que la théorie CS. Il est également déjà facile d'écrire un simulateur de machine de Turing dans ce langage développé. Il n'est pas exactement facile, mais certainement standard, d'écrire un auto-compilateur pour la langue. Bien sûr, vous avez besoin d'un compilateur externe pour créer la MT externe à partir d'un code dans ce langage de type C ou Python, mais cela peut être fait dans n'importe quel langage informatique.

Notez que cette mise en œuvre esquissée prend en charge non seulement la thèse Church-Turing des logiciens pour la classe de fonctions récursives, mais aussi la thèse Church-Turing étendue (c'est-à-dire polynomiale), en ce qui concerne le calcul déterministe. En d'autres termes, il a une surcharge polynomiale. En fait, si on nous donne une machine RAM ou (mon préféré) un tree-tape TM, cela peut être réduit à une surcharge polylogarithmique pour le calcul en série avec la mémoire RAM.

Le compilateur LLVM permet de «brancher» assez simplement une nouvelle architecture. Ils appellent cela l' écriture un nouveau back-end , et donnent des instructions détaillées et des exemples sur la façon de le faire. Je soupçonne que vous devrez sauter à travers quelques cerceaux en ce qui concerne la mémoire à accès aléatoire, si vous ne souhaitez pas cibler une machine RAM Turing, mais c'est certainement faisable, comme j'ai vu un certain nombre de projets qui provoquent la génération de LLVM VHDL ou d'autres langages machine très différents.

Cela aurait pour effet intéressant d'avoir un compilateur d'optimisation de pointe (à bien des égards LLVM est plus avancé que GCC) générant du code pour une machine de Turing.

Je ne suis pas dans la théorie cs mais j'ai quelque chose qui pourrait être utile. J'ai pris une autre approche. J'ai conçu un processeur simple directement programmable avec un petit sous-ensemble de C. Il n'y a AUCUN code d'assemblage, seulement du code de type C. Vous pouvez utiliser le même outil que j'ai utilisé et modifier ce processeur pour concevoir votre simulateur de machine Turing. Il m'a fallu 4 jours pour concevoir, simuler et tester ce processeur, enfin quelques instructions! Les outils que j'ai utilisés m'ont même permis de générer du vrai code synthétisable VHDL. C'est un véritable processeur qui fonctionne.

Voici à quoi ressemble un programme:

Voici une image du processeur utilisant ces outils:

Les outils "Novakod Studio" utilisent un langage de description matérielle de langage de haut niveau. À titre d'exemple, voici le code du compteur de programme: Assez parlé, si quelqu'un est intéressé, voici les informations publiques pour me contacter: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Luc

Que diriez-vous de prendre l'idée représentée par l'utilisateur GMB ici (une machine de Turing avec une bande peut simuler une machine de Turing avec N bandes en entrelaçant les N bandes sur une seule bande et en lisant l'une de ces bandes en sautant N emplacements à la fois, un Turing machine à N bandes peut implémenter ...) et écrire un programme machine Turing qui implémente une machine RAM simpliste. La machine RAM peut être en fait un processeur simpliste et réel avec un backend LLVM ou GCC disponible. Ensuite, le GCC / LLVM peut être utilisé pour la compilation croisée d'un programme C pour cette CPU et le programme de la machine Turing qui simule la machine RAM, exécute la simulation de la machine RAM en demandant à la machine RAM simulée d'exécuter la sortie GCC / LLVM. L'implémentation de la machine Turing peut être un code C très simple qui s'adapte à un petit fichier C.

En ce qui concerne la machine RAM, il existe alors un projet de démonstration, où un processeur 32 bits est simulé par un microcontrôleur 8 bits et le processeur 32 bits simulé démarre Linux. Lent comme l'enfer, mais selon l'auteur , Dmitry Grinberg, cela a fonctionné. Peut-être que le CPU Zylin (zylin utilisateur GitHub) pourrait être un choix viable pour la machine RAM simulable. Un autre candidat pour la machine RAМ pourrait être le ProjectOberon dot com de Niklaus Wirth .

(Le "point" et le "com" dans mon texte sont dus au fait que je viens, 2015_10_21, d'enregistrer mon compte sur cstheory.stackexchange et l'application web n'autorise pas plus de 2 liens pour les utilisateurs novices, malgré le fait qu'ils peuvent voir automatiquement à partir de mes autres comptes stackexchange que je suis peut-être stupide, mais je ne suis pas un troll.)