Machines de Turing

GW-Basic, utilisé par PC-Basic

Programme avec Texte Seulement

PC-BASIC

L'histoire des ordinateurs ne pourrait être écrite sans un chapitre – ou plusieurs chapitres – sur le mathématicien Alan Turing.

Turing est né à Londres en 1912. Il a montré une faculté précoce en mathématiques, offrant finalement une preuve unique du théorème central limite, un concept statistique clé, dans sa thèse de premier cycle. Plus tard, après avoir obtenu un doctorat en mathématiques à Princeton, il est allé travailler pour le gouvernement britannique à Bletchley Park, aidant à décoder la machine allemande Enigma pendant la Seconde Guerre mondiale.

Mais la contribution la plus significative de Turing à l'informatique ne réside pas dans la cryptographie, mais dans ses machines de Turing.

Formulées pour la première fois dans son article révolutionnaire de 1936 "On Computable Numbers, with an Application to the Entschei-dungsproblem", les machines de Turing sont des machines à états finis, ce qui signifie qu'elles ont un nombre fini (c'est-à-dire dénombrable) d'états possibles, et ne peuvent être que dans un état à la fois.

Chaque machine contient également une très longue bande de papier divisée en carrés, ainsi qu'une tête de lecture/écriture qui peut lire des symboles ou écrire des symboles sur la bande. Les symboles, qui sont généralement 0, 1 ou aucun symbole, coupés en carrés sur la bande de papier, un symbole par carré, et sont entrés avant que la machine exécute un programme.

Les machines de Turing sont programmées à l'aide de jeux d'instructions, qui spécifient explicitement ce que la machine doit faire lorsque la tête de lecture/écriture rencontre les symboles : écrire un symbole différent sur le papier ? déplacer à gauche ou à droite, ou pas du tout? passer à un état différent ou arrêter la machine ?

Le jeu d'instructions, partant d'un état initial (ou de départ), rend compte de toutes les possibilités.

Examinons quelques exemples.

Considérez la table d'état suivante :

Ce premier programme s'exécutera indéfiniment, quelle que soit l'entrée.

Si la tête de lecture/écriture rencontre un carré vide sur la bande, rien ne se passe ; mais si un 0 ou un 1 est trouvé, le symbole est inversé (0 à 1, 1 à 0).

Après avoir traité l'entrée, cependant, la machine se réinitialise à l'état initial et recommence. La bande de papier est traitée par la tête de lecture/écriture (représentée par le symbole caré ou ^) comme suit :

Considérez cet exemple suivant, qui inverse le symbole d'entrée, se déplace vers la droite pour lire le symbole suivant et ne s'arrête pas tant qu'un espace vide n'est pas trouvé :

Programme 2 de la machine de Turing : un onduleur de bits

Ce programme n'a qu'un seul état, l'état initial. Par conséquent, la machine requise pour exécuter ce jeu d'instructions est appelée une machine de Turing à un état. Plus d'états permettent des opérations plus compliquées, telles que l'addition et la soustraction de nombres binaires.

Les machines de Turing ont également engendré leur propre ensemble de problèmes de programmation intéressants.

 Le plus célèbre est peut-être le problème du castor occupé : combien de 0 ou de 1 peut-on écrire sur une bande complètement vierge tout en s'assurant que le programme s'arrête ?

Sans la restriction d'arrêt, la réponse est l'infini :

Programme de la machine de Turing n° 3 : une chaîne de 1s pour toujours

Mais la machine de Turing doit s'arrêter pour résoudre le problème du castor occupé, ce qui signifie donc qu'une machine à un état ne peut avoir qu'un seul symbole écrit sur la bande :

Programme 4 de la machine de Turing : le castor occupé à 1 état

Voici le jeu d'instructions pour une machine à deux états :

Programme de la machine de Turing n° 5 : Le castor occupé à 2 états

Un programme de machine de Turing à trois états ressemble à ceci :

Programme de la machine de Turing n° 6 : Le castor occupé à 3 états

Bien qu'il prenne quatorze étapes, le programme écrira six 1 sur la bande avant de s'arrêter. Il s'avère que six est le nombre maximum de 1 qui peuvent être écrits à l'aide d'une machine à trois états - c'est-à-dire, que si vous voulez que la machine s'arrête.

Vous pouvez amadouer une machine à quatre états pour écrire treize 1, mais cela prendra 107 étapes avant de s'arrêter. À partir de là, à mesure que le nombre d'états augmente, le nombre d'étapes nécessaires avant de s'arrêter augmente de façon exponentielle.

Ce qui est particulièrement remarquable, c'est qu'Alan Turing a formulé ses machines de Turing des décennies avant la construction de tout ordinateur numérique programmable (binaire).

Vous trouverez ci-dessous le code pour simuler une machine de Turing à n états, capable d'exécuter tous les jeux d'instructions énumérés ci-dessus ainsi que tout ce que vous pouvez concevoir.

Les boucles FOR/NEXT, ainsi qu'un certain nombre de tableaux, créent les conditions nécessaires pour entrer dans le jeu d'instructions.

Les symboles définis comme entrée initiale sont définis au milieu de la bande (voir lignes 220 à 260).

Bien qu'en théorie les machines de Turing contiennent une bande de papier d'une longueur infinie - ou du moins aussi longue qu'il en faut pour exécuter un programme - dans GW-BASIC, la longueur du tableau est assez restreinte.

Si la tête de lecture/écriture de la machine de Turing, affichée à l'écran à l'aide du symbole caret (^), s'aventure trop à gauche ou à droite, TURING.BAS s'arrêtera de lui-même malheureusement.

Outre le fait que la bande de papier ne peut pas vraiment être d'une longueur infinie - c'est une restriction que vous rencontreriez dans n'importe quel langage de programmation - TURING.BAS pourrait être amélioré dans deux domaines clés : la saisie du jeu d'instructions et la visualisation de la machine de Turing au travail.

Le jeu d'instructions est très lourd à saisir ; une erreur, et toutes vos frappes sont perdues. Le codage d'une fonction d'annulation, et peut-être même d'une fonction de sauvegarde, supprimerait une grande partie de l'ennui du processus.

Bien qu'une partie de la bande à gauche et à droite de la tête de lecture/écriture soit affichée à l'écran, davantage de fioritures graphiques, voire peut-être une animation, augmenteraient l'excitation de l'exécution du jeu d'instructions.

5 REM TURING.BAS
10 KEY OFF:CLS
20 PRINT "------MACHINE DE TURING ------"
25 PRINT:PRINT "TAPER EN MAJUSCULES!!"
30 PRINT:INPUT "Combien d'états sont nécessaires, y compris l'état initial";STATE
40 PRINT "Il y a trois symboles qui peuvent être lus dans chaque état: B (BLANK), 0, and 1."
50 PRINT "Une commande d'écriture, une instruction de déplacement et un état suivant (ou arrêt) doivent"
60 PRINT "être spécifié pour chaque état."
70 FOR LOOP=1 TO STATE
75 PRINT
80 PRINT "TABLEAU D'ETAT pour STATE";LOOP
85 FOR LOOP2=1 TO 3
86 IF LOOP2=1 THEN PRINT "POUR LE SYMBOLE LIRE = BLANK"
87 IF LOOP2=2 THEN PRINT "POUR LE SYMBOLE LIRE = 0"
88 IF LOOP2=3 THEN PRINT "POUR LE SYMBOLE LIRE = 1"
90 INPUT "Instruction d'écriture (0 or 1 or B)";WRIT$
100 INPUT "Instruction de déplacement (L or R or <ENTER> pour rien)";MOVE$
110 INPUT "État suivant (halt = 0)";NXT
115 'Encoder les instructions d'écriture, de déplacement et d'état suivant
120 WRIT$(LOOP,LOOP2)=WRIT$
122 MOVE$(LOOP,LOOP2)=MOVE$
124 NXT(LOOP,LOOP2)=NXT
130 NEXT LOOP2
140 NEXT LOOP
200 CLS
201 DIM INPU$(200) 'Configuration du tableau pour bande vierge
202 FOR TAPE=1 TO 200
203 INPU$(TAPE)="B"
204 NEXT TAPE
210 INPUT "Combien de caractères à saisir";CH
215 PRINT "Saisissez soit un 0, 1, or B"
220 FOR LOOP3=100 TO (CH+100-1) 'Configure les caractères saisis au milieu de la bande
230 PRINT "Quel est le caractère #";LOOP3-99;
240 INPUT CH$
250 INPU$(LOOP3)=CH$
260 NEXT LOOP3
300 CLS
305 STP=100 'Défini sur la première entrée (les entrées de rappel commencent à l'élément 100
306 'pour donner de l'espace à la tête de lecture/écriture pour se déplacer vers la gauche/droite
310 STATE=1 'Commence par l'état initial
320 'Continuer jusqu'à HALT; d'abord, montrez la bande:
321 FOR DISP=(STP-10) TO (STP+10)
322 PRINT INPU$(DISP);
323 NEXT DISP
324 PRINT
325 PRINT TAB(11) "^" 'Indique l'emplacement de la tête de lecture/écriture
330 PRINT "État actuel = ";STATE
340 PRINT "Lecture de ce qui suit sur la tête de lecture/écriture:";INPU$(STP)
345 PRINT:INPUT "Appuyez <ENTER> pour Continuer...";G$
358 'Déterminez s'il y a un 0, 1, ou BLANK comme entrée
360 IF INPU$(STP)="B" THEN LOOP2=1:GOTO 500
370 IF INPU$(STP)="0" THEN LOOP2=2:GOTO 500
380 IF INPU$(STP)="1" THEN LOOP2=3:GOTO 500
400 GOTO 320
500 'Sous-programme pour les trois entrées possibles
515 CLS
530 INPU$(STP)=WRIT$(STATE,LOOP2)
531 FOR DISP=(STP-10) TO (STP+10)
532 PRINT INPU$(DISP);
533 NEXT DISP
534 PRINT
535 PRINT TAB(11) "^"
536 PRINT "État actuel = ";STATE
537 PRINT "L'instruction d'écriture était:";WRIT$(STATE,LOOP2)
540 PRINT "L'instruction initiale est:";MOVE$(STATE,LOOP2)
550 IF MOVE$(STATE,LOOP2)="L" THEN STP=STP-1
560 IF MOVE$(STATE,LOOP2)="R" THEN STP=STP+1
570 PRINT "Le prochain état où nous irons est:";NXT (STATE,LOOP2)
575 S=S+1:PRINT "Le nombre de pas que la machine a effectués jusqu'à présent:";S
580 STATE =NXT(STATE,LOOP2)
590 IF STATE=0 THEN PRINT "Halt":END 'Mis à halt
595 PRINT:LINE INPUT "Appuyez <ENTER> POUR CONTINUER, OU 'H' ET <ENTER> POUR ARRÊTER LA MACHINE"'G$
596 IF G$="H" THEN END
598 CLS
600 GOTO 320