Équivalents des machines de Turing - Turing machine equivalents

Une machine de Turing est un dispositif informatique hypothétique, conçu pour la première fois par Alan Turing en 1936. Les machines de Turing manipulent des symboles sur une bande de ruban potentiellement infinie selon une table finie de règles, et elles fournissent les fondements théoriques de la notion d'algorithme informatique.

Bien qu'aucun des modèles suivants ne se soit avéré avoir plus de puissance que le modèle de machine de Turing à une seule bande, infini à sens unique et multi-symboles, leurs auteurs les ont définis et utilisés pour étudier des questions et résoudre des problèmes plus facilement qu'ils n'auraient pu l'avoir. s'ils étaient restés avec le modèle d' une machine de Turing .

Machines équivalentes au modèle de machine de Turing

Équivalence de Turing

De nombreuses machines dont on pourrait penser qu'elles ont plus de capacités de calcul qu'une simple machine de Turing universelle peuvent s'avérer n'avoir plus de puissance. Ils peuvent calculer plus vite, peut-être, ou utiliser moins de mémoire, ou leur jeu d'instructions peut être plus petit, mais ils ne peuvent pas calculer plus puissamment (c'est-à-dire plus de fonctions mathématiques). (La thèse Church-Turing émet l'hypothèse que cela est vrai : que tout ce qui peut être "calculé" peut être calculé par une machine de Turing.)

Les modèles de machines séquentielles

Tous les éléments suivants sont appelés « modèles de machines séquentielles » pour les distinguer des « modèles de machines parallèles ».

Machines de Turing à bande

Turing est un modèle de machine

La machine a de Turing (comme il l'appelait) était à gauche, à droite-infinie. Il a fourni des symboles əə pour marquer l'extrémité gauche. Un nombre fini de symboles de bande était autorisé. Les instructions (s'il s'agit d'une machine universelle) et les "entrées" et "sorties" n'étaient écrites que sur les "carrés F", et les marqueurs devaient apparaître sur les "carrés E". Essentiellement, il a divisé sa machine en deux bandes qui se déplaçaient toujours ensemble. Les instructions apparaissaient sous une forme tabulaire appelée "5 tuples" et n'étaient pas exécutées de manière séquentielle.

Machines à bande unique avec symboles restreints et/ou instructions restreintes

Les modèles suivants sont des machines de Turing à bande unique mais restreintes avec (i) des symboles de bande restreints { marque, blanc }, et/ou (ii) des instructions séquentielles de type informatique, et/ou (iii) des actions de machine entièrement atomisées.

Modèle de calcul "Formulation 1" de Post

Emil Post dans une description indépendante d'un processus de calcul, a réduit les symboles autorisés à l'ensemble binaire équivalent de marques sur la bande { "mark", "blank"=not_mark }. Il a changé la notion de "ruban" d'une voie infinie à droite à un ensemble infini de pièces chacune avec une feuille de papier dans les deux sens. Il a atomisé les 5 tuples de Turing en 4 tuples, des instructions de mouvement séparées des instructions d'impression/effacement. Bien que son modèle de 1936 soit ambigu à ce sujet, le modèle de Post de 1947 ne nécessitait pas l'exécution d'instructions séquentielles.

Son modèle extrêmement simple peut imiter une machine de Turing, et bien que son 1936 Formulation 1 ne pas utiliser le mot « programme » ou « machine », il est effectivement une formulation d'un ordinateur programmable très primitive et associée langage de programmation , les boîtes servant une mémoire de chaînes de bits illimitée, et l'ensemble d'instructions constituant un programme.

Machines de Wang

Dans un article influent, Hao Wang a réduit la « formulation 1 » de Post à des machines qui utilisent toujours une bande binaire infinie bidirectionnelle, mais dont les instructions sont plus simples – étant les composants « atomiques » des instructions de Post – et sont par défaut exécutées séquentiellement (comme un "programme informatique"). Son objectif principal déclaré était d'offrir, comme alternative à la théorie de Turing, celle qui « est plus économique dans les opérations de base ». Ses résultats ont été des "formulations de programmes" d'une variété de ces machines, y compris la machine Wang W à 5 instructions avec le jeu d'instructions

{ MAJ-GAUCHE, MAJ-DROITE, MARQUE-CARRE, EFFACER-CARRE, SAUT-SI-CARRE-MARQUE-à xxx }

et sa machine Wang B à 4 instructions la plus sévèrement réduite ("B" pour "basique") avec le jeu d'instructions

{ SHIFT-GAUCHE, SHIFT-RIGHT, MARK-SQUARE, JUMP-SI-SQUARE-MARKED-to xxx }

qui n'a même pas d'instruction ERASE-SQUARE.

De nombreux auteurs ont introduit plus tard des variantes des machines discutées par Wang :

Minsky a fait évoluer la notion de Wang avec sa version du modèle de "contre-machine" (à plusieurs bandes) qui permettait le mouvement SHIFT-LEFT et SHIFT-RIGHT des têtes séparées mais aucune impression du tout. Dans ce cas, les bandes seraient à extrémité gauche, chaque extrémité étant marquée d'une seule "marque" pour indiquer la fin. Il a pu réduire cela à une seule bande, mais au détriment de l'introduction d'un mouvement carré multi-bande équivalent à la multiplication et à la division plutôt que le beaucoup plus simple { SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT }.

Davis, ajoutant une instruction HALT explicite à l'une des machines discutées par Wang, a utilisé un modèle avec le jeu d'instructions

{ SHIFT-GAUCHE, SHIFT-RIGHT, ERASE, MARK, JUMP-SI-CARRE-MARKED-to xxx, JUMP-to xxx, HALT }

et a également considéré des versions avec des alphabets de bande de taille supérieure à 2.

Le langage machine théorique de Böhm P"

Conformément au projet de Wang de rechercher une théorie équivalente à Turing "économique dans les opérations de base", et souhaitant éviter les sauts inconditionnels, un langage théorique notable est le langage à 4 instructions P" introduit par Corrado Böhm en 1964 - le premier "GOTO -moins " impératif " langage de programmation structuré " à prouver Turing-complet .

Machines de Turing multi-bandes

Dans l'analyse pratique, divers types de machines de Turing à plusieurs bandes sont souvent utilisés. Les machines à plusieurs bandes sont similaires aux machines à une seule bande, mais il existe un nombre constant k de bandes indépendantes.

Machines de Turing déterministes et non déterministes

Si la table d'action a au plus une entrée pour chaque combinaison de symbole et d'état alors la machine est une "machine de Turing déterministe" (DTM). Si la table d'action contient plusieurs entrées pour une combinaison de symbole et d'état, alors la machine est une "machine de Turing non déterministe" (NDTM). Les deux sont équivalents en termes de calcul, c'est-à-dire qu'il est possible de transformer n'importe quel NDTM en DTM (et vice versa ) , bien qu'ils aient généralement des temps d'exécution différents. Cela peut être prouvé par la construction.

Machines de Turing inconscientes

Une machine de Turing inconsciente est une machine de Turing où, pour chaque longueur d'entrée, le mouvement des différentes têtes est une fonction fixe du temps, indépendante de l'entrée. En d'autres termes, il existe une séquence prédéterminée dans laquelle les différentes bandes sont balayées, avancées et écrites. Les valeurs réelles qui sont écrites sur la bande à n'importe quelle étape peuvent toujours être différentes pour chaque entrée de cette longueur. Pippenger et Fischer ont montré que tout calcul pouvant être effectué par une machine de Turing multi-bandes en n étapes peut être effectué par une machine de Turing à deux bandes inconsciente en plusieurs étapes. $O(n\log n)$

Enregistrer les modèles de machines

Peter van Emde Boas regroupe toutes les machines de ce type dans une seule classe, "la machine à registre". Cependant, historiquement, la littérature a également appelé le membre le plus primitif de ce groupe, c'est-à-dire "la machine de comptage" - "la machine de registre". Et l'incarnation la plus primitive d'une "machine de comptoir" est parfois appelée la "machine de Minsky".

Le modèle « machine de comptoir », également appelé « machine à registres »

La machine à registres modèle primitif est, en effet, une machine Post-Turing multibande à 2 symboles dont le comportement est restreint de sorte que ses bandes agissent comme de simples "compteurs".

À l'époque de Melzak, Lambek et Minsky, la notion de "programme informatique" produisait un type différent de machine simple avec de nombreuses bandes à extrémité gauche coupées à partir d'une bande Post-Turing. Dans tous les cas, les modèles n'autorisent que deux symboles de bande { marque, blanc }.

Certaines versions représentent les entiers positifs uniquement comme une chaîne/une pile de marques autorisées dans un "registre" (c'est-à-dire une bande à extrémité gauche), et une bande vierge représentée par le nombre "0". Minsky a éliminé l'instruction PRINT au détriment de la fourniture à son modèle d'une seule marque obligatoire à l'extrémité gauche de chaque bande.

Dans ce modèle, les bandes-comme-registres asymétriques sont considérées comme des "compteurs", leurs instructions limitées à seulement deux (ou trois si l'instruction TEST/DECREMENT est atomisée). Les deux ensembles d'instructions courants sont les suivants :

(1) : { INC ( r ), DEC ( r ), JZ ( r,z ) }, c'est-à-dire

{ INCremente le contenu du registre #r; DIMINUER le contenu du registre #r; SI le contenu de #r=Zero ALORS Aller à l'instruction #z}

(2) : { CLR ( r ); INC ( r ); JE ( r _i , r _j , z ) }, c'est-à-dire

{ CLaR contenu du registre r; Incrémenter le contenu de r ; comparer le contenu de r _i à r _j et si égal alors sauter à l'instruction z}

Bien que son modèle soit plus compliqué que cette simple description, le modèle du « caillou » de Melzak a étendu cette notion de « compteur » pour permettre des additions et des soustractions de plusieurs cailloux.

Le modèle de la machine à accès aléatoire (RAM)

Melzak a reconnu quelques défauts sérieux dans son modèle de registre/contre-machine : (i) Sans une forme d'adressage indirect, il ne serait pas en mesure de montrer « facilement » que le modèle est l' équivalent de Turing , (ii) Le programme et les registres étaient dans différents "espaces", donc les programmes auto-modifiables ne seraient pas faciles. Lorsque Melzak a ajouté l'adressage indirect à son modèle, il a créé un modèle de machine à accès aléatoire.

(Cependant, avec la numérotation de Gödel des instructions, Minsky a offert une preuve qu'avec une telle numérotation, les fonctions récursives générales étaient en effet possibles ; il offre la preuve que la récursivité est en effet possible).

Contrairement au modèle RASP, le modèle RAM ne permet pas aux actions de la machine de modifier ses instructions. Parfois, le modèle ne fonctionne que de registre à registre sans accumulateur, mais la plupart des modèles semblent inclure un accumulateur.

van Emde Boas divise les différents modèles de RAM en plusieurs sous-types :

SRAM, la « RAM successeur » avec une seule instruction arithmétique, le successeur (INCREMENT h). Les autres incluent "CLEAR h", et un SI d'égalité entre les registres ALORS sauter à xxx.
RAM : le modèle standard avec addition et soustraction
MRAM : la RAM augmentée de la multiplication et de la division
BRAM, MBRAM : versions booléennes au niveau du bit de la RAM et de la MRAM
N**** : versions non déterministes de l'un des éléments ci-dessus avec un N avant le nom

Le modèle de machine à programme stocké à accès aléatoire (RASP)

Le RASP est une RAM avec les instructions stockées avec leurs données dans le même « espace », c'est-à-dire une séquence de registres. La notion de RASP a été décrite au moins dès Kiphengst. Son modèle avait un "moulin" - un accumulateur, mais maintenant les instructions étaient dans les registres avec les données - la soi-disant architecture de von Neumann . Lorsque le RASP a des registres pairs et impairs alternés - le pair contenant le "code d'opération" (instruction) et l'impair contenant son "opérande" (paramètre), alors l'adressage indirect est obtenu en modifiant simplement l'opérande d'une instruction.

Le modèle RASP original d'Elgot et Robinson n'avait que trois instructions à la manière du modèle de la machine à registres, mais ils les ont placées dans l'espace des registres avec leurs données. (Ici, COPY remplace CLEAR lorsqu'un registre, par exemple "z" ou "0" commence par et contient toujours 0. Cette astuce n'est pas inhabituelle. L'unité 1 dans le registre "unit" ou "1" est également utile.)

{ INC ( r ), COPIER ( r _i , r _j ), JE ( r _i , r _i , z ) }

Les modèles RASP permettent l'adressage aussi bien indirect que direct ; certains autorisent également des instructions "immédiates", par exemple "Charger l'accumulateur avec la constante 3". Les instructions peuvent être d'un ensemble très restreint tel que les 16 instructions suivantes de Hartmanis. Ce modèle utilise un accumulateur A. Les mnémoniques sont celles que les auteurs ont utilisées (leur CLA est « load accumulator » à constante ou à partir du registre ; STO est « store accumulator »). Leur syntaxe est la suivante, à l'exception des sauts : "n, <n>, <<n>>" pour "immédiat", "direct" et "indirect"). Les sauts se font via deux « instructions de transfert » TRA — saut inconditionnel par directement « n » ou indirectement « < n > » brouillant le contenu du registre n dans le compteur d’instructions, TRZ (saut conditionnel si l’accumulateur est à zéro de la même manière que TRA) :

{ AJOUTER n , AJOUTER < n >, AJOUTER << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n > , STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, HALT }

Le modèle de machine Pointer

Un retardataire relatif est la machine de modification de stockage de Schönhage ou la machine à pointer . Une autre version est la machine de Kolmogorov-Uspensii et la proposition d'"automate de liaison" de Knuth. (Pour les références voir pointeur machine ). Comme un diagramme de machine à états, un nœud émet au moins deux « arêtes » (flèches) étiquetées qui pointent vers un autre nœud ou des nœuds qui à leur tour pointent vers d'autres nœuds, etc. Le monde extérieur pointe vers le nœud central.

Machines avec entrée et sortie

N'importe laquelle des machines à bandes ci-dessus peut être équipée de bandes d'entrée et de sortie ; toutes les machines basées sur des registres ci-dessus peuvent être équipées de registres d'entrée et de sortie dédiés. Par exemple, le modèle pointeur-machine de Schönhage a deux instructions appelées " input λ ₀ , λ ₁ " et " output β ".

Il est difficile d'étudier sublinéaire la complexité de l' espace sur les machines multi-bandes avec le modèle traditionnel, car une entrée de taille n prend déjà l' espace n . Ainsi, pour étudier de petites classes DSPACE , nous devons utiliser un modèle différent. Dans un certain sens, si nous n'écrivons jamais sur la bande d'entrée, nous ne voulons pas nous facturer cet espace. Et si nous ne « lisons » jamais sur notre bande de sortie, nous ne voulons pas nous facturer cet espace.

Nous résolvons ce problème en introduisant une machine de Turing à chaîne k avec entrée et sortie. Ceci est identique à une ordinaire k -string machine de Turing, sauf que la fonction de transition $δ$ est limitée de telle sorte que la bande d'entrée peut jamais être modifié, et de telle sorte que la tête de sortie peut jamais se déplacer à gauche. Ce modèle nous permet de définir des classes d'espace déterministes plus petites que linéaires. Les machines de Turing avec entrée-sortie ont également la même complexité temporelle que les autres machines de Turing ; dans les mots de Papadimitriou 1994 Prop 2.2 :

Pour toute machine de Turing à k- chaîne M fonctionnant dans le temps, il existe une machine de Turing à -chaîne M' avec entrée et sortie, qui fonctionne dans le temps .

{\style d'affichage f(n)}

{\style d'affichage (k+2)}

{\style d'affichage O(f(n))}

k -string Les machines de Turing avec entrée et sortie peuvent être utilisées dans la définition formelle de la ressource de complexité DSPACE .

Autres machines et méthodes équivalentes

Machine de Turing multidimensionnelle : Par exemple, un modèle de Schönhage utilise les quatre commandes de mouvement de la tête { N orth, S outh, E ast, W est }.
Machine de Turing à une seule bande et à plusieurs têtes : dans une preuve indécidable du « problème de l'étiquette », Minsky et Shepherdson et Sturgis ont décrit des machines avec une seule bande qui pouvaient lire le long de la bande avec une tête et écrire plus loin le long de la bande avec une autre .

L'algorithme de Markov est un autre modèle de calcul remarquablement simple, basé sur la réécriture de chaînes, équivalent aux machines de Turing.
Calcul lambda
Automate de file d'attente

Languages

In other projects