Propriétés de la machine de Turing en tant qu'algorithme. La pensée est matérielle : Alan Turing en tant que « calculateur universel » Modèle de machine de Turing

21.11.2023

L’une des questions les plus importantes de l’informatique moderne est de savoir s’il existe un artiste formel avec lequel on peut imiter n’importe quel artiste formel. la réponse à cette question a été obtenue presque simultanément par deux scientifiques exceptionnels - A. Turing et E. Post. Les artistes proposés différaient les uns des autres, mais il s’est avéré qu’ils pouvaient s’imiter et, surtout, imiter le travail de n’importe quel artiste formel.

Qu’est-ce qu’un exécuteur formel ? Qu'est-ce que cela signifie : un artiste formel imite le travail d'un autre artiste formel ? Si vous avez joué à des jeux informatiques, les objets à l’écran obéissent sans aucun doute aux commandes du joueur. Chaque objet possède un ensemble de commandes valides. Dans le même temps, l'ordinateur lui-même est un interprète, non pas virtuel, mais réel. Il s’avère donc qu’un artiste formel imite le travail d’un autre artiste formel.

Considérons le fonctionnement d'une machine de Turing.

Une machine de Turing est une bande sans fin divisée en cellules et un chariot (dispositif de lecture et d'impression) qui se déplace le long de la bande.

Ainsi, la Machine de Turing est formellement décrite par un ensemble de deux alphabets :

A=(a1, a2, a3, …, an) - alphabet externe, utilisé pour enregistrer les données source

Q=(q1, q2, q3,…, qm) - alphabet interne, décrit un ensemble d'états du dispositif de lecture-impression.

Chaque cellule de la bande peut contenir un caractère de l'alphabet externe A = (a0,a1,…,an) (Dans notre cas A=(0, 1))

Les actions autorisées d'une machine de Turing sont :

1) écrivez n'importe quel symbole de l'alphabet externe dans une cellule de la bande (le symbole qui s'y trouvait auparavant est écrasé)

2) passer à une cellule adjacente

3) changer l'état pour l'un de ceux indiqués par le symbole alphabétique interne Q

Une machine de Turing est un automate contrôlé par une table.

Les lignes du tableau correspondent aux symboles de l'alphabet A sélectionné, et les colonnes correspondent aux états de la machine Q = (q0,q1,…,qm). Au début du fonctionnement, la machine de Turing est dans l'état q1. L'état q0 est l'état final ; une fois dans cet état, la machine termine son fonctionnement.

Chaque cellule du tableau correspondant à un symbole ai et à un état qj contient une commande composée de trois parties
· caractère de l'alphabet A
· sens de déplacement : « > » (à droite), «<» (влево) или «.» (на месте)
· nouvel état de la machine

Dans le tableau ci-dessus, l'alphabet A =(0, 1, _) (contient 3 caractères) et l'alphabet interne Q=(q1, q2, q3, q4, q0), q0 est l'état qui provoque l'arrêt du chariot.

Considérons plusieurs solutions aux problèmes. Vous pouvez télécharger la machine de Turing sur le site dans la rubrique.

Problème 1. Soit A=(0, 1, _). Sur la bande, les cellules contiennent des caractères de l'alphabet dans l'ordre suivant : 0011011. Le chariot est situé au dessus du premier caractère. Il est nécessaire de créer un programme qui remplacera 0 par 1, 1 par 0 et ramènera le chariot à sa position d'origine.

Définissons maintenant les états du chariot. Je les appelle « le désir de faire quelque chose ».

q1) Le chariot doit aller vers la droite : s'il voit 0, il le change en 1 et reste dans l'état q1, s'il voit 1, il le change en 0 et reste dans l'état q1, s'il voit _, il remonte 1 cellule "veut autre chose", c'est à dire passe dans l'état q2. Écrivons notre raisonnement dans le tableau de l'interprète. Pour la syntaxe, consultez l'aide du programme)

q2) Décrivons maintenant le « désir de transport » q2. Nous devons revenir à notre position initiale. Pour ce faire : si on voit 1, on le quitte et on reste dans l'état q2 (avec la même envie d'arriver à la fin de la série de symboles) ; si nous voyons 0, nous le quittons et continuons à nous déplacer vers la gauche dans l'état q2 ; nous voyons _ - se déplace vers la droite d'une cellule. Vous êtes maintenant là où cela est requis dans les conditions de la tâche. on passe à l'état q0.

Vous pouvez voir le programme en action sur la vidéo :

Problème 2. Étant donné : une séquence finie de 0 et 1 (001101011101). Il faut les écrire après cette séquence, à travers une cellule vide, et dans cette séquence les remplacer par 0. Par exemple :

À partir du 001101011101, nous obtenons 000000000000 1111111.

Comme vous pouvez le voir, sept unités ont été écrites après cette séquence, et à leur place il y a des zéros.

Commençons la discussion. Déterminons de quels états le chariot a besoin et combien.

q1) scie 1 - corrigez-la à zéro et passez à un autre état q2 (un nouvel état est introduit pour que le chariot ne change pas tous les uns en zéros en un seul passage)

q2) ne change rien, passe à la fin de la séquence

q3) dès que le chariot voit une cellule vide, il fait un pas vers la droite et tire un 1, s'il voit un 1, il signe le symbole à la fin. Dès que j'ai pioché une unité, on passe à l'état q4

q4) on parcourt les unités écrites sans rien changer. Dès qu'on atteint une cellule vide séparant la séquence des unités, on passe à un nouvel état q5

q5) dans cet état on passe au début de la séquence sans rien changer. On atteint une cellule vide, on fait demi-tour et on passe à l'état q1

Le chariot prendra l'état q0 dans le cas où il passe à l'état q1 jusqu'à la fin de cette séquence et rencontre une cellule vide.

On obtient le programme suivant :

Vous pouvez regarder la machine de Turing en action dans la vidéo ci-dessous.

Qui, après avoir emprunté l'idée à Emil Post, l'aurait eue, semble-t-il, en 1936. Malgré une définition formelle assez complexe, l’idée est simple dans son principe. Pour le comprendre, parcourons les pages de Wikipédia.

Tout d’abord, nous arrivons à la page qui, en fait, s’appelle : « Machine de Turing ».

Machine de Turing

Machine de Turing (MT)- une abstraction mathématique représentant une machine informatique générale. Il a été proposé par Alan Turing en 2010 pour formaliser le concept d'algorithme.

Une machine de Turing est une extension du modèle de machine à états finis et, selon la thèse Church-Turing, est capable de simuler (avec le programme approprié) toute machine dont l'action est de passer d'un état discret à un autre.

La Machine de Turing inclut un infini dans les deux sens ruban, divisé en cellules, et dispositif de contrôle avec un nombre fini d'états.

Le dispositif de contrôle peut se déplacer à gauche et à droite le long de la bande, lire et écrire des caractères d'un alphabet fini dans des cellules. Se démarque particulièrement vide un symbole qui remplit toutes les cellules de la bande, à l'exception de celles d'entre elles (le numéro final) sur lesquelles les données d'entrée sont écrites.

Le dispositif de commande contient table de transition, qui représente l'algorithme, réalisableétant donné la machine de Turing. Chaque règle du tableau demande à la machine, en fonction de l'état actuel et du symbole observé dans la cellule actuelle, d'écrire un nouveau symbole dans cette cellule, de passer à un nouvel état et de déplacer une cellule vers la gauche ou la droite. Certains états de la machine de Turing peuvent être étiquetés comme suit : Terminal, et aller à l'un d'eux signifie la fin du travail, l'arrêt de l'algorithme.

Une machine de Turing s'appelle déterministe, si chaque combinaison d'état et de symbole de ruban dans le tableau correspond à au plus une règle, et non déterministe sinon.

Ainsi, une machine de Turing est une abstraction mathématique, une construction spéculative de l’esprit humain : elle n’existe pas dans la nature. Ou est-ce qu'il y en a ? Ce qui vient immédiatement à l’esprit, c’est le fonctionnement d’une cellule vivante. Au moins deux exemples.

1. Pour produire des protéines dans une cellule, à l'aide d'une enzyme complexe - l'ARN polymérase - les informations sont lues à partir de l'ADN, une sorte de bande d'informations de la machine de Turing. Ici, cependant, les cellules de la bande elle-même ne sont pas réécrites, mais sinon le processus est très similaire : l'ARN polymérase repose sur l'ADN et se déplace le long de celui-ci dans une direction, tandis qu'elle synthétise un brin d'ARN - un acide nucléique similaire à l'ADN. L'ARN fini, une fois détaché de l'enzyme, transporte des informations vers les organites cellulaires dans lesquels les protéines sont produites.

2. Le processus de correction des erreurs dans l'ADN est encore plus similaire à une machine de Turing : sa réparation. Ici, l'ADN polymérase, avec d'autres protéines, se déplace le long de la bande d'ADN et en lit les deux moitiés (l'ADN génomique, comme on le sait, est constitué de deux brins entrelacés qui portent la même information). Si les informations contenues dans les moitiés ne correspondent pas, l’ADN polymérase prélève l’une d’elles comme échantillon et « corrige » l’autre.

Cette analogie n'est pas nouvelle, et sur Wikipédia elle est également décrite dans l'article « Ordinateur moléculaire » :

ordinateur moléculaire

Informatique biomoléculaire ou ordinateurs moléculaires ou encore l'informatique sur l'ADN - ou l'ARN - tous ces termes sont apparus à l'intersection de sciences aussi diverses que la génétique moléculaire et l'informatique.

L'informatique biomoléculaire est un nom collectif désignant diverses techniques liées d'une manière ou d'une autre à l'ADN ou à l'ARN. En informatique ADN, les données ne sont pas représentées sous forme de zéros et de uns, mais sous la forme d’une structure moléculaire construite sur la base de l’hélice de l’ADN. Le rôle du logiciel de lecture, de copie et de gestion des données est assuré par des enzymes spéciales.

La base de tout le système de stockage d'informations biologiques, et donc des ordinateurs à ADN, est la capacité des atomes d'hydrogène inclus dans les composés azotés (adénine, thymine, cytosine et guanine), dans certaines conditions, à s'attirer les uns les autres, formant des liaisons non valentes. paires. D'autre part, ces substances peuvent se lier de valence avec des combinaisons d'une molécule de sucre (désoxyribose) et de phosphate, formant ce qu'on appelle des nucléotides. Les nucléotides, à leur tour, forment facilement des polymères longs de plusieurs dizaines de millions de bases. Dans ces supermolécules, le phosphate et le désoxyribose jouent le rôle de structure porteuse (ils alternent dans la chaîne), et les composés azotés codent l'information.

La molécule s'avère directionnelle : elle commence par un groupe phosphate et se termine par le désoxyribose. Les longues chaînes d’ADN sont appelées brins, les courtes sont appelées oligonucléotides. Chaque molécule d'ADN correspond à un autre ADN - ce qu'on appelle le complément de Watson-Crick. Elle a la direction opposée à celle de la molécule d’origine. L’attraction de l’adénine sur la thymine et de la cytosine sur la guanine donne naissance à la fameuse double hélice, qui permet à l’ADN de doubler lors de la reproduction cellulaire. Le problème du doublement est résolu à l'aide d'une enzyme spéciale, la protéine polymérase. La synthèse ne commence que si un morceau de son complément est attaché à l'ADN. Cette propriété est activement utilisée en biologie moléculaire et en informatique moléculaire. À la base, l’ADN+polymérase est une implémentation d’une machine de Turing, composée de deux bandes et d’un panneau de commande programmable. La console lit les données d'une bande, les traite selon un algorithme et les écrit sur une autre bande. La polymérase lit également séquentiellement les données initiales d'une bande (ADN) et forme sur sa base une bande comme avec les résultats des calculs (addition Watson-Crick).

Des perspectives un peu fantastiques ne font qu’alimenter notre curiosité. En attendant, nous n’avons pas encore tout compris sur la machine de Turing. Comme vous vous en souvenez, dans l'article de Wikipédia, cela était appelé une extension de la machine à états finis. Qu’est-ce qu’une machine à états finis ? Heureusement, un lien y est fourni. En le parcourant, nous découvrons que :

Machine d'état

Les automates abstraits forment une classe fondamentale de modèles discrets, à la fois en tant que modèle à part entière et en tant que composant fondamental des machines de Turing, des automates à mémoire de stockage, des machines à états finis et d'autres transformateurs d'informations.

Avec chaque définition, nous pénétrons de plus en plus dans le domaine des mathématiques pures. Le langage devient plus strict, des définitions formelles apparaissent, constituées de symboles mathématiques. Si nous allons plus loin, nous arriverons à la théorie des algorithmes et à la théorie de la calculabilité. Vous pouvez parcourir les pages de Wikipédia pendant longtemps, mais il vaut mieux faire le plein d'eau et de nourriture au cas où vous vous promèneriez dans le désert d'axiomes et de définitions, ou au moins de liens fiables vers des manuels de mathématiques, par exemple http:/ /www.mccme.ru/free-books/, ou des articles du magazine Potential ;)

J'espère que cette explication vous permettra de comprendre un peu plus clairement ce qu'est exactement une machine de Turing ?

Revenons sur l'histoire de ce terme.

Ainsi, comme nous l'avons déjà mentionné, Alan Turing a parlé au monde de sa machine en 1937 dans la soi-disant thèse Church-Turing. L'article « Alan Turing » nous parlera d'Alan Turing, le premier hacker et pionnier de l'informatique, tel qu'écrit sur la plaque commémorative de l'hôtel où il est né. Nous ne donnerons pas ici le texte intégral de l’article, mais celui-ci lui-même n’est pas très détaillé.

Alan Turing

Turing, Alan Matheson(23 juin 1912 - 7 juin 1954) - Mathématicien, logicien, cryptographe anglais, inventeur de la machine de Turing.

L'article lui-même en dit plus sur le travail de Turing : en plus du texte sur la machine de Turing, que nous donnerons plus tard, il est dit qu'il a travaillé sur le « problème du gel » (C'est drôle, n'est-ce pas ? Il n'y avait pas encore d'ordinateurs , et le système Windows non plus, mais il y avait déjà un problème de gel.); l'histoire héroïque de la façon dont Turing a déchiffré le code Enigma pendant la Seconde Guerre mondiale et a ainsi sauvé la Grande-Bretagne ; le fait qu'il soit le fondateur de la théorie de l'intelligence artificielle, ainsi qu'une mention du célèbre test de Turing. De nos jours, ce test n'est plus aussi souvent utilisé comme prémisse d'un récit de science-fiction, mais le problème de l'humain dans la machine restera toujours un classique, à l'instar des romans d'Isaac Asimov et de Stanislaw Lem.

Malgré son caractère démodé, le test de Turing est apparu de manière inattendue dans le monde moderne de la communication sur Internet. Par exemple, vous pouvez tomber sur le texte d'un dialogue entre deux utilisateurs d'ICQ, dont l'un est un « bot », et la tâche est de déterminer lequel. Ou encore, un utilisateur inconnu, peut-être un robot ICQ, peut frapper à votre porte. Le reconnaissez-vous ? En étudiant la théorie, vous pourrez peut-être appliquer le test de Turing à temps et ne pas vous laisser tromper. Vous pouvez commencer votre étude avec l'article Wikipédia correspondant, puis suivre les liens fournis à la fin de l'article :

Test de Turing

Test de Turing- un test proposé par Alan Turing en 1950 dans l'article « Computing machines and intelligence » pour tester si un ordinateur est intelligent au sens humain du terme.

Le juge (humain) correspond en langage naturel avec deux interlocuteurs dont l'un est une personne, l'autre est un ordinateur. Si le juge ne peut pas déterminer de manière fiable qui est qui, l’ordinateur a réussi le test. On suppose que chacun des interlocuteurs s'efforce d'être reconnu en tant que personne. Afin de rendre le test simple et universel, la correspondance est réduite à la messagerie texte.

La correspondance doit avoir lieu à intervalles contrôlés afin que le juge ne puisse pas tirer de conclusions basées sur la rapidité des réponses. (À l’époque de Turing, les ordinateurs réagissaient plus lentement que les humains. Aujourd’hui, cette règle est nécessaire car ils réagissent beaucoup plus rapidement que les humains.)

Le test s'inspire d'un jeu de société dans lequel les invités tentaient de deviner le sexe d'une personne dans une autre pièce en écrivant des questions et en lisant les réponses. Dans la formulation originale de Turing, la personne devait se faire passer pour une personne du sexe opposé et le test durait 5 minutes. Ces règles ne sont actuellement pas considérées comme nécessaires et ne font pas partie de la spécification du test.

Turing a proposé un test pour remplacer, à son avis, la question dénuée de sens « une machine peut-elle penser ? » à un plus spécifique.

Turing a prédit que les ordinateurs finiraient par réussir son test. Il pensait que d'ici 2000, un ordinateur doté d'un milliard de bits de mémoire (environ 119 Mo) serait capable de tromper les juges dans 30 % des cas lors d'un test de 5 minutes. Cette prédiction ne s'est pas réalisée. (Il est vrai que lors du premier concours Loebner, le programme informatique « PC Therapist » sur un IBM PC 386 a pu tromper 5 juges sur 10, mais son résultat n'a pas été crédité et, en 1994, le concours a été rendu plus difficile.) Turing a également prédit que la combinaison « machine pensante » ne serait pas considérée comme un oxymore et que la formation en informatique jouerait un rôle important dans la création d'ordinateurs puissants (ce avec lequel la plupart des chercheurs modernes sont d'accord).

Jusqu’à présent, aucun programme n’a réussi le test. Des programmes comme ELIZA faisaient parfois croire aux gens qu'ils parlaient à une personne, comme dans une expérience informelle appelée AOLiza. Mais de tels « succès » ne constituent pas une réussite au test de Turing. Premièrement, la personne participant à de telles conversations n'avait aucune raison de croire qu'elle parlait au programme, alors que dans un véritable test de Turing, la personne essaie activement de déterminer avec qui elle parle. Deuxièmement, les cas documentés ont tendance à se produire dans des forums de discussion tels que IRC, où de nombreuses conversations sont fragmentaires et dénuées de sens. Troisièmement, de nombreux utilisateurs d'IRC utilisent l'anglais comme deuxième ou troisième langue, et la réponse absurde d'un programme est probablement attribuée à une barrière linguistique. Quatrièmement, de nombreux utilisateurs ne connaissent rien d'Eliza et des programmes similaires et ne peuvent pas reconnaître les erreurs totalement inhumaines que commettent ces programmes.

Chaque année, il y a un concours entre programmes parlants, et le plus humain, de l'avis des juges, reçoit le prix Loebner. Il y a un prix supplémentaire pour le programme qui, selon les juges, réussira le test de Turing. Ce prix n'a pas encore été attribué.

Le programme A.L.I.C.E a montré le meilleur résultat au test de Turing. gagner le test 3 fois (en 2000, 2001 et 2004).

Liens

Turing A. M. Machines informatiques et intelligence. // Dans : Hofstader D., Dennett D. L'Œil de l'esprit. - Samara : Bakhrakh-M, 2003. - pp. 47-59.
Livre en anglais : Roger Penrose « The Emperor’s New Mind ».
Article d'Alan Turing :
- Alan Turing, « Machines informatiques et intelligence », Mind, vol. LIX, non. 236, octobre 1950, p. 433-460.
- En ligne:
Article de G. Oppy et D. Dowe sur le test de Turing tiré de la Stanford Encyclopedia of Philosophy (en anglais)
"Test de Turing : 50 ans plus tard" passe en revue 50 années de travail sur le test de Turing, dans la perspective de l'an 2000.

Revenons à nouveau à la machine de Turing. Un extrait d'un article sur Alan Turing indique que le concept d'une machine de Turing a été proposé pour la première fois dans le cadre de ce qu'on appelle. Thèse de Church-Turing :

Extrait de l'article Wikipédia "Alan Turing"

Toute fonction intuitivement calculable est partiellement calculable ou, de manière équivalente, calculable par une machine de Turing.

Alan Turing a proposé (connu sous le nom de thèse Church-Turing) que tout algorithme au sens intuitif du terme puisse être représenté par une machine de Turing équivalente. La clarification du concept de calculabilité basée sur le concept de machine de Turing (et d'autres concepts équivalents) a ouvert la possibilité de prouver rigoureusement l'insolvabilité algorithmique de divers problèmes de masse (c'est-à-dire les problèmes de recherche d'une méthode unifiée pour résoudre une certaine classe de problèmes). problèmes dont les conditions peuvent varier dans certaines limites). L’exemple le plus simple d’un problème de masse insoluble sur le plan algorithmique est ce qu’on appelle le problème d’applicabilité de l’algorithme (également appelé problème d’arrêt). Elle consiste en ce qui suit : il s'agit de trouver une méthode générale qui permettrait, pour une machine de Turing arbitraire (précisée par son programme) et un état initial arbitraire de la bande de cette machine, de déterminer si le fonctionnement de la machine sera être complété en un nombre fini d’étapes, ou se poursuivre indéfiniment.

Dans un article intitulé « La thèse Church-Turing », ils écrivent à son sujet comme ceci :

Thèse Church-Turing

Thèse Church-Turing- une déclaration fondamentale pour de nombreux domaines scientifiques, tels que la théorie de la calculabilité, l'informatique, la cybernétique théorique, etc. Cette déclaration a été faite par Alonzo Church et Alan Turing au milieu des années 1930.

Dans sa forme la plus générale, il stipule que toute fonction intuitivement calculable est partiellement calculable, ou de manière équivalente, calculable par une machine de Turing.

La thèse de Church-Turing ne peut être rigoureusement prouvée ou réfutée car elle établit une « égalité » entre la notion strictement formalisée de fonction partiellement calculable et la notion informelle de « fonction intuitivement calculable ».

Thèse de physique Church-Turing lit : Toute fonction pouvant être calculée par un appareil physique peut être calculée par une machine de Turing.

De ce carrefour on peut s’orienter, par exemple, vers la théorie de la calculabilité. Ou vous pouvez essayer de découvrir qui est cette mystérieuse Église, avec laquelle Alan Turing a soutenu sa thèse.

Machine de Turing universelle

Machine de Turing universelle appelée machine de Turing, qui peut remplacer n'importe quelle machine de Turing. Après avoir reçu un programme et saisi des données en entrée, il calcule la réponse qu'une machine de Turing dont le programme a été donné en entrée aurait calculé à partir des données d'entrée.

Définition formelle

Le programme de toute machine de Turing déterministe peut être écrit en utilisant un alphabet fini composé de symboles d'état, de parenthèses, de flèches, etc. ; désignons cet alphabet de machine comme Σ 1 (\displaystyle \Sigma _(1)). Puis la machine de Turing universelle U pour la classe alphabétique des voitures Σ 2 (\displaystyle \Sigma _(2)) Et k les bandes d'entrée s'appellent une machine de Turing avec k+1 ruban d'entrée et alphabet Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\cup \Sigma _(2)) de sorte que si vous postulez pour le premier k enregistre la valeur d'entrée, et sur k+1 est le code correctement écrit d'une machine de Turing, alors U produira la même réponse qu'elle produirait avec ces données d'entrée M 1 (\style d'affichage M_(1)), ou fonctionnera indéfiniment si M 1 (\style d'affichage M_(1)) ne s'arrêtera pas avec ces données.

Le théorème universel de la machine de Turing déclare qu'une telle machine existe et modélise d'autres machines avec au plus un ralentissement quadratique (c'est-à-dire si la machine d'origine produisait tétapes, alors l'universel ne produira plus côté 2). La preuve de ce théorème est constructive (il n'est pas difficile de construire une telle machine, il suffit de la décrire soigneusement). Le théorème a été proposé et prouvé par Turing en 1936-37.

La mise en œuvre du logiciel dans le langage de programmation Delphi est assez simple. L'une de ces implémentations peut être trouvée sur le site Web http://kleron.ucoz.ru/load/24-1-0-52. Il est possible de télécharger et de sauvegarder dans un fichier Excel.

Machine de Turing non déterministe

Machine de Turing probabiliste

Une généralisation d'une machine de Turing déterministe, dans laquelle, à partir de n'importe quel état et valeur sur la bande, la machine peut effectuer une parmi plusieurs (on peut compter, sans perte de généralité, deux) transitions possibles, et le choix est fait de manière probabiliste (en lançant une pièce de monnaie).

Une machine de Turing probabiliste est similaire à une machine de Turing non déterministe, mais au lieu d'une transition non déterministe, la machine choisit l'une des options avec une certaine probabilité.

Il existe également une définition alternative :

Une machine de Turing probabiliste est une machine de Turing déterministe qui dispose en outre d'une source matérielle de bits aléatoires, dont elle peut, par exemple, « ordonner » et « charger » n'importe quel nombre sur une bande séparée, puis l'utiliser dans les calculs de la manière habituelle pour MT.

La classe d'algorithmes qui se terminent en temps polynomial sur une machine de Turing probabiliste et renvoient une réponse avec une erreur inférieure à 1/3 est appelée classe BPP.

Considérons le fonctionnement d'une machine de Turing.

Une machine de Turing est une bande sans fin divisée en cellules et un chariot (dispositif de lecture et d'impression) qui se déplace le long de la bande.

Ainsi, la Machine de Turing est formellement décrite par un ensemble de deux alphabets :

A=(a1, a2, a3, …, an) - alphabet externe, utilisé pour enregistrer les données source

Q=(q1, q2, q3,…, qm) - alphabet interne, décrit un ensemble d'états du dispositif de lecture-impression.

Chaque cellule de la bande peut contenir un caractère de l'alphabet externe A = (a0,a1,…,an) (Dans notre cas A=(0, 1))

Les actions autorisées d'une machine de Turing sont :

1) écrivez n'importe quel symbole de l'alphabet externe dans une cellule de la bande (le symbole qui s'y trouvait auparavant est écrasé)

2) passer à une cellule adjacente

3) changer l'état pour l'un de ceux indiqués par le symbole alphabétique interne Q

Une machine de Turing est un automate contrôlé par une table.

Dans le tableau ci-dessus, l'alphabet A =(0, 1, _) (contient 3 caractères) et l'alphabet interne Q=(q1, q2, q3, q4, q0), q0 est l'état qui provoque l'arrêt du chariot.

Considérons plusieurs solutions aux problèmes. Vous pouvez télécharger la machine de Turing sur le site Internet dans la section TÉLÉCHARGEMENT.

Définissons maintenant les états du chariot. Je les appelle « le désir de faire quelque chose ».

q1) Le chariot doit aller vers la droite : s'il voit 0, il le change en 1 et reste dans l'état q1, s'il voit 1, il le change en 0 et reste dans l'état q1, s'il voit _, il revient à 1 cellule « veut autre chose », c'est-à-dire passe à l'état q2. Écrivons notre raisonnement dans le tableau de l'interprète. Pour la syntaxe, consultez l'aide du programme)

Vous pouvez voir le programme en action sur la vidéo :

À partir du 001101011101, nous obtenons 000000000000 1111111.

Comme vous pouvez le voir, sept unités ont été écrites après cette séquence, et à leur place il y a des zéros.

Commençons la discussion. Déterminons de quels états le chariot a besoin et combien.

q1) scie 1 - corrigez-la à zéro et passez à un autre état q2 (un nouvel état est introduit pour que le chariot ne change pas tous les uns en zéros en un seul passage)

q2) ne change rien, passe à la fin de la séquence

q3) dès que le chariot voit une cellule vide, il fait un pas vers la droite et tire un 1, s'il voit un 1, il signe le symbole à la fin. Dès que j'ai pioché une unité, on passe à l'état q4

q4) on parcourt les unités écrites sans rien changer. Dès qu'on atteint une cellule vide séparant la séquence des unités, on passe à un nouvel état q5

q5) dans cet état on passe au début de la séquence sans rien changer. On atteint une cellule vide, on fait demi-tour et on passe à l'état q1

Le chariot prendra l'état q0 dans le cas où il passe à l'état q1 jusqu'à la fin de cette séquence et rencontre une cellule vide.

On obtient le programme suivant :

Vous pouvez regarder la machine de Turing en action dans la vidéo ci-dessous.

Machine de Turing (MT)- interprète abstrait (machine informatique abstraite). A été suggéré Alan Turing V 1936 formaliser le concept algorithme.

La machine de Turing est une extension machine à états finis et, selon Thèse Church-Turing, est capable de simuler tous les autres exécuteurs (en spécifiant des règles de transition) qui implémentent d'une manière ou d'une autre le processus de calcul étape par étape, dans lequel chaque étape de calcul est assez élémentaire.

Conception de la machine de Turing

La machine de Turing est infinie dans les deux sens. ruban(Il est possible que des machines de Turing aient plusieurs bandes infinies), divisées en cellules et dispositif de contrôle, capable d'être dans l'un des ensemble d'états. Le nombre d'états possibles du dispositif de commande est fini et précisément précisé.

Le dispositif de contrôle peut se déplacer à gauche et à droite le long de la bande, lire et écrire des symboles d'un alphabet fini dans les cellules de la bande. Se démarque particulièrement vide un symbole qui remplit toutes les cellules de la bande, à l'exception de celles d'entre elles (le numéro final) sur lesquelles les données d'entrée sont écrites.

Le dispositif de commande fonctionne selon règles de transition, qui représentent l'algorithme, réalisable cette machine de Turing. Chaque règle de transition demande à la machine, en fonction de l'état actuel et du symbole observé dans la cellule actuelle, d'écrire un nouveau symbole dans cette cellule, de passer à un nouvel état et de déplacer une cellule vers la gauche ou la droite. Certains états de la machine de Turing peuvent être étiquetés comme suit : Terminal, et aller à l'un d'eux signifie la fin du travail, l'arrêt de l'algorithme.

Une machine de Turing s'appelle déterministe, si chaque combinaison d'état et de symbole de ruban dans le tableau correspond à au plus une règle. S'il existe une paire "symbole du ruban - état" pour laquelle il y a 2 instructions ou plus, une telle machine de Turing est appelée non déterministe .

Description de la machine de Turing

Une machine de Turing spécifique est définie en répertoriant les éléments de l'ensemble des lettres de l'alphabet A, l'ensemble des états Q et l'ensemble des règles selon lesquelles la machine fonctionne. Ils ont la forme : q i a j →q i1 a j1 d k (si la tête est dans l'état q i, et la lettre a j est écrite dans la cellule observée, alors la tête passe à l'état q i1, a j1 est écrit dans la cellule au lieu de a j, la tête effectue un mouvement d k, qui a trois options : une cellule vers la gauche (L), une cellule vers la droite (R), rester en place (N)). Pour toutes les configurations possibles il y a exactement une règle. Il n’y a pas de règles uniquement pour l’état final, une fois que la voiture s’arrête. De plus, vous devez spécifier les états final et initial, la configuration initiale sur la bande et l'emplacement de la tête de la machine.

Un exemple de machine de Turing

Donnons un exemple de MT pour multiplier des nombres dans système de numérotation unaire. La machine fonctionne selon l'ensemble de règles suivant :

Un ensemble de règles	Un ensemble de règles


q 0 × → q 1 × R



	q 6 × → q 7 × R
q 2 × → q 3 × L
q 3 1 → q 4 aR


q 4 × → q 4 × R

Multiplions en utilisant MT 3 par 2 dans le système d'unités :

Le protocole indique les états initial et final du MT, la configuration initiale sur la bande et l'emplacement de la tête de la machine (symbole souligné).

Complétude de Turing

Article principal: Complétude de Turing

On peut dire qu'une machine de Turing est la machine informatique la plus simple à mémoire linéaire, qui, selon des règles formelles, transforme les données d'entrée à l'aide d'une séquence actions élémentaires.

Le caractère élémentaire des actions réside dans le fait que l'action ne modifie qu'une petite donnée en mémoire (dans le cas d'une machine de Turing, une seule cellule), et que le nombre d'actions possibles est fini. Malgré la simplicité de la machine de Turing, elle peut calculer tout ce qui peut être calculé sur n'importe quelle autre machine effectuant des calculs à l'aide d'une séquence d'actions élémentaires. Cette propriété est appelée exhaustivité.

Une façon naturelle de prouver que les algorithmes de calcul pouvant être implémentés sur une machine peuvent l’être sur une autre est de simuler la première machine sur une seconde.

L'imitation est la suivante. Une description du programme (règles de fonctionnement) de la première machine est fournie à l'entrée de la deuxième machine. D et données d'entrée X, qui aurait dû arriver à l'entrée de la première machine. Il est nécessaire de décrire un tel programme (règles de fonctionnement de la deuxième machine) pour qu'à la suite des calculs, la sortie soit la même que celle que la première machine renverrait si elle recevait des données en entrée X.

Comme cela a été dit, sur une machine de Turing, il est possible de simuler (en spécifiant des règles de transition) tous les autres exécuteurs qui mettent en œuvre d'une manière ou d'une autre le processus de calcul étape par étape, dans lequel chaque étape du calcul est assez élémentaire.

Sur une machine de Turing, vous pouvez simuler La voiture de la poste, algorithmes de Markov normaux et tout programme pour ordinateurs ordinaires qui convertit les données d'entrée en données de sortie à l'aide d'un algorithme. À son tour, une machine de Turing peut être simulée à l’aide de divers exécuteurs abstraits. Les artistes pour lesquels cela est possible sont appelés Turing terminé(Turing terminé).

Il existe des programmes pour ordinateurs ordinaires qui simulent le fonctionnement d'une machine de Turing. Mais il faut noter que cette simulation est incomplète, puisque la machine de Turing contient une bande infinie abstraite. Une bande sans fin contenant des données ne peut pas être entièrement simulée sur un ordinateur doté d'une mémoire finie (la mémoire totale de l'ordinateur - RAM, disques durs, divers supports de stockage externes, registres et cache du processeur, etc. - peut être très volumineuse, mais néanmoins toujours limitée ).

Variantes de machines de Turing

Le modèle de machine de Turing peut être étendu. On peut considérer des machines de Turing avec un nombre arbitraire de bandes et des bandes multidimensionnelles avec diverses restrictions. Cependant, toutes ces machines sont Turing complètes et sont modélisées par une machine de Turing ordinaire.

Machine de Turing fonctionnant sur une bande semi-infinie

À titre d’exemple de telles informations, considérons le théorème suivant : Pour toute machine de Turing, il existe une machine de Turing équivalente fonctionnant sur une bande semi-infinie.

Considérons la preuve donnée par Yu. G. Karpov dans le livre « Theory of Automata ». La preuve de ce théorème est constructive, c'est-à-dire que nous donnerons un algorithme grâce auquel pour toute machine de Turing, une machine de Turing équivalente avec la propriété déclarée peut être construite. Tout d'abord, nous numérotons aléatoirement les cellules de la bande de travail MT, c'est-à-dire que nous déterminons un nouvel emplacement d'informations sur la bande :

Ensuite on renumérote les cellules, et on supposera que le symbole « * » n'est pas contenu dans le dictionnaire MT :

Enfin, changeons la machine de Turing en doublant le nombre de ses états, et changeons le décalage de la tête de lecture-écriture pour que dans un groupe d'états le fonctionnement de la machine soit équivalent à son fonctionnement dans la zone ombrée, et dans dans un autre groupe d'états, la machine fonctionnerait comme la machine d'origine fonctionne dans la zone non ombrée. Si le symbole « * » est rencontré pendant le fonctionnement du MT, cela signifie que la tête de lecture-écriture a atteint la limite de zone :

L'état initial de la nouvelle machine de Turing est défini dans l'une ou l'autre zone, selon l'endroit où se trouvait la tête de lecture-écriture dans la configuration d'origine sur la bande d'origine. Évidemment, à gauche des marqueurs de délimitation "*", la bande n'est pas utilisée dans une machine de Turing équivalente.

J'ai décidé d'expliquer à l'humanité le principe des calculs algorithmiques. Le fait est que M. Turing était un prophète de l’ère informatique, il ne pouvait donc s’empêcher de dire aux gens ce qu’est un algorithme. Il a donc imaginé une machine abstraite qui porte son nom. C'est-à-dire le nom de famille. Mais prenons les choses dans l'ordre...

L'essence en mots simples

Un point important doit être immédiatement noté : une machine de Turing est un dispositif exclusivement spéculatif. Rien de tel n’existe dans la nature. Il existe cependant des modèles informatiques. Même les actifs. Mais ce ne sont que des modèles.

Pourquoi donc? Parce que le sujet de discussion est une bande sans fin, dont la pleine existence physique à ce stade du développement de la science et de la technologie n'est possible que théoriquement.

La bande est constituée de cellules, comme une chaîne de maillons. Les cellules contiennent des données, par exemple des caractères alphabétiques. Eh bien, ou des zéros et des uns. En général, tout ce qui convient au traitement automatique. Ceci est réalisé par une partie mobile de la machine.

Comment ça fonctionne

La partie mobile est le lecteur et l’écrivain. Une sorte d'engin capable de lire le contenu des cellules, d'y écrire quelque chose qui lui est propre et, plus important encore, d'agir en fonction des résultats obtenus.

De plus, la machine ne peut déplacer qu’une seule cellule à la fois. Droite, gauche, partout où cela est nécessaire pour effectuer des calculs. Ici, vous avez ajouté quelque chose - vous devez bouger pour retirer quelque chose. Et puis pliez-le à nouveau. Et ainsi de suite aussi longtemps que nécessaire jusqu'à ce que la tâche soit terminée. La bande est infinie, il y a suffisamment d'options pour n'importe quelle opération.

En fait, Alan Turing essayait justement de souligner que chaque calcul, aussi complexe soit-il, peut être effectué par étapes, étape par étape, divisant le problème en composants élémentaires. C'est l'essence de l'algorithme.

Différentes variantes

Les cybernéticiens novices ont examiné la machine de Turing et ont réalisé qu'il n'y avait rien à redire. En effet, les programmes informatiques doivent être construits sur la base d'algorithmes - exécution d'instructions étape par étape.

Dans le même temps, la renommée d’Alan Turing en a hanté beaucoup et ses adeptes ont commencé, comme on dit, à en avoir un aperçu. Ils ont commencé à inventer des machines de Turing multidimensionnelles, avec de nombreuses bandes, des machines « semi-infinies », etc.

Nous essaierons d'apporter au moins un peu de clarté à ce chaos et d'envisager de véritables options pour l'appareil en discussion.

Non déterministe- il s'agit d'une machine de Turing qui fonctionne sur la bande à cellules décrite ci-dessus en fonction de la situation qui se présente à une étape particulière des calculs. En d’autres termes, là où elle doit aller, c’est là qu’elle ira.
Déterministe- celui qui contient des instructions spécifiques. Par exemple, si la lettre A est écrite dans la cellule où se trouve la machine d'exécution, alors vous devez vous déplacer vers celle adjacente, avec la lettre B, que vous le vouliez ou non.
Complet- capable de calculer tout ce qui peut être calculé par des opérations étape par étape. Il peut même simuler une machine dans une machine, un émulateur qui décrit avec des algorithmes le fonctionnement d'un autre appareil similaire.
Universel- capable de tout ce que n'importe quelle variante d'une machine de Turing peut faire. En général, n'importe lequel, même pas encore inventé. Bien sûr, c'est complet.

Avantages pratiques

Bien entendu, un algorithme est un concept plus complexe que le simple déplacement d’une exécution étape par étape dans un espace unidimensionnel. Après tout, créer des branchements, des boucles, revenir en arrière et utiliser des sous-programmes sont possibles.

De plus, il est impossible en pratique de simuler un nombre infini de cellules contenant des données, ne serait-ce que parce que les capacités des équipements informatiques sont limitées.

Cependant, il existe des programmes simulant des machines de Turing conçues pour enseigner aux étudiants. Les programmeurs débutants sont encouragés à développer différents algorithmes, par exemple en recherchant, en modifiant, en ajoutant ou en réorganisant des lettres dans des cellules.

Par conséquent, les avantages de la machine de Turing sont exactement ceux souhaités par son créateur, le prophète de l’ère informatique : une démonstration claire de l’essence des calculs algorithmiques.

Publications précédentes :

Dernière édition : 2013-04-01 10:58:05

Étiquettes matérielles : ,