Écrivez un simulateur de machine de Turing .
Pour plus de simplicité, nous pouvons supposer que les états sont des nombres entiers, des symboles comme des caractères, un symbole vide est égal à un espace blanc
5-tuple sous forme d'état actuel, symbole d'entrée, état suivant, symbole de sortie, direction (gauche ou droite) la commande n'est pas obligatoire mais spécifiez si vous la permutez
La machine doit s'arrêter lorsqu'un état inconnu est atteint, aucune autre condition d'arrêt n'est autorisée.
La bande est infinie dans les deux sens et vous pouvez toujours lire un caractère vide.
Entrée: la bande initiale, un état initial et un programme. vous êtes libre de lire les données de n'importe où dans le format que vous aimez
Sortie: la bande après l'exécution du programme
Obligatoire: un exemple de programme qui s'exécute au-dessus de votre simulateur
C'est un code-colf donc le code le plus court l'emporte.
Je publierai une implémentation et quelques exemples de programmes dans les prochaines heures.
la source
Réponses:
GolfScript, 92 caractères
La machine Turing dans GolfScript est devenue beaucoup plus longue que prévu. Je joue toujours avec différentes représentations de la bande.
La première ligne de l'entrée est l'état d'origine, la deuxième ligne la bande initiale, suivie d'un tableau de transitions (avec l'état actuel de l'ordre, le symbole d'entrée, l'état suivant, la direction, le symbole de sortie).
Exemple (également disponible en ligne )
la source
GNU sed avec
-r-13311711193 caractèresOui, sed est complet. GNU sed et
-r(regexps étendus) ne servent qu'à enregistrer quelques caractères, ce n'est qu'un petit changement pour fonctionner avec POSIX sed.Le format d'entrée est
Les délimiteurs
@,#et le caractère de tête>ne peuvent pas être utilisés comme un symbole sur la bande. Les étiquettes d'état ne peuvent pas contenir@>ou#.Il exécutera tous les programmes en entrée, un par ligne
Exemples:
Marco est un n b n programme
Bonjour de Marco! programme
la source
Je suis donc un peu en retard, mais je pensais juste laisser ça ici ...
Machine de Turing Simuler une machine de Turing: 370 octets?
Ici, j'utilise la structure utilisée par Turing dans son article de 1936. J'utilise un symbole = un octet, y compris les m-configs et les opérations.
Voici un des exemples de Turing du papier ci-dessus pour ma machine:
Essayez-le en ligne! (Utilise Python 3 comme interprète) --Edit: Je viens de vérifier le TIO, et il ne semble pas vraiment fonctionner correctement ... Essayez-le sur votre machine locale et cela devrait (espérons-le) fonctionner. C'est le mien.
la source
APL (110)
(Ce n'est même pas si court ...)
Il lit deux lignes à partir du clavier: la première est le programme et la seconde est la bande initiale.
Le format est
et ils devraient tous être sur la même ligne. «Mouvement» est 0 pour se déplacer vers la droite et 1 pour se déplacer vers la gauche.
Exemple de programme (les sauts de ligne sont insérés pour plus de clarté, ils doivent tous être sur une seule ligne.)
Le programme ajoute deux nombres unaires ensemble, par exemple:
Exemple 2 (adapté du programme d'incrémentation binaire de l'entrée de Marco Martinelli):
la source
Python,
101189152142 142b et p sont les entrées, b est la bande initiale, p code les règles en tant que (représentation sous forme de chaîne) d'un dicton de (dans l'état, dans la bande) tuple vers (hors état, déplacement de la tête, hors bande) tuple . Si le déplacement est 0, le programme se termine, 1 est le déplacement vers la droite et -1 est le déplacement vers la gauche.
Cet exemple de programme teste si la dernière lettre de la chaîne (avant la bande vide) est «a», si c'est le cas, il écrit «Y» à la fin de la chaîne (premier espace vide).
Modifier 1:
Modification de la bande pour qu'elle soit représentée comme dictée, car cela semblait être le moyen le plus court d'écrire une structure de données extensible. L'avant-dernière ligne la transforme principalement en une forme lisible pour la sortie.
Modifier 2:
Merci à Strigoides pour de nombreuses améliorations.
Modifier 3:
Je l'avais fait inutilement pour que 0 comme sortie laisse la place telle qu'elle est. J'ai supprimé cela car nous pouvons toujours écrire la sortie de la même manière que l'entrée.
la source
r=0;s=0devenirr=s=0(et le point-virgule à la fin de cette ligne n'est pas nécessaire), vous pouvez supprimer la fonctionw, car elle n'est pas utilisée, les crochets peuvent être supprimés(s,m,t)=r[s,c], le bloctry/exceptpeut être raccourci en utilisant dict.get;c=a.get(i,' '), puisqu'ilmvaut 0 ou 1, vous pouvez l'utiliserif m-1:et vous pouvez raccourcir votremap()appel en le convertissant en une liste de compréhension.Postscript
(205)(156)(150)(135)C'est probablement de la triche, mais la table de transition contient du code pour effectuer les transitions. Et puisque la bande est représentée par un mappage d'entiers en entiers, j'ai représenté les états comme un mappage de noms vers des dictionnaires afin que la bande et le programme coexistent dans le même dictionnaire anonyme.
Économies supplémentaires en rendant tous les noms d'état exécutables, afin qu'ils se chargent automatiquement .
Non golfé avec le programme "Hello" intégré.
52 caractères supplémentaires achètent une boucle pour lire la bande depuis stdin.Courez avecgsnd -q tm.ps.Le format de tableau est donc
où
in-stateest un nom,in-tapeetout-tapesont des caractères (c'est-à-dire des entiers ou des expressions qui produisent des entiers),movementest-1pour gauche ou1pour droite, etout-stateest un nom exécutable . Lesin-tapetransitions multiples pour le même état doivent être combinées comme ci-dessus.la source
currentdict{search-for-min-and-max}forall juggle-params-for-for. :(0 1 0 not{(%stdin)(r)file read not{exit}if def}for. Je ne sais pas pourquoi j'ai pensé que je pourrais m'en tirer en omettant cela de la version golfée. : P0 notdevrait l'être16#7fffffff. Pardon. Ah! c'est pourquoi il a été commenté! Il est sorti directement du cahier, n'a pas été testé et j'ai coupé tous les commentaires sans regarder quand je l'ai joué au golf. Ne le dites pas au gars de Python! : PC (pas encore joué au golf)
Je suppose que je ne peux pas gagner avec ça, c'était quand même amusant de le faire fonctionner. Cela est encore plus vrai maintenant que ce vraiment fait le travail. :)
Sauf que c'est seulement infini dans une direction. Je suppose qu'il a également besoin d'une bande négative. Soupir....
Le négatif n'était pas si mal. Nous entrelacons les deux côtés comme des chances égales. La complication est maintenant qu'il doit afficher la bande dans un ordre séquentiel , car le fichier lui-même est maintenant brouillé. Je pense que c'est une modification légitime. Turing lui-même a simplifié de cette façon.
Et voici le test:
Le programme sort la bande dans un ordre séquentiel, mais le fichier représente les côtés négatifs et positifs entrelacés.
la source
0 'a' 0 'b' R; 0 'b' 0 'a' Ravec l'entrée aaa la sortie est bab au lieu de bbb. Et il y a des problèmes de déplacement à gauche.Groovy
234228154153149139124Formaté pour la lisibilité
t est la fonction qui définit la bande e est la fonction qui évalue le programme
Exemple 1 - Imprimez "Bonjour!" sur la bande :)
Exemple 2 - Laissez un T sur la bande si la chaîne initiale est sous la forme d'un n b n , arrêtez sinon.
Exemple 3 - Incrément d'un nombre binaire
dans les exemples 1 signifie déplacer vers la droite et -1 signifie déplacer vers la gauche
la source