Qui, ayant emprunté l'idée à Emil Post, l'a eue, pense-t-on, en 1936. Malgré la définition formelle assez compliquée, 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 un type général d'ordinateur. Il a été proposé par Alan Turing dans l'année pour formaliser le concept d'algorithme.
La machine de Turing est une extension du modèle des automates finis et, selon la thèse de Church-Turing, est capable d'imiter (s'il existe un programme approprié) toute machine dont l'action est de passer d'un état discret à un autre.
La composition de la machine de Turing comprend l'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 les cellules. Une spéciale vide un symbole qui remplit toutes les cellules de la bande, sauf celles d'entre elles (un nombre fini) sur lesquelles les données d'entrée sont enregistrées.
Le dispositif de contrôle contient table de saut, qui représente l'algorithme, réalisable machine de Turing donnée. Chaque règle du tableau ordonne à la machine, selon l'état courant et le symbole observé dans la cellule courante, d'écrire un nouveau symbole dans cette cellule, de passer à un nouvel état et de se déplacer d'une cellule vers la gauche ou vers la droite. Certains états de la machine de Turing peuvent être étiquetés comme Terminal, et la transition vers l'un d'eux signifie la fin du travail, l'arrêt de l'algorithme.
La 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 autrement.
Ainsi, la 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-il? Vient immédiatement à l'esprit le fonctionnement d'une cellule vivante. Au moins deux exemples.
1. Pour la production de 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'information de la machine de Turing. Ici, cependant, les cellules de la bande elle-même ne sont pas écrasées, 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, se détachant de l'enzyme, transmet des informations aux organites cellulaires dans lesquels les protéines sont produites.
2. Le processus de correction des erreurs dans l'ADN est encore plus similaire à la 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 vous le savez, se compose de deux brins entrelacés portant la même information). Si les informations contenues dans les moitiés ne correspondent pas, l'ADN polymérase prend l'une d'entre elles comme modèle et « gouverne » l'autre.
Une telle 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 de l'ADN - ou de l'ARN - tous ces termes sont apparus à la jonction de sciences aussi différentes que la génétique moléculaire et l'informatique.
L'informatique biomoléculaire est un nom collectif pour diverses techniques liées d'une manière ou d'une autre à l'ADN ou à l'ARN. Dans les calculs d'ADN, les données ne sont pas présentées sous la forme de zéros et de uns, mais sous la forme d'une structure moléculaire construite sur la base de l'hélice d'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 de l'information biologique, et donc des ordinateurs à ADN, est la capacité des atomes d'hydrogène, qui font partie des composés azotés (adénine, thymine, cytosine et guanine), sous certaines conditions, à s'attirer les uns vers les autres, formant paires liées non-valentes. D'autre part, ces substances peuvent se lier par valence à des combinaisons d'un sucre (désoxyribose) et d'une molécule de phosphate, formant ce que l'on appelle des nucléotides. Les nucléotides, à leur tour, forment facilement des polymères de dizaines de millions de bases de long. Dans ces supermolécules, le phosphate et le désoxyribose jouent le rôle de structure porteuse (ils alternent dans la chaîne), tandis que les composés azotés codent l'information.
La molécule s'avère être dirigée : elle commence par un groupement phosphate et se termine par le désoxyribose. Les longs brins d'ADN sont appelés brins, les courts sont appelés oligonucléotides. Chaque molécule d'ADN correspond à un autre ADN - le soi-disant complément de Watson-Crick. Il a la direction opposée à celle de la molécule d'origine. Du fait de l'attraction de l'adénine sur la thymine et de la cytosine sur la guanine, la fameuse double hélice se forme, ce qui permet à l'ADN de se dupliquer lors de la reproduction cellulaire. La tâche de doubler est résolue à l'aide d'une protéine-enzyme spéciale - la 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 télécommande 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 sur leur base forme une bande, pour ainsi dire, avec les résultats des calculs (addition Watson-Crick).
Des perspectives un peu fantastiques ne font qu'attiser notre curiosité. Pendant ce temps, nous n'avons pas encore tout compris sur la machine de Turing. Comme vous vous en souvenez, dans l'article de Wikipedia, cela s'appelait une extension de la machine d'état. Qu'est-ce qu'une machine à états finis ? Heureusement, il existe un lien vers celui-ci. En le parcourant, on apprend 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 central des machines de Turing, des automates à pile, des automates finis et d'autres convertisseurs d'informations.
A 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 longuement les pages de Wikipédia, mais mieux vaut faire le plein d'eau et de nourriture au cas où vous vous promèneriez dans le désert des axiomes et des définitions, ou du moins des liens fiables vers des manuels de mathématiques, par exemple http : //www.mccme.ru/free-books/, ou des articles du magazine "Potential";)
Espérons qu'après cette explication, vous ayez compris ce qu'est exactement une machine de Turing ?
Revenons à 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. À propos d'Alan Turing - le premier hacker et pionnier de l'informatique, comme il est écrit sur la plaque commémorative de l'hôtel où il est né, l'article "Alan Turing" nous le dira. Nous ne donnerons pas ici le texte intégral de l'article, mais il n'est pas très détaillé en soi.
Alan Turing
Turing, Alan Mathison(23 juin 1912 - 7 juin 1954) - Mathématicien, logicien, cryptographe anglais, inventeur de la machine de Turing.
L'article lui-même est 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 suspendu" (C'est marrant, n'est-ce pas ? Il n'y avait pas encore d'ordinateurs , et Windows aussi, mais il y avait déjà un problème de blocage.); 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é le Royaume-Uni ; le fait qu'il soit le fondateur de la théorie de l'intelligence artificielle, ainsi que la mention du célèbre test de Turing. Désormais, ce test n'est plus souvent utilisé comme début d'une histoire 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 Stanislav Lem.
Bien qu'il soit démodé, le test de Turing a refait surface de manière inattendue dans le monde actuel de la communication Internet. Par exemple, vous pouvez rencontrer le texte du dialogue de deux utilisateurs d'ICQ, dont l'un est un "bot", et la tâche consiste à déterminer lequel. Ou 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 tromper. Vous pouvez commencer votre étude par l'article Wikipédia correspondant, puis suivre les liens fournis à la fin de l'article :
Essai de Turing
Essai de Turing- un test proposé par Alan Turing en 1950 dans l'article "Machines informatiques et intelligence" pour vérifier si un ordinateur est intelligent au sens humain du terme.
Le juge (humain) correspond en langage naturel avec deux interlocuteurs dont l'un est un humain, 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 cherche à ê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 à des intervalles contrôlés afin que le juge ne puisse tirer des conclusions de la rapidité des réponses. (À l'époque de Turing, les ordinateurs réagissaient plus lentement que les humains. Maintenant, cette règle est nécessaire car ils réagissent beaucoup plus rapidement que les humains.)
Le test s'inspirait d'un jeu de société dans lequel les invités essayaient 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, une personne devait faire semblant d'être une personne du sexe opposé, et le test durait 5 minutes. Désormais, ces règles ne sont pas considérées comme nécessaires et ne sont pas incluses dans la spécification de test.
Turing a proposé un test pour remplacer la question dénuée de sens, à son avis, "une machine peut-elle penser?" à un plus spécifique.
Turing a prédit que les ordinateurs finiraient par réussir son test. Il croyait qu'en l'an 2000, un ordinateur avec une mémoire de 1 milliard de bits (environ 119 Mo) dans un test de 5 minutes pourrait tromper les juges 30% du temps. Cette prédiction ne s'est pas réalisée. (Certes, lors du premier concours Loebner, le programme informatique "PC Therapist" sur IBM PC 386 a réussi à tromper 5 juges sur 10, mais il n'a pas compté le résultat, et en 1994 le concours a été rendu plus difficile.) Turing a également prédit que la combinaison "machine à penser" ne serait pas considérée comme un oxymore, et que la formation en informatique jouerait un rôle important dans la construction d'ordinateurs puissants (avec lesquels la plupart des chercheurs modernes sont d'accord).
Jusqu'à présent, aucun programme n'a même failli passer 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 passent pas le test de Turing. Premièrement, la personne dans de telles conversations n'avait aucune raison de croire qu'elle parlait au programme, alors que dans le vrai test de Turing, la personne essaie activement de déterminer à qui elle parle. Deuxièmement, les cas documentés se trouvent généralement dans des forums de discussion comme IRC, où de nombreuses conversations sont sommaires et absurdes. Troisièmement, de nombreux utilisateurs d'IRC utilisent l'anglais comme deuxième ou troisième langue, et la réponse absurde du programme est susceptible d'être attribuée à la barrière de la langue. Quatrièmement, de nombreux utilisateurs ne savent rien d'Elise et des programmes similaires et ne peuvent pas reconnaître les erreurs complètement inhumaines que commettent ces programmes.
Chaque année, il y a un concours entre les programmes parlants, et le plus humain, selon les juges, reçoit le prix Loebner. Il y a un prix supplémentaire pour un programme qui, selon les juges, réussira le test de Turing. Ce prix n'a pas encore été décerné.
Le meilleur résultat au test de Turing a été montré par le programme A.L.I.C.E. ayant remporté le test 3 fois (en 2000, 2001 et 2004).
Liens
- Turing A. M. Machines informatiques et esprit. // Dans : Hofstader D., Dennett D. L'œil de l'esprit. - Samara : Bahrakh-M, 2003. - S. 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 de la Stanford Encyclopedia of Philosophy (en anglais)
- "Turing Test: 50 Years Later" une revue de 50 ans de travail sur le test de Turing, du point de vue de 2000 (en anglais).
Revenons à la machine de Turing. Dans un extrait d'un article sur Alan Turing, il est indiqué que pour la première fois le concept d'une machine de Turing a été proposé dans le cadre de la soi-disant. 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, peut être calculée par une machine de Turing.
Alan Turing a suggéré (connu sous le nom de thèse de Church-Turing) que tout algorithme au sens intuitif du terme peut être représenté par une machine de Turing équivalente. Le raffinement du concept de calculabilité basé sur le concept de machine de Turing (et d'autres concepts équivalents) a ouvert des possibilités de preuve rigoureuse de l'insolvabilité algorithmique de divers problèmes de masse (c'est-à-dire des problèmes de recherche d'une méthode unifiée pour résoudre un certain classe de problèmes dont les conditions peuvent varier dans certaines limites). L'exemple le plus simple d'un problème de masse algorithmiquement indécidable est le soi-disant problème d'applicabilité de l'algorithme (également appelé problème d'arrêt). Elle consiste en ceci : il s'agit de trouver une méthode générale qui permettrait, pour une machine de Turing arbitraire (donnée par son programme) et un état initial arbitraire de la bande de cette machine, de déterminer si le fonctionnement de la machine se terminer par un nombre fini d'étapes ou si elle se poursuivra indéfiniment.
Dans un article intitulé "The Church-Turing Thesis", ils écrivent à son sujet comme ceci :
Thèse de Church-Turing
Thèse de 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 déclare que toute fonction intuitivement calculable est partiellement calculable, ou de manière équivalente, peut être calculée par une machine de Turing.
La thèse de Church-Turing ne peut être rigoureusement prouvée ou réfutée, puisqu'elle établit une « égalité » entre la notion strictement formalisée d'une fonction partiellement calculable et la notion informelle d'une « fonction intuitivement calculable ».
Thèse physique de Church-Turing lit: Toute fonction qui peut être calculée par un appareil physique peut être calculée par une machine de Turing.
A partir de ce carrefour, on peut s'orienter vers, par exemple, la théorie de la calculabilité. Ou vous pouvez essayer de découvrir qui est cette mystérieuse Église, avec qui 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 le programme et les données d'entrée en entrée, il calcule la réponse que la machine de Turing, dont le programme a été donné en entrée, calculerait à partir des données d'entrée.
Définition formelle
Le programme de n'importe quelle 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 machine par Σ 1 (\displaystyle\Sigma _(1)). Puis la machine de Turing universelle tu pour une classe de machines avec un alphabet Σ 2 (\displaystyle \Sigma _(2)) et k bandes d'entrée s'appelle une machine de Turing avec k+1 bande d'entrée et alphabet Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\cup \Sigma _(2)) de sorte que si vous postulez pour la première k valeur d'entrée des bandes, et sur k+1 est le code correctement écrit d'une machine de Turing, alors tu donnera la même réponse qu'il donnerait sur ces entrées M 1 (\displaystyle M_(1)), ou s'exécutera indéfiniment si M 1 (\displaystyle M_(1)) ne vous arrêtez pas à ces données.
Le théorème universel de la machine de Turing stipule qu'une telle machine existe et modélise d'autres machines avec au plus une décélération quadratique (c'est-à-dire si la machine d'origine a produit tétapes, alors l'universel produira au plus ct2). La preuve de ce théorème est constructive (une telle machine est facile à construire, il suffit de bien la décrire). Le théorème a été proposé et prouvé par Turing en 1936-37.
L'implémentation logicielle dans le langage de programmation Delphi est assez simple. L'une de ces implémentations peut être trouvée sur http://kleron.ucoz.ru/load/24-1-0-52 . Il est possible de charger et d'enregistrer 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 valeurs sur la bande, la machine peut effectuer une parmi plusieurs (on peut considérer, sans perte de généralité - deux) transitions possibles, et le choix est fait de manière probabiliste (lancer une pièce).
Une machine de Turing probabiliste est similaire à une machine de Turing non déterministe, seulement au lieu d'une transition non déterministe, la machine choisit l'une des options avec une certaine probabilité.
Il existe également une autre définition :
Une machine de Turing probabiliste est une machine de Turing déterministe qui possède en outre une source matérielle de bits aléatoires, dont n'importe quel nombre, par exemple, elle peut « ordonner » et « charger » 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 la classe BPP.
En 1936, Alan Turing propose de clarifier le concept d'algorithme interprète universel abstrait. Son caractère abstrait réside dans le fait qu'il s'agit d'une construction informatique logique et non d'un véritable ordinateur. Le terme "interprète universel" signifie que cet interprète peut imiter n'importe quel autre interprète. Par exemple, les opérations effectuées par de vrais ordinateurs peuvent être simulées sur un exécuteur universel. En conséquence, la construction informatique inventée par Turing s'appelait Machine de Turing.
De plus, on suppose qu'un exécuteur universel doit être capable de prouver l'existence ou l'absence d'un algorithme pour une tâche particulière.
Qu'est-ce qu'une machine de Turing ?
La machine de Turing se compose d'une bande infinie dans les deux sens, divisée en cellules, et d'un automate (tête) contrôlé par le programme.
Les programmes pour les machines de Turing sont écrits sous la forme d'un tableau, où la première colonne et la première ligne contiennent les lettres de l'alphabet externe et les états internes possibles de l'automate (alphabet interne). Le contenu du tableau sont des instructions pour la machine de Turing. La lettre que la tête lit dans la cellule (sur laquelle elle se trouve actuellement) et l'état interne de la tête déterminent l'instruction à exécuter. La commande est déterminée par l'intersection des caractères des alphabets externes et internes dans le tableau.
Pour spécifier une machine de Turing spécifique, il est nécessaire de décrire les composants suivants :
- alphabet externe. Un ensemble fini (par exemple, A), dont les éléments sont appelés lettres (symboles). Une des lettres de cet alphabet (par exemple, un 0) doit être un caractère vide.
- alphabet interne. Ensemble fini d'états de la tête (automate). L'un des états (par exemple, q 1) doit être initial (lancement du programme). Un autre des états (q 0) doit être final (fin du programme) - l'état d'arrêt.
- Tableau de saut. Description du comportement de l'automate (tête) en fonction de l'état et du caractère lu.
L'automate d'une machine de Turing au cours de son travail peut effectuer les actions suivantes :
- Écrivez un caractère de l'alphabet externe dans une cellule (y compris une cellule vide), en remplaçant celui qui s'y trouve (y compris une cellule vide).
- Déplacer une cellule vers la gauche ou vers la droite.
- Changez votre état intérieur.
Une commande pour une machine de Turing est juste une combinaison spécifique de ces trois composants : des instructions pour savoir quel caractère écrire dans la cellule (au-dessus de laquelle se trouve la machine), où se déplacer et dans quel état aller. Bien que la commande ne contienne pas tous les composants (par exemple, ne modifiez pas le symbole, ne bougez pas ou ne modifiez pas l'état interne).
Exemple de machine de Turing
Supposons qu'il y ait un mot sur la bande composé des caractères #, $, 1 et 0. Vous souhaitez remplacer tous les caractères # et $ par des zéros. Au moment du lancement, la tête est située au-dessus de la première lettre du mot à gauche. Le programme se termine lorsque la tête est sur le caractère vide après la lettre la plus à droite du mot.
Noter: la longueur du mot et la séquence de caractères n'ont pas d'importance. La figure montre un exemple de la séquence d'exécution des commandes pour un cas particulier. S'il y a un mot différent sur la bande, la séquence de commandes sera différente. Malgré cela, ce programme pour la machine de Turing (sur la figure - le tableau de gauche) est applicable à tous les mots de l'alphabet externe décrit (la propriété d'applicabilité de l'algorithme à toutes les tâches du même type est observée - caractère de masse ).
Vous pouvez compliquer le programme. Supposons que la tête ne soit pas nécessairement située au-dessus du premier, mais au-dessus de n'importe quel caractère du mot. Alors le programme pour une machine de Turing donnée pourrait ressembler à ceci (ou il pourrait être différent) :
Ici, la tête est décalée vers la gauche jusqu'à ce qu'elle soit au-dessus du caractère vide. Après cela, la machine entre dans l'état q 2 (dont les commandes sont les mêmes que les commandes q 1 du programme précédent).
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 tout simplement pas s'empêcher de dire aux gens ce qu'est un algorithme. Il a donc inventé une machine abstraite, qui porte son nom. Je veux dire, nom de famille. Mais faisons les choses correctement...
L'essentiel en mots simples
Un point important doit être immédiatement identifié : la machine de Turing est un dispositif exclusivement spéculatif. Rien de tel n'existe dans la nature. Des modèles informatiques existent. 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 l'existence physique à part entière à 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, telles que des caractères alphabétiques. Eh bien, ou des zéros et des uns. En général, quelque chose qui convient au traitement automatique. Ceci est fait par la partie mobile de la machine.
Comment ça fonctionne
La partie mobile est le lecteur et l'écrivain. Une sorte de chose qui peut lire le contenu des cellules, y écrire quelque chose qui lui est propre et, surtout, agir en fonction des résultats obtenus.
De plus, l'automate ne peut déplacer qu'une cellule à la fois. Droite, gauche, si nécessaire pour effectuer des calculs. J'ai ajouté quelque chose ici - vous devez vous déplacer pour emporter quelque chose. Et puis pliez à nouveau. Et ainsi de suite aussi longtemps que vous le souhaitez, jusqu'à ce que la tâche soit terminée. Après tout, la bande est sans fin, il y a suffisamment d'options pour toute opération.
En fait, Alan Turing essayait simplement de souligner que chaque calcul, aussi complexe soit-il, peut être effectué par étapes, étape par étape, en divisant la tâche en composants élémentaires. C'est l'essence de l'algorithme.
Différentes variantes
Le novice en cybernétique a regardé la machine de Turing et a compris qu'il n'y avait rien à redire. En effet, les programmes informatiques doivent être construits sur la base d'algorithmes - l'exécution pas à pas d'instructions.
Dans le même temps, la gloire d'Alan Turing n'a pas donné de repos à beaucoup, et les adeptes ont commencé, comme on dit, à capter ses réflexions. Ils ont commencé à inventer des machines de Turing multidimensionnelles, avec de nombreuses bandes, "semi-infinies" etc.
Nous essaierons d'apporter au moins un peu de clarté dans ce chaos et d'envisager de réelles options pour l'appareil en discussion.
- non déterministe- il s'agit d'une machine de Turing qui agit sur la bande avec les cellules décrites ci-dessus en fonction de la situation qui se présente à un stade particulier des calculs. Où qu'elle veuille, elle s'y installera, en d'autres termes.
- déterministe un avec des instructions spécifiques. Par exemple, si la cellule où se trouve l'automate d'exécution contient la lettre A, alors vous devez passer à la suivante, avec la lettre B, que vous le vouliez ou non.
- Compléter- capable de calculer en général tout ce qui peut être calculé par des opérations pas à pas. Il peut même simuler une machine dans une machine, un émulateur qui décrit le fonctionnement d'un autre appareil similaire avec des algorithmes.
- Universel- capable de tout ce que n'importe quelle machine de Turing peut faire. En général, aucun, même pas encore inventé. Bien sûr, il est complet.
Avantages pratiques
Bien sûr, un algorithme est un concept plus complexe que le simple fait de déplacer l'exécution à travers des étapes dans un espace unidimensionnel. Après tout, brancher, boucler, revenir en arrière, 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 de simulation de machine de Turing conçus pour enseigner aux étudiants. Les programmeurs novices sont encouragés à développer différents algorithmes, par exemple, rechercher, modifier, ajouter, réorganiser les lettres dans les cellules.
Par conséquent, les avantages de la machine de Turing sont exactement ce que son créateur, le prophète de l'ère informatique, voulait : une démonstration claire de l'essence du calcul algorithmique.
Parutions précédentes :
Dernière édition : 2013-04-01 10:58:05
Balises de matériaux : ,
Une machine de Turing est une collection des objets suivants
- 1) alphabet externe A=(a 0 , a 1 , …, a n );
- 2) alphabet interne Q=(q 1 , q 2 ,…, q m ) - ensemble d'états ;
- 3) ensemble de caractères de contrôle (P, L, S)
- 4) une bande sans fin dans les deux sens, divisée en cellules, dans chacune desquelles un seul caractère de l'alphabet A peut être écrit à tout moment discret ;
- 5) un dispositif de contrôle capable d'être dans l'un des nombreux états
Le symbole d'une cellule vide est la lettre de l'alphabet externe, un 0 .
Parmi les états, on distingue le q 1 initial, dans lequel la machine commence à fonctionner, et l'état final (ou d'arrêt) q 0, une fois dans lequel la machine s'arrête.
Le dispositif de commande peut se déplacer de gauche à droite sur la bande, lire et écrire dans les cellules de la bande des lettres de l'alphabet A. Le dispositif de commande fonctionne selon des commandes qui ont la forme suivante
q je une j > une p X q k
L'entrée signifie ce qui suit : si le dispositif de contrôle est à l'état qi et que la lettre aj est écrite dans la cellule visualisée, alors (1) ap est écrit dans la cellule au lieu de aj , (2) la machine procède à la visualisation la cellule de droite suivante à partir de celle qui vient d'être visualisée, si X=P, ou pour visualiser la cellule de gauche suivante, si X=L, ou continuer à visualiser la même cellule de bande, si X=C, (3) le dispositif de contrôle entre dans l'état q k.
Comme le fonctionnement de la machine, par condition, est entièrement déterminé par son état q, à un instant donné, et par le contenu a de la cellule visualisée à cet instant, il existe exactement une règle pour chaque configuration possible q i a j. Il n'y a pas de règles uniquement pour l'état final, dans lequel la machine s'arrête. Par conséquent, le programme de la machine de Turing avec l'alphabet extérieur A=(a0, a1, …, an) et l'alphabet intérieur Q=(q1, q2,…, qm) ne contient pas plus de m (n+ 1) instructions.
Un mot de l'alphabet A ou de l'alphabet Q ou de l'alphabet A Q est une séquence quelconque de lettres de l'alphabet correspondant. Sous la k-ième configuration, on entend l'image de la bande de la machine avec les informations qui s'y sont développées au début de la k-ième étape (ou le mot de l'alphabet A écrit sur la bande au début de la k-ième étape), indiquant quelle cellule est visualisée à cette étape Et dans quel état est la voiture ? Seules les configurations finies ont un sens, c'est-à-dire ceux dans lesquels toutes les cellules de la bande, à l'exception possible d'un nombre fini, sont vides. Une configuration est dite finale si l'état dans lequel se trouve la machine est final.
Si l'on choisit une configuration non finale de la machine de Turing comme configuration initiale, le travail de la machine consiste à transformer séquentiellement (pas à pas) la configuration initiale en fonction du programme de la machine jusqu'à ce que la configuration finale soit atteinte. Après cela, le travail de la machine de Turing est considéré comme terminé et le résultat du travail est la configuration finale atteinte.
On dira qu'un mot non vide b de l'alphabet A (à 0 ) = (a 1 , ..., an ) est perçu par la machine dans une position standard s'il est écrit dans des cellules successives de la bande, toutes les autres cellules sont vides et la machine balaye la cellule a la plus à gauche ou la plus à droite parmi celles dans lesquelles le mot b est écrit. La position standard est dite initiale (finale) si la machine qui perçoit le mot en position standard est dans l'état initial q 1 (respectivement, dans l'état d'arrêt q 0).
Si le traitement du mot b amène la machine de Turing à son état final, alors on dit qu'il s'applique à b, sinon il ne s'applique pas à b (la machine tourne indéfiniment)
Prenons un exemple :
Soit une machine de Turing avec un alphabet externe A \u003d (0, 1) (ici 0 est le symbole d'une cellule vide), un alphabet d'états internes Q \u003d (q 0, q 1, q 2 ) et avec les éléments suivants schéma fonctionnel (programme):
q 1 0 > 1 L q 2 ;
q 1 1 > 0 С q 2 ;
q 2 0 > 0 Ï q 0 ;
q 2 1 > 1 C q 1;
Ce programme peut être écrit à l'aide du tableau
A la première étape, la commande opère : q 1 0 > 1 Ë q 2 (le dispositif de contrôle est à l'état q1, et la lettre 0 est écrite dans la cellule surveillée, 1 est écrit dans la cellule au lieu de 0, la tête est décalé vers la gauche, l'organe de commande passe à l'état q2), en conséquence, la configuration suivante est créée sur la machine :
Enfin, après avoir exécuté la commande q 2 0 > 0 P q 0, une configuration est créée
Cette configuration est définitive car la machine est dans un état d'arrêt q 0 .
Ainsi, le mot original 110 est transformé par la machine en mot 101.
La séquence de configurations résultante peut être écrite de manière plus courte (le contenu de la cellule surveillée est écrit à droite de l'état dans lequel se trouve actuellement la machine) :
11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1
La machine de Turing n'est rien de plus qu'une règle (algorithme) pour convertir les mots de l'alphabet A Q, c'est-à-dire configurations. Ainsi, pour définir une machine de Turing, il faut spécifier ses alphabets externe et interne, le programme, et indiquer lequel des symboles dénote une cellule vide et l'état final.
transcription
1 Université d'État Lomonossov de Moscou M.V. Faculté Lomonossov de mathématiques computationnelles et de cybernétique V.N. Pilshchikov, V.G. Abramov, A.A. Vylitok, I.V. Machine de Turing chaude et algorithmes de Markov. Résolution de problèmes (Manuel pédagogique) Moscou, 2006
2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. Machine de Turing et algorithmes de Markov. Résolution de problème. (Manuel pédagogique) - M.: Université d'État de Moscou, p. Le Département d'édition de la Faculté de CMC MSU (licence LR de) Le manuel est consacré à la résolution de problèmes sur le thème "Introduction à la théorie des algorithmes", étudié en première année de la Faculté de CMC MSU au sein de la discipline "Algorithmes et langages algorithmiques ». Il s'agit de tâches de compilation d'algorithmes sous forme de machine de Turing et d'algorithmes de Markov normaux, ainsi que de tâches de nature théorique. Le manuel fournit les informations nécessaires sur la théorie des algorithmes, explique en détail les techniques typiques de résolution de problèmes et propose un large éventail de problèmes pour une solution indépendante. Le manuel est conçu pour les étudiants de première année de la faculté du CMC de l'Université d'État de Moscou et les enseignants qui animent des séminaires sur la programmation. Évaluateurs : professeur agrégé Baula V.G. Professeur agrégé Korukhova L.S. Publié par décision du Conseil de rédaction et de publication de la Faculté de mathématiques computationnelles et de cybernétique de l'Université d'État de Moscou. M.V. Lomonosov. ISBN ??? Département d'édition de la Faculté de mathématiques computationnelles et de cybernétique, Université d'État Lomonossov de Moscou M.V. Lomonosov,
3 1. Machine de Turing Cette section traite des problèmes de compilation d'algorithmes pour une machine de Turing. Une brève description de cette machine est donnée, les principales méthodes de compilation de tels algorithmes sont expliquées avec des exemples, et des problèmes pour une solution indépendante sont proposés. 1.1 Brève description de la machine de Turing Structure de la machine de Turing La machine de Turing (MT) se compose de deux parties d'une bande et d'un automate (voir à gauche) : bande : abb Λ Λ abb Λ Λ automate : qq La bande sert à stocker information. Il est infini dans les deux sens et est divisé en cellules qui ne sont ni numérotées ni nommées d'aucune façon. Chaque cellule peut contenir un caractère ou rien. Le contenu de la cellule peut y changer, vous pouvez écrire un autre caractère ou effacer le caractère qui s'y trouve. Convenons d'appeler le contenu vide de la cellule le symbole "vide" et notons le signe Λ ("lambda"). Par conséquent, l'image de la bande illustrée sur la figure de droite est la même que celle illustrée sur la figure de gauche. Cette convention est pratique en ce que l'opération de suppression d'un caractère dans une certaine cellule peut être considérée comme l'écriture du caractère Λ dans cette cellule, donc au lieu de la longue phrase "écrire un caractère dans une cellule ou effacer un caractère qui s'y trouve", vous peut simplement dire "écrire un caractère dans une cellule". La machine est la partie active du MT. A chaque instant, il se place sous l'une des cellules de la bande et voit son contenu ; il s'agit d'une cellule visible et le symbole qu'elle contient est un symbole visible ; le contenu des cellules voisines et autres n'est pas visible par la machine. De plus, à chaque instant l'automate est dans l'un des états, qui sera désigné par la lettre q avec des chiffres : q1, q2, etc. Étant dans un certain état, l'automate effectue une opération spécifique (par exemple, il se déplace vers la droite le long de la bande, remplaçant tous les caractères b par a), tout en étant dans un autre état, une autre opération. Une paire d'un symbole visible (S) et de l'état courant de l'automate (q) sera appelée une configuration et notée
4 Cycle de la machine de Turing Le MT fonctionne par cycles qui s'exécutent les uns après les autres. A chaque cycle, l'automate MT effectue les trois actions suivantes, et nécessairement dans l'ordre indiqué : 1) écrit un symbole S dans une cellule visible (en particulier, le même symbole peut être écrit tel qu'il y était, puis le contenu de cette cellule ne change pas); 2) se déplace d'une cellule vers la gauche (notation L, de gauche), ou d'une cellule vers la droite (notation R, de droite), ou reste immobile (notation N). 3) passe dans un état q (en particulier, il peut rester dans le même état). Formellement, les actions d'une mesure s'écriront sous la forme d'un triplet : S, , q où la construction entre crochets signifie la possibilité d'écrire à cet endroit n'importe laquelle des lettres L, R ou N. décalage d'une cellule vers la gauche et transition énoncer q8. Le programme de la machine de Turing Par lui-même, le MT ne fait rien. Pour le faire fonctionner, vous devez écrire un programme pour cela. Ce programme est écrit sous la forme du tableau suivant : q 1 qjqm S 1 S 2 S i S n Λ S, , q A gauche, tous les états dans lesquels l'automate peut se trouver sont listés, en haut tous les symboles (y compris Λ) que l'automate peut voir sur la bande. (Les symboles et les états à indiquer dans le tableau sont déterminés par l'auteur du programme.) Aux intersections (dans les cellules du tableau), ces cycles sont indiqués que l'automate doit effectuer lorsqu'il est dans l'état approprié et voit le symbole correspondant sur la bande. En général, le tableau détermine les actions du MT pour toutes les configurations possibles et fixe ainsi complètement le comportement du MT. Décrire un algorithme sous forme de MT revient à présenter un tel tableau. (Remarque. Souvent, un MT est défini comme composé d'une bande, d'un automate et d'un programme, donc différents programmes produisent différents MT. Nous supposerons, dans l'esprit des ordinateurs modernes, qu'il n'y a qu'un seul MT, mais il peut exécuter différents programmes.) 4
5 Règles d'exécution du programme Avant d'exécuter le programme, les étapes préliminaires suivantes doivent être suivies. Tout d'abord, le mot d'entrée auquel le programme sera appliqué doit être écrit sur la bande. Le mot d'entrée est la séquence finale de caractères écrits dans des cellules adjacentes de la bande ; il ne doit pas y avoir de cellules vides à l'intérieur du mot d'entrée, et seules les cellules vides doivent se trouver à gauche et à droite de celui-ci. Un mot d'entrée vide signifie que toutes les cellules de la bande sont vides. Dans un second temps, il faut mettre l'automate dans l'état q 1 (indiqué en premier dans le tableau) et le placer sous le premier symbole du mot d'entrée : abbq 1 Si le mot d'entrée est vide, alors l'automate peut regarder n'importe quelle cellule , car ils sont tous vides. Après ces étapes préliminaires, l'exécution du programme commence. Une cellule se trouve dans le tableau à l'intersection de la première ligne (car l'automate est dans l'état q 1) et de la colonne qui correspond au premier caractère du mot d'entrée (ce n'est pas forcément la colonne de gauche du tableau), et le cycle indiqué dans cette cellule est exécuté. De ce fait, la machine sera dans une nouvelle configuration. Maintenant, les mêmes actions sont répétées, mais pour une nouvelle configuration : une cellule est trouvée dans le tableau qui correspond à l'état et au symbole de cette configuration, et un cycle est effectué à partir de cette cellule. Etc. Quand le programme se termine-t-il ? Introduisons le concept de cycle d'arrêt. C'est un cycle qui ne change rien : l'automate écrit dans la cellule visible le même symbole qu'avant, ne bouge pas et reste dans le même état, c'est-à-dire c'est le cycle S,N,q pour la configuration
6 2) Le deuxième résultat est "mauvais": c'est lorsque le MT boucle, n'arrivant jamais au cycle d'arrêt (par exemple, l'automate se déplace vers la droite à chaque pas et ne peut donc pas s'arrêter, car la bande est sans fin). Dans ce cas, le MT est dit inapplicable au mot d'entrée donné. Il ne peut être question d'aucun résultat avec un tel résultat. Notez que le même algorithme (programme MT) peut être applicable à certains mots d'entrée (c'est-à-dire stop) et inapplicable à d'autres (c'est-à-dire boucle). Ainsi, l'applicabilité/inapplicabilité dépend non seulement de l'algorithme lui-même, mais également du mot d'entrée. À quels mots d'entrée l'algorithme doit-il s'arrêter ? Sur, pour ainsi dire, les bons mots, c'est-à-dire sur ceux qui se réfèrent aux données initiales admissibles du problème à résoudre, pour lesquelles le problème est significatif. Mais tous les mots d'entrée peuvent être enregistrés sur la bande, y compris ceux pour lesquels la tâche n'a pas de sens ; sur de tels mots, le comportement de l'algorithme n'est pas fixe, il peut s'arrêter (pour n'importe quel résultat), ou il peut aller par cycles. Conventions pour raccourcir l'enregistrement Mettons-nous d'accord sur quelques conventions qui raccourcissent l'enregistrement du programme pour MT. 1) Si un symbole visible ne change pas dans une mesure, ou que l'automate ne bouge pas, ou que l'état de l'automate ne change pas, alors on n'écrira rien à la position correspondante de la mesure. Par exemple, lors de la configuration
7 1.2 Exemples de programmation MT Regardons des exemples de programmation MT pour démontrer quelques techniques de programmation MT typiques. Pour abréger la formulation des problèmes, nous introduisons les deux conventions suivantes : nous désignerons le mot d'entrée par la lettre P ; la lettre A désignera l'alphabet du mot d'entrée, c'est-à-dire l'ensemble des symboles dont et seulement lesquels P peut être constitué (notez, cependant, que d'autres symboles peuvent apparaître dans les mots intermédiaires et de sortie). Exemple 1 (déplacement de l'automate, remplacement de caractères) A=(0,1,2,3,4,5,6,7,8,9). Soit P un mot non vide ; donc P est une séquence de chiffres décimaux, c'est-à-dire notation d'un entier non négatif dans le système décimal. Il est nécessaire d'obtenir sur la bande un enregistrement d'un nombre supérieur de 1 au nombre P. Solution. Pour résoudre ce problème, il est proposé d'effectuer les actions suivantes : 1. Déplacer la machine jusqu'au dernier chiffre du numéro. 2. S'il s'agit d'un nombre compris entre 0 et 8, remplacez-le par un nombre 1 de plus et arrêtez ; par exemple : S'il s'agit du chiffre 9, alors remplacez-le par 0 et déplacez l'automate au chiffre précédent, puis augmentez cet avant-dernier chiffre de 1 de la même façon ; Ex. : Cas particulier : P n'a que des neufs (ex. 99). Ensuite, l'automate se déplacera vers la gauche, remplaçant les neuf par des zéros, et à la fin il se trouvera sous une cellule vide. Écrivez 1 dans cette cellule vide et arrêtez-vous (la réponse sera 100) : Sous la forme d'un programme pour MT, ces actions sont décrites comme suit : Λ q1 0,R,q1 1,R,q1 2,R,q1 3 ,R,q1 4, R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2, N ! 3, N ! 4, N ! 5, N ! 6, N ! 7, N ! 8, N ! 9, N ! 0,L,q2 1,N,! Explications. q1 est l'état dans lequel l'automate "fonctionne" sous le dernier chiffre du nombre. Pour ce faire, il se déplace constamment vers la droite, sans changer les chiffres visibles et en restant dans le même état. Mais il y a une caractéristique ici : lorsque la machine a moins de 7 ans
8 est le dernier chiffre, alors il ne le sait toujours pas (après tout, il ne voit pas ce qui est écrit dans les cellules voisines) et ne le déterminera que lorsqu'il arrivera dans une cellule vide. Par conséquent, ayant atteint la première cellule vide, l'automate revient sous le dernier chiffre et passe à l'état q2 (il n'est plus nécessaire de se déplacer vers la droite). q2 est l'état dans lequel l'automate ajoute 1 au chiffre qu'il voit en ce moment. C'est d'abord le dernier chiffre du nombre; s'il est compris entre 0 et 8, la machine le remplace par un chiffre supérieur à 1 et s'arrête. Mais s'il s'agit du nombre 9, alors l'automate le remplace par 0 et se décale vers la gauche, restant dans l'état q2. Ainsi, il va maintenant ajouter 1 au chiffre précédent. Si ce chiffre est également égal à 9, alors l'automate le remplace par 0 et se décale vers la gauche, restant dans l'état q2 comme précédemment, puisque doit effectuer la même augmentation d'action d'un chiffre visible. Si l'automate s'est déplacé vers la gauche et qu'il n'y a pas de numéro dans la cellule visible (mais qu'il y a "vide"), alors il écrit 1 ici et s'arrête. Notez que pour un mot d'entrée vide, notre problème n'est pas défini, donc, sur ce mot, le MT peut se comporter de n'importe quelle manière. Dans notre programme, par exemple, avec un mot d'entrée vide, le MT s'arrête et donne la réponse 1. Ci-dessus, nous avons donné le programme sous une forme complète et non abrégée. Écrivons maintenant le programme sous une forme abrégée, plus visuelle, tandis qu'à droite nous donnons une brève explication des actions qui sont mises en œuvre dans les états correspondants de l'automate : Λ q1,r,r,r,r,r,r ,r,r,r,r, l,q2 sous le dernier chiffre de q2 1,! 2 ! 3 ! 4, ! 5, ! 6 ! sept! huit,! 9, ! 0,L, 1,! nombre visible + 1 C'est ainsi que nous écrirons les programmes à l'avenir. Exemple 2 (analyse des caractères) A=(a,b,c). Déplace le premier caractère d'un mot non vide P à sa fin. Par exemple : a b c b b c b a Solution. Pour résoudre ce problème, il est proposé d'effectuer les actions suivantes : 1. Mémoriser le premier caractère du mot P, puis effacer ce caractère. 2. Déplacez l'automate vers la droite sous la première cellule vide après P et écrivez-y le symbole mémorisé. Comment "courir" vers la droite, nous le savons déjà grâce à l'exemple précédent. Mais comment retenir le premier caractère ? En effet, en MT il n'y a pas d'autre dispositif de stockage que la bande, et il est inutile de mémoriser un symbole dans une cellule de la bande : dès que l'automate se déplace à gauche ou à droite de cette cellule, il oublie immédiatement ce symbole . Que faire? La solution consiste à utiliser différents états de l'automate. Si le premier caractère est un, alors vous devez passer à l'état q2, dans lequel l'automate 8
9 court vers la droite et écrit un à la fin. Si le symbole b était le premier, alors il faut passer à l'état q3, où tout se fait pareil, seul le symbole b est écrit à la fin. Si le premier symbole était c, alors on passe à l'état q4, dans lequel l'automate ajoute le symbole c après le mot d'entrée. Par conséquent, nous fixons ce qu'était le premier symbole en transférant l'automate dans différents états. Il s'agit d'une technique de programmation MT typique. Au vu de ce qui précède, le programme sera le suivant : abc Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, analyse du 1er caractère, suppression de celui-ci, branchement q2,r,r ,r, un, ! enregistrer a à droite q3,r,r,r, b,! enregistrer b à droite q4,r,r,r, c,! écrivez c à droite Considérez le comportement de ce programme sur des mots d'entrée contenant au plus un caractère. Avec un mot vide, qui est "mauvais" pour la tâche, le programme bouclera l'automate, étant dans l'état q1 et tombant tout le temps sur des cellules vides, il se déplacera indéfiniment vers la droite. (Bien sûr, dans ce cas, le programme pourrait être arrêté, mais nous avons spécifiquement fait une boucle pour démontrer cette possibilité.) S'il y a exactement un caractère dans le mot d'entrée, alors l'automate effacera ce caractère, déplacera une cellule vers le à droite et écrivez-y ce caractère : cc q1 q4 ! Ainsi, un mot d'un caractère se déplacera simplement d'une cellule vers la droite. C'est acceptable. Après tout, les cellules de la bande ne sont pas numérotées, de sorte que l'emplacement du mot sur la bande n'est en aucun cas fixé et que le mouvement du mot vers la gauche ou la droite ne peut pas être remarqué. A cet égard, il n'est pas nécessaire que le mot de sortie soit au même endroit où se trouvait le mot d'entrée, le résultat pouvant être à la fois à gauche et à droite de cet endroit. Exemple 3 (comparaison de caractères, effacement de mots) A=(a,b,c). Si les premier et dernier symboles d'un mot (non vide) P sont identiques, alors ce mot n'est pas modifié, sinon il est remplacé par le mot vide. Solution. Pour résoudre ce problème, il est proposé d'effectuer les actions suivantes : 1. Mémoriser le premier caractère du mot d'entrée sans l'effacer. 2. Déplacez l'automate sous le dernier caractère et comparez-le avec celui mémorisé. S'ils sont égaux, ne faites rien d'autre. 3. Sinon, détruisez tout le mot d'entrée. Nous savons déjà comment mémoriser un caractère et comment dépasser la machine jusqu'au dernier caractère d'un mot des exemples précédents. L'effacement du mot d'entrée est mis en œuvre 9
10 en remplaçant tous ses symboles par le symbole Λ. En même temps, puisque l'automate est en fin de mot, on va déplacer l'automate de droite à gauche jusqu'à la première cellule vide. Ces actions sont décrites par le programme suivant pour MT (rappelons qu'une croix dans une cellule du tableau signifie que la configuration correspondante ne peut pas apparaître lors de l'exécution du programme) : a b c Λ q1,q2,q4,q6,! analyse du 1er caractère, branchement q2,r,r,r, L,q3 aller au dernier caractère au 1er caractère a q3,!, q8, q8 comparer en dernier. caractère avec a ne sont pas égaux sur q8 (effacer P) q4,r,r,r, L,q5 de même pour le 1er caractère b q5, q8,!, q8 q6,r,r,r, L,q7 de même pour le 1er caractère c q7, q8, q8,! q8 Λ,L, Λ,L, Λ,L,! effacer tout le mot en se déplaçant de droite à gauche Exemple 4 (effacer un caractère d'un mot) A=(a,b). Supprimez du mot P son deuxième caractère, le cas échéant. Solution. Il semblerait que ce problème soit facile à résoudre : il faut déplacer l'automate sous la cellule avec le deuxième symbole puis effacer cette cellule : a b b a a b b a a b a Cependant, rappelons qu'il ne doit pas y avoir de cellules vides à l'intérieur du mot de sortie. Par conséquent, après avoir supprimé le deuxième caractère, il est nécessaire de "compresser" le mot en déplaçant le premier caractère d'une cellule vers la droite. Pour ce faire, l'automate doit revenir au premier symbole, s'en souvenir et l'effacer, puis, en se déplaçant à nouveau vers la droite, l'écrire dans la cellule où se trouvait le deuxième symbole. Cependant, la «marche» initiale vers la droite jusqu'au deuxième symbole pour l'effacer, et le retour ultérieur au premier symbole sont des actions inutiles: quelle différence cela fait-il de transférer le premier symbole dans une cellule vide ou dans une cellule avec symbole? Par conséquent, nous retenons immédiatement le premier caractère, l'effaçons et le notons à la place du second caractère : abbabbaaba Sous forme de programme pour MT, tout cela s'écrit comme suit : ab Λ q1 Λ,R,q2 Λ,R, q3, ! analyse et suppression du 1er caractère, branchement q2, ! une! une! remplacement du 2ème caractère par un q3 b,!,! b! remplacement du 2ème caractère par b Exemple 5 (compression de mots) A=(a,b,c). Supprimez du mot P la première occurrence du caractère a, s'il y en a. Solution. Dans l'exemple précédent, nous avons déplacé un seul caractère vers la position à droite - 10
11 sem. Dans cet exemple, nous allons boucler vers la droite pour transférer tous les caractères initiaux b et c du mot d'entrée vers le premier caractère a ou vers une cellule vide : bcbcbaabbaabcaabcba ce symbole y pourrait-il être déplacé vers la cellule de droite ? Si qx désigne l'état dans lequel il est nécessaire d'écrire le symbole x, qui était auparavant dans la cellule de gauche, dans la cellule visible, alors cette action peut être représentée comme suit : d'abord, le symbole x extrait de la cellule sur la gauche est écrite dans la cellule visible ; deuxièmement, l'automate se déplace vers la droite sous la cellule, dans laquelle il faudra alors écrire le symbole y qui vient d'être remplacé ; dans un troisième temps, l'automate passe à l'état q y, dans lequel il va effectuer cet enregistrement. La répétition de telles mesures dans un cycle entraînera un décalage vers la droite d'une position des caractères initiaux du mot d'entrée. Ce cycle doit se terminer lorsque le caractère a ou Λ (y=a ou y=λ) apparaît dans la cellule suivante, et au début du cycle, on peut supposer que le caractère "vide" (x=λ) est transféré dans la place du premier caractère à gauche. Le résultat est le programme suivant pour MT : a b c Λ q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : efface le 1er caractère et le déplace vers la droite q2 b,!,r, b,r,q3 b,! q b : écrivez b, déplacez le caractère précédemment visible vers la droite q3 c,! c,r,q2,r, c, ! q c : écrivez c, déplacez le caractère précédemment visible vers la droite Dans ce programme, vous devez faire attention au cycle Λ,R,!
12 le premier caractère (vous ne pouvez pas encore le supprimer à l'ancien emplacement), puis, en revenant à l'ancien emplacement, écrivez le caractère a : bcabcabbcabaca Déplacer le caractère d'une position vers la gauche revient à déplacer le caractère vers la droite, comme discuté dans les deux exemples précédents, nous allons donc donner un programme pour MT sans commentaires supplémentaires. Notons seulement que dans les états q2, q3 et q4 l'automate ne peut voir qu'une cellule vide, et dans l'état q5 il voit nécessairement le premier symbole du mot d'entrée, mais pas une cellule vide. a b c Λ q1,l,q2,l,q3,l,q4,! analyser le 1er caractère pour le déplacer vers la gauche q2 a,r,q5 affecter a à gauche q3 b,r,q5 affecter b à gauche q4 c,r,q5 affecter c à gauche q5,! une! une! remplacer l'ancien 1er caractère par un Exemple 7 (propagation de mots) А=(a,b,c). Insérez le caractère a dans le mot P après la première occurrence du caractère c, le cas échéant. Solution. Nous parcourons le mot d'entrée de gauche à droite jusqu'à une cellule vide ou jusqu'au premier caractère c. Dans le premier cas, c n'est pas inclus dans P, donc on ne fait rien. Dans le second cas, vous devez faire de la place pour le caractère inséré a, pour lequel nous décalons le début du mot P (du premier caractère au caractère trouvé c) d'une position vers la gauche. Dans ce cas, on effectue un tel décalage de droite à gauche du symbole c au début du mot, puisque l'automate se situe sous ce symbole. De plus, afin de ne pas revenir plus tard à la position libérée, nous commençons ce décalage en écrivant a à la place du caractère trouvé c. Puisque ce décalage cyclique vers la gauche est mis en œuvre de manière similaire au décalage cyclique vers la droite de l'exemple 5, nous ne l'expliquerons pas, mais donnons immédiatement le programme pour MT : abc Λ q1,r,r, a,l,q4,l ,! droite vers c, insérer un a au lieu de c, déplacer c vers la gauche q2,l, a,l,q3 a,l,q4 a,! déplacer a vers la droite q3 b,l,q2,l, b,l,q4 b,! décalage à droite b q4 c,l,q2 c,l,q3,l, c,! transfert c vers la droite Exemple 8 (formation d'un mot à une nouvelle place) А=(a, b, c). Supprimez de P toutes les occurrences du caractère a. Solution. Les exemples précédents montrent que l'insertion de caractères dans des mots et la suppression de caractères dans des mots sont assez difficiles dans MT. Par conséquent, il est parfois plus facile de ne pas étendre ou compresser le mot d'entrée, mais de former le mot de sortie.
13 dans un autre endroit libre sur la bande. C'est exactement ce que nous allons faire pour résoudre ce problème. Plus précisément, il est proposé d'effectuer les actions suivantes : 1. On va construire le mot de sortie à droite du mot d'entrée. Pour délimiter ces mots, nous les séparons par un symbole auxiliaire, par exemple le signe =, différent de tous les symboles de l'alphabet A (voir étape 1). (Rappelez-vous que non seulement les caractères de l'alphabet du mot saisi peuvent être écrits sur la bande.) 2. Après cela, nous revenons au début du mot saisi (voir étape 2). a b c a b c = a b c = Maintenant, notre tâche consiste à transférer dans une boucle tous les caractères du mot d'entrée, à l'exception de a, à droite derrière le signe = dans le mot de sortie généré. Pour ce faire, nous analysons le premier caractère du mot d'entrée. Si c'est un, effacez-le et passez au caractère suivant (voir étape 3). Si le premier caractère est b ou c, alors nous l'effaçons et "courons" vers la droite jusqu'à la première cellule vide (voir étape 4), où nous écrivons ce caractère (voir étape 5). b c = c = c = b Nous revenons à gauche au caractère qui est devenu le premier dans le mot d'entrée et répétons les mêmes actions, mais par rapport à ce caractère (voir étapes 6-9). c = b = b = b c Cette boucle se termine lorsque nous revenons à gauche et voyons = comme premier caractère. C'est le signe que nous avons complètement scanné le mot d'entrée et transféré tous ses caractères autres que a au mot de sortie formé à droite. Il faut effacer ce signe, se déplacer vers la droite sous le mot de sortie et s'arrêter (voir étape 10). = b c b c 9 10 Compte tenu de tout ce qui a été dit, nous construisons un programme pour MT. Dans le même temps, nous notons qu'en plus des symboles a, b et c, le signe = apparaît sur la bande lors du processus de résolution du problème, de sorte que le tableau doit également avoir une colonne pour ce signe. abc = Λ q1,r,r,r, =,q2 écrire le signe = q2,l,l,l,l,r,q3 de droite au 1er symbole du mot q3 Λ,R, Λ,R, q4 Λ, R,q5 Λ,R,! analysez-le et supprimez-le, branchez q4,r,r,r,r, b,q2 écrivez b à droite, revenez à gauche (dans une boucle) q5,r,r,r,r, c,q2 écrivez c à droite, retour à gauche (en cycle) 13
14 Exemple 9 (fixation de l'endroit sur la bande) A=(a,b). Doublez le mot P en mettant un signe = entre lui et sa copie. Par exemple : a a b a a b = a a b Solution. Ce problème est résolu de la même manière que le précédent : on écrit le signe = à la fin du mot d'entrée, puis on revient au début du mot et on copie tous ses caractères (y compris un) dans la boucle vers les cellules vides à droite : aabaab = aab = aab = a 1 2 Cependant, il y a aussi une différence : les caractères copiés du mot d'entrée ne sont pas supprimés, ce qui conduit au problème suivant. Après avoir écrit une copie du caractère suivant à droite, il faut alors revenir au mot d'entrée à la position de ce caractère puis se déplacer vers la droite jusqu'au caractère suivant afin de le copier déjà. Mais comment savoir à quelle position du mot d'entrée revenir ? Par exemple, comment savons-nous dans notre exemple qu'après avoir copié le premier caractère a, nous devons revenir exactement au premier caractère du mot d'entrée, et non au deuxième ou au troisième ? Dans la tâche précédente, nous revenions toujours au premier des caractères restants du mot d'entrée, et maintenant nous enregistrons tous les caractères, il n'est donc pas clair quels caractères nous avons déjà copiés et lesquels ne l'ont pas encore été. Nous notons également qu'en MT les cellules de bande ne sont en aucun cas numérotées, il n'y a pas de compteurs en MT qui nous permettraient de déterminer combien de caractères nous avons déjà copiés. D'une manière générale, le problème auquel nous sommes confrontés est le suivant : comment fixer sur la bande une certaine position dans laquelle nous nous sommes déjà trouvés et sur laquelle nous devons revenir plus tard ? Habituellement, ce problème est résolu comme ceci. Lorsque nous nous trouvons dans cette position pour la première fois, nous remplaçons le caractère qu'il contient avec son double par un nouveau symbole auxiliaire, et nous remplaçons différents caractères par différents doubles, par exemple, a par A et b par B. Après cela, nous effectuons certaines actions à d'autres endroits sur la bande. Pour revenir ensuite à notre position, il suffit de trouver sur la bande la cellule où se trouve le symbole A ou B. Ensuite dans cette cellule vous pouvez restaurer le symbole précédent si nous n'avons plus besoin de fixer cette position (c'était pour restaurer le symbole précédent que nous avons dû remplacer différents symboles par différentes contreparties). Utilisons cette technique dans notre tâche, en effectuant les actions suivantes : 1. Comme déjà mentionné, nous écrivons d'abord le signe = derrière le mot d'entrée (voir l'étape 1 ci-dessus). 2. Ensuite, nous revenons sous le premier caractère du mot d'entrée (voir étape 2 ci-dessus). 3. Ensuite, nous remplaçons le symbole visible a par un double A (voir l'étape 3 ci-dessous), "courons" vers la droite jusqu'à la première cellule libre et y écrivons le symbole a (voir l'étape 4). Après cela, nous revenons à gauche à la cellule avec le double A (voir Fig. étape 5), restaurer le caractère précédent a et se déplacer vers la droite jusqu'au caractère suivant (voir étape 6). 14
15 aab = A ab = A ab = a A ab = aaab = aa A b = aa A b = aaaa B = aabaab = aab Copiez maintenant le deuxième caractère de la même manière (remplacez-le par A, ajoutez a à la fin, etc.) ) et tous les caractères suivants du mot d'entrée. 4. Lorsque nous copions le dernier caractère du mot d'entrée et revenons à son jumeau (après l'étape 12), puis après avoir décalé d'une position vers la droite, nous arriverons au signe = (étape 13). Il s'agit d'un signal indiquant que le mot d'entrée est complètement copié, de sorte que le travail du MT doit être terminé. Compte tenu de tout ce qui a été dit, on obtient pour MT le programme suivant : ab = AB Λ q1,r,r, =,L,q2 mettre = à droite du mot q2,l,l,r,q3 pour la gauche sous le 1er caractère q3 A,R, q4 B,R,q5,! analyse et remplacement du caractère suivant q4,r,r,r, a,q6 écrire a à droite q5,r,r,r, b,q6 écrire b à droite q6,l,l,l, a,r ,q3 b,r, q3 retour, restauration, au suivant. Notons que dans ce programme, on peut se débarrasser de l'état q6 en le combinant avec l'état q2, en prévoyant que q2 revienne vers la gauche à la fois sur la case vide et sur les symboles A et B : ab = AB Λ.. q2,l,l ,l, a,r,q3 b,r,q3,r,q3 laissés à Λ, A ou B Problèmes à solution indépendante Notes : 1) Seuls les entiers non négatifs sont considérés dans les problèmes, sauf si autrement dit. 2) Le système numérique "unique" est compris comme l'enregistrement d'un nombre entier non négatif à l'aide de bâtons ; autant de bâtons que la grandeur du nombre doit être écrit ; ex : 2, 5, 0<пустое слово>. 1.1 A=(a,b,c). Attribuez le symbole b (P bp) à gauche du mot P. 1.2 A=(a,b,c). Attribuez les symboles bc (P Pbc) à droite du mot P. 1.3 A=(a,b,c). Passez à un caractère toutes les secondes dans le mot P. 15
16 1.4 A=(a,b,c). Ne laissez que le premier caractère du mot P (ne modifiez pas le mot vide). 1.5A=(a,b,c). Ne laissez que le dernier caractère du mot P (ne modifiez pas le mot vide). 1.6 A=(a,b,c). Déterminer si P est un mot ab. Réponse (mot de sortie) : le mot ab si c'est le cas, ou le mot vide sinon. 1.7 A=(a,b,c). Déterminez si le mot P contient le caractère a. Réponse : un mot d'un caractère a (oui, inclus) ou un mot vide (non). 1.8 A=(a,b,c). Si le mot P n'inclut pas le symbole a, alors remplacez tous les symboles b dans P par c, sinon donnez le mot d'un symbole a comme réponse. 1.9 A=(a,b,0,1). Déterminez si le mot P est un identifiant (un mot non vide commençant par une lettre). Réponse : mot a (oui) ou mot vide (non) A=(a,b,0,1). Déterminez si le mot P est une représentation d'un nombre en notation binaire (un mot non vide composé uniquement des chiffres 0 et 1). Réponse : mot 1 (oui) ou mot A=(0,1). Considérant un mot non vide P comme une représentation d'un nombre binaire, enlevez les zéros non significatifs, s'il y en a A=(0,1). Pour un mot non vide P, déterminez s'il s'agit d'une représentation d'une puissance de deux (1, 2, 4, 8,) dans le système de numération binaire. Réponse : mot 1 (est) ou mot A=(0,1,2,3). Considérant un mot non vide P pour représenter un nombre dans le système de numération quaternaire, déterminez s'il s'agit d'un nombre pair ou non. Réponse : 1 (oui) ou A=(0,1). En considérant un mot non vide P comme représentation d'un nombre dans le système binaire, obtenir un nombre binaire égal à quatre fois le nombre P (par exemple : A=(0,1). Considérant un mot non vide P comme représentation d'un nombre dans le système binaire, obtenir un nombre binaire égal au quotient incomplet de la division du nombre P par 2 (par exemple :) A=(a,b,c). Si P est un mot de longueur paire (0, 2, 4,), alors retournez la réponse a, sinon le mot vide A=(0,1,2). Considérant un mot non vide P comme représentation d'un nombre dans le système numérique ternaire, déterminez s'il s'agit d'un nombre pair ou non. Réponse : 1 (oui) ou 0. (Remarque : un nombre ternaire pair doit avoir un nombre pair de chiffres 1.) 1.18 A=(a,b,c). Soit P de longueur impaire. Ne laissez que le symbole du milieu A=(a,b,c) dans P. Si le mot P a une longueur paire, ne laissez que la moitié gauche A=(a,b,c) dedans. Attribuez à gauche du mot non vide P son premier caractère. seize
17 1.21 A=(a,b). Pour un mot P non vide, déterminer si son premier caractère le ressaisit. Réponse : a (oui) ou le mot vide A=(a,b). Dans un mot non vide P, échanger ses premier et dernier symboles A=(a,b). Déterminez si P est un palindrome (changeling, mot symétrique) ou non. Réponse : a (oui) ou le mot vide A=(a,b). Remplacer dans P chaque occurrence de a par bb A=(a,b,c). Remplacez dans P chaque occurrence de ab par c A=(a,b). Doublez le mot P (par exemple : abb abbab) A=(a,b). Double chaque caractère du mot P (ex : bab bbaabb) A=(a,b). Retourner le mot P (par exemple : abb bba) A=(0,1). Considérant un mot non vide P comme un nombre binaire, obtenir le même nombre, mais dans le système quaternaire. (Remarque : tenez compte du fait qu'il peut y avoir un nombre impair de chiffres dans un nombre binaire.) 1,30 A=(0,1,2,3). Considérant un mot non vide P comme représentation d'un nombre dans le système numérique quaternaire, obtenir la représentation de ce nombre dans le système binaire A=(0,1,2). Considérant un mot non vide P comme un nombre positif en notation ternaire, diminuer ce nombre de A=( ). Considérant le mot P comme représentation d'un nombre dans le système des nombres unitaires, obtenez la représentation de ce nombre dans le système ternaire. (Recommandation : vous devez retirer un bâton du nombre « unique » dans un cycle et ajouter à chaque fois 1 au nombre ternaire, qui est d'abord fixé égal à 0.) 1,33 A=(0,1,2). Considérant un mot non vide P comme une représentation numérique dans le système numérique ternaire, obtenir une représentation de ce nombre dans le système d'unités. Soit le mot P avoir la forme suivante : (... (... nm où l'un des signes +, /, ou, à gauche desquels n bâtons sont indiqués et m bâtons à droite Mettre en œuvre l'opération correspondante dans le système de numérotation des unités (en réponse, donner le mot indiqué à droite de la flèche): a) addition : (... + (... (... (n 0, m 0) nm n+ mb) soustraction : (... (... (... (nm 0) nmnm c) multiplication : (... (... (... (n 0, m 0) nmnm d) division entière : ((... /... (... (n 0, m>0, k=n div m) nmk e) en prenant le reste : (... (... (... (n 0, m>0, k=n mod m) nmk 17
18 f) maximale : (... (... (... (n 0, m 0, k=max(n, m)) nmk g) minimale : (... (... (... (n 0, m 0, k=min(n,m)) knm 1,35 A=( ) En supposant que le mot P représente un nombre dans le système d'identité, déterminer si ce nombre est une puissance de 3 (1, 3, 9 , 27,) Réponse : un mot vide, si c'est le cas, ou un mot d'un bâton sinon A=( ). En considérant le mot P comme une représentation du nombre n dans le système d'identité, obtenir le nombre 2 n A=( ) dans le même système Soit le mot P une représentation du nombre 2 n (n=0, 1, 2,) dans le système d'identité Obtenir le nombre n dans le même système Soit P de la forme Q+R, où Q et R sont des mots non vides de symboles 0, 1 et 2. En traitant Q et R comme des nombres de notation dans le système de numération ternaire (éventuellement avec des zéros insignifiants), donnez comme réponse l'enregistrement de la somme de ces nombres dans le même système ternaire. comme un enregistrement de nombres dans le système de nombres ternaire (éventuellement avec des zéros insignifiants) et en supposant que QR, donner comme réponse l'enregistrement de la différence de ces nombres dans ce dans le même système ternaire Soit P de la forme Q=R, où Q et R sont des mots quelconques parmi les symboles a et b. Donner la réponse a si les mots Q et R sont identiques, et le mot vide sinon. Soit P de la forme Q=R, où Q et R sont des mots non vides de symboles 0 et 1. En traitant Q et R comme notations de nombres binaires (éventuellement avec des zéros non significatifs), répond mot 1 si ces nombres sont égaux, et mot 0 sinon Soit P de la forme Q>R, où Q et R sont des mots non vides de symboles 0 et 1 . zéros), donner comme réponse le mot 1 si le nombre Q est supérieur au nombre R, et le mot 0 sinon A=((,)). Déterminez si le mot P est équilibré par des parenthèses. Réponse : D (oui) ou N (non) A=(a,b). S'il y a plus de caractères a dans P que de caractères b, alors renvoie la réponse a, si les caractères a sont inférieurs aux caractères b, alors renvoie la réponse b, sinon renvoie le mot vide. 2. Algorithmes de Markov normaux Dans cette section, nous considérons le problème de l'écriture d'algorithmes de Markov normaux. Une brève description de ces algorithmes est donnée, les principales méthodes de leur compilation sont expliquées avec des exemples, et des problèmes pour une solution indépendante sont proposés. dix-huit
19 2.1 Brève description des algorithmes de substitution de Markov normaux Une caractéristique intéressante des algorithmes de Markov normaux (NAM) est qu'ils n'utilisent qu'une seule opération élémentaire, appelée substitution, qui est définie comme suit. Une formule de substitution est un enregistrement de la forme α β (il se lit « remplacer α par β »), où α et β sont des mots quelconques (éventuellement vides). Dans ce cas, α est appelé le côté gauche de la formule et β est appelé le côté droit. La substitution elle-même (en tant qu'action) est spécifiée par une formule de substitution et appliquée à un mot P. L'essence de l'opération est que dans le mot P la partie est trouvée qui correspond au côté gauche de cette formule (c'est-à-dire avec α) , et elle est remplacée par les formules du côté droit (c'est-à-dire sur β). Dans ce cas, les parties restantes du mot P (à gauche et à droite de α) ne changent pas. Le mot résultant R est appelé le résultat de la substitution. Classiquement, cela peut être représenté comme suit : P x α y R x β y Précisions nécessaires : 1. Si le côté gauche de la formule de substitution est inclus dans le mot P, alors on dit que cette formule est applicable à P. Mais si α n'est pas inclus dans P, alors la formule est considérée comme non applicable à P et aucune substitution n'est effectuée. 2. Si le côté gauche de α apparaît plusieurs fois dans P, alors par définition, seule la première occurrence de α dans P est remplacée par le côté droit de β : P x α y α z R x β y α z 3. Si le membre droit de la formule de substitution est un mot vide , alors la substitution α revient à supprimer la partie α de P (notons au passage qu'il n'est pas d'usage de noter le mot vide dans les formules de substitution) : P x α y R xy 4. Si le mot vide est indiqué à gauche de la formule de substitution, alors la substitution β revient, par définition, à attribuer β à gauche au mot P : P x R β x Un fait très important découle de cette règle : une formule avec un côté gauche vide est applicable à n'importe quel mot. Notez également qu'une formule avec des côtés gauche et droit vides ne change pas le mot. Définition de NAM Un algorithme de Markov normal (NAM) est un ensemble ordonné fini non vide de formules de substitution : 19
20 α1 β1 α 2 β 2... (k 1) α k β k Deux types de flèches peuvent être utilisées dans ces formules : une flèche régulière () et une flèche à queue (a). Une formule avec une flèche ordinaire est appelée une formule régulière, et une formule avec une flèche en queue est appelée une formule finale. La différence entre eux est expliquée ci-dessous. Ecrire un algorithme sous forme de NAM revient à présenter un tel ensemble de formules. Règles d'exécution de NAM Tout d'abord, on donne un mot d'entrée P. L'endroit exact où il est écrit n'a pas d'importance, cette question n'est pas spécifiée dans NAM. Le travail de NAM est réduit à la mise en œuvre d'une séquence d'étapes. A chaque étape, les formules de substitution incluses dans le NAM sont balayées de haut en bas et la première des formules applicables au mot d'entrée P est sélectionnée, c'est-à-dire le plus haut de ceux, dont la partie gauche est incluse dans R. Ensuite, la substitution est effectuée selon la formule trouvée. On obtient un nouveau mot P. A l'étape suivante, ce mot P est pris comme mot d'origine et on lui applique la même procédure, c'est-à-dire les formules sont à nouveau recherchées de haut en bas, en commençant par la plus haute, et la première formule applicable au mot P est recherchée, après quoi la substitution appropriée est effectuée et un nouveau mot P est obtenu. Et ainsi de suite : Р Р Р Une attention particulière doit être accordée au fait qu'à chaque étape de la formule aux États-Unis sont toujours considérés à partir de la toute première. Précisions nécessaires : 1. Si la formule habituelle (α β) a été appliquée à l'étape suivante, alors le travail NAM continue. 2. Si la formule finale (α a β) a été appliquée à l'étape suivante, alors après son application, le travail du NAM s'arrête. Le mot qui est sorti à ce moment est le mot de sortie, c'est-à-dire le résultat de l'application de NAM au mot d'entrée. Comme vous pouvez le constater, la différence entre les formules de substitution habituelle et finale ne se manifeste que par le fait qu'après l'application de la formule habituelle, le travail du NAM se poursuit et qu'il s'arrête après la formule finale. 3. Si à l'étape suivante aucune formule n'est applicable au mot courant, alors dans ce cas le travail du NAM est également terminé, et le mot courant est considéré comme le mot de sortie. Ainsi, NAM s'arrête pour deux raisons : soit la formule finale a été appliquée, soit aucune des formules ne correspond. Les deux sont considérés comme de "bonnes" fins pour NAM. Dans les deux cas, on dit que le NAM s'applique au mot d'entrée. vingt
Université d'État de Moscou nommée d'après M.V. Faculté Lomonossov de mathématiques computationnelles et de cybernétique V.N. Pilshchikov, V.G. Abramov, A.A. Vylitok, I.V. Machine de Turing chaude et algorithmes de Markov.
MACHINE DE TURING DANS L'ÉTUDE DE LA THÉORIE DES ALGORITHMES Lebedeva N.Yu. Branche Shuya de l'Université d'État d'Ivanovo MACHINE DE TURING DANS L'ÉTUDE DE LA THÉORIE DES ALGORITHMES Lebedeva N. Yu. Succursale de Chouya
ADDITION Ajouter 1 à un nombre signifie obtenir le nombre suivant celui donné : 4+1=5, 1+1=14, etc. Additionner les nombres 5 signifie ajouter un à 5 trois fois : 5+1+1+1=5+=8. SOUSTRAIRE Soustraire 1 d'un nombre signifie
Problèmes et solutions de la ronde de qualification de l'Olympiade DM&T 2014-2015 Tous les problèmes, manipulateurs et solutions sont à la disposition des participants sur le site Internet de l'Olympiade. Toutes les tâches proposées ont été évaluées avec le même nombre de points. Comptes.
Machine de Turing 1 Une machine de Turing est un concept mathématique, pas une vraie machine informatique. MT est un modèle mathématique d'un appareil informatique. MT a été proposé par Alan Turing en 1936
Résolution des problèmes de la machine de Turing en ligne >>> Résolution des problèmes de la machine de Turing en ligne Résolution des problèmes de la machine de Turing en ligne Le contenu d'une cellule peut changer, vous pouvez y écrire un autre caractère ou le supprimer
Systèmes de nombres A notre époque, une personne est constamment confrontée à des nombres. Depuis l'enfance, nous connaissons tous la notation généralement acceptée des nombres en chiffres arabes. Cependant, cette méthode d'enregistrement n'a pas été largement utilisée.
Algorithme implémenté Nous utilisons la variante suivante de l'algorithme d'Euclide pour calculer le pgcd des nombres M et N :. un M, b N; 2. t a-b, si t = 0, arrêtez ; 3. a t, b min(a,b), passez à l'étape 2. Après avoir arrêté GCD(M,N)
Problèmes du tour de qualification de l'Olympiade en mathématiques discrètes et informatique théorique avec solutions (lors de la résolution de problèmes constructifs, le participant travaille avec des émulateurs, des images de leurs interfaces sont affichées dans les solutions)
Chapitre B. Leçon d'arithmétique informatique B3. Arithmétique binaire Voyons comment vous avez fait les exercices de la leçon B2. Voici leurs solutions. Exercices B2-2 a) Le tableau de placement des kettlebells ressemble à ceci : numéroté
Leçon 23 Dans les conditions des problèmes M, x signifie, respectivement, la description de la machine de Turing et le mot d'entrée dans le format qui a été introduit lors de la conférence (et écrit dans le projet de manuel). Problème 23.1. Prouve-le
Section 6. Théorie des algorithmes. Un concept informel d'un algorithme, ses principales caractéristiques et propriétés. Alphabet, mots, algorithme dans l'alphabet. Algorithmes assez équivalents. Définition d'un algorithme normal (algorithme
SYSTÈMES DE NUMÉROTATION POSITIONNELLE Il existe de nombreuses façons de représenter les nombres. Dans tous les cas, le nombre est représenté par un symbole ou un groupe de symboles (mot) d'un alphabet. Nous appellerons ces symboles
Tâches pour l'étape de sélection de la 11e année. Premier tour 1. Codage des informations. Systèmes de numération (2 points) [Permutations] Combien y a-t-il de nombres hexadécimaux à trois chiffres qui seront simultanément
Résolution de problèmes sur le thème "Représentation des nombres dans un ordinateur" Types de problèmes : 1. Entiers. Représentation des nombres au format virgule fixe. 2. Nombres fractionnaires. Représentation des nombres au format virgule flottante.
1. Chevaliers et valets. Diagramme logique - 1. Tâches et solutions du tour à temps plein de l'Olympiade Dmitri-2017-2018 Quatre personnes sont assises à la table ronde. Chacun d'eux est soit un chevalier, soit un fripon. Les chevaliers disent toujours seulement
Systèmes de numération Le système de numération est une façon d'écrire des nombres à l'aide d'un ensemble donné de caractères spéciaux (chiffres). En informatique, on utilise des systèmes de numérotation de position, dans lesquels la valeur d'un chiffre
COURS 3. Algorithmes de traitement de tableaux unidimensionnels. Le but de la conférence: Familiarisation avec le concept d'un tableau. Acquisition de compétences dans la construction d'algorithmes destinés à traiter des tableaux unidimensionnels. 6. Algorithmes
Version de démonstration de la tâche USE 2019 6 L'entrée de l'algorithme est un nombre naturel N. L'algorithme en construit un nouveau nombre R comme suit. 1) On construit une notation binaire du nombre N. 2) A cette notation
Introduction aux systèmes de numération Lingot Le système de numération est une façon d'écrire des nombres en utilisant un ensemble donné de caractères spéciaux (chiffres). Il existe des systèmes de numération positionnels et non positionnels. En non positionnel
Partie III Langages, grammaires, automates 137 Chapitre 10 Langages et automates finis 10.1 Langage de Dick Comme nous le savons, les structures de parenthèses correctes sont énumérées par des nombres catalans. Nous écrivons toutes les parenthèses correctes
Étape municipale de l'Olympiade panrusse pour les écoliers en informatique Moscou, décembre 00. Tâches pour les classes 7-8 Chaque tâche est estimée à 0 point. Le score final est défini comme la somme des points pour les tâches
Machines virtuelles Introduction Il y a plus de quarante ans, l'éminent mathématicien américain Emil L. Post publiait dans le Journal of Symbolic Logic un article "Processus combinatoires finis, formulation !" (sa
Ugra Physics and Mathematics Lyceum VP Chuvakov Task C6 (Théorie des nombres sur l'examen d'État unifié) Guide pédagogique et méthodologique Khanty-Mansiysk 0 VP Chuvakov Problem C6 (Théorie des nombres sur l'examen d'État unifié): Guide d'étude, - Khanty-Mansiysk,
9 CLASSE 1. Dans l'une des cellules du papier quadrillé infini, il y a un robot, auquel les commandes suivantes peuvent être données : vers le haut (le robot se déplace vers la cellule suivante d'en haut) ; vers le bas (le robot se déplace vers
Systèmes numériques Le système numérique est une façon d'écrire des nombres à l'aide d'un ensemble donné de caractères spéciaux (chiffres). Il existe des systèmes de numération positionnels et non positionnels. Dans les systèmes non positionnels, le poids
Systèmes de numération Le système de numération est une façon de décrire les nombres en utilisant les caractères d'un certain alphabet selon des règles connues. Systèmes de nombres positionnels Dans le système de nombres positionnels, la valeur d'un chiffre dépend
K. Polyakov, 009-06 6- (niveau basique, durée 4 min) Sujet : Trouver un algorithme de longueur minimale pour un interprète. Ce que vous devez savoir : l'interprète est une personne, un groupe de personnes, un animal, une machine ou un autre objet,
Cours 5 Fondamentaux de la représentation de l'information dans les automates numériques Systèmes de nombres positionnels Le système de nombres est un ensemble de techniques et de règles d'écriture des nombres en caractères numériques. Tout prévu
Éléments de la théorie de la complexité Machine de Turing Alan Turing (23.06.1912-7.06.1954) (Alan Mathison Turing) Mathématicien, logicien, cryptographe anglais. En 1936, il proposa une "Machine de Turing" computationnelle abstraite,
Ministère de l'éducation et des sciences de la Fédération de Russie Établissement d'enseignement professionnel de la Fédération de Russie "Université d'État de Rostov" M. E. Abramyan
10 CLASSE 1. Les nombres réels satisfont les relations suivantes : Trouver tous les triplets possibles de nombres, où Solution. Notez qu'en dénotant et en soustrayant ces égalités les unes des autres, nous obtenons Supposons que tous
Annexe à l'article Gorbunov K.Yu., Lyubetsky V.A. "Un algorithme linéaire pour une restructuration minimale des structures" Preuve du lemme 3. On appelle un bloc rigide, délimité de part et d'autre par des gènes communs, semi-rigide
Annexe 1 Atelier pour le chapitre 2 "Représentation de l'information dans un ordinateur" Travaux pratiques pour le paragraphe 2.1 Exemple 2.1. Exprimez les nombres 2466,675 10, 1011,11 2 en fonction des puissances de la base. Pour décimal
Correspondance Lycée Physique et Mathématique "Avangard" EN Filatov ALGÈBRE 8 Manuel expérimental Partie 1 MOSCOU 2016 SOMMAIRE 1. Divisibilité. 2. Pair impair 3. Ensembles. 4. Tâches amusantes. 5. Combinatoire
Cahier de tâches sur l'informatique de l'élève (tsy) de la 11e classe physique et mathématique de l'école secondaire 36 de Vladimir Partie II 2016-2017 2 1. Algorithmisation. 1.1 Une opération est proposée sur deux arbitraires
Thème 7. Représentation de l'information dans un ordinateur Unités d'information. Bit - (chiffre bit-biry - chiffre binaire) la plus petite unité d'information - la quantité d'informations nécessaire pour distinguer deux événements également probables.
I. V. Yakovlev Matériaux sur les mathématiques MathUs.ru Contenu Notation décimale 1 Olympiade panrusse des écoliers en mathématiques......... 1 2 Olympiade mathématique de Moscou......... ....... ........
Thème 1 : Systèmes d'équations linéaires A. Ya. Ovsyannikov Institut universitaire fédéral de mathématiques et d'informatique de l'Oural Département d'algèbre et de mathématiques discrètes Algèbre et géométrie pour physiciens-ingénieurs
Chapitre 5 Éléments de la théorie des algorithmes 31 Clarification du concept d'algorithme Mots-clés : algorithme théorie des algorithmes exécuteur universel Machine de Turing Algorithme de Markov normal post-machine Pourquoi
Résoudre des problèmes sur le thème "Représentation des nombres dans un ordinateur". Types de tâches. 1. Entiers. Représentation des nombres au format virgule fixe. 2. Nombres fractionnaires. Représenter des nombres au format flottant
A. Shen Jeux et stratégies du point de vue des mathématiques, MTsNMO Jeux simples et classification des positions Il y a 12 matchs sur la table. Les joueurs jouent à tour de rôle entre un et trois matchs. Qui ne peut pas bouger
Théorie des algorithmes 79 3.2. Algorithmes normaux j Soit A un alphabet ne contenant aucun symbole. et. Une formule de substitution ordinaire est une représentation de la forme P Q, où P et Q sont des mots de l'alphabet A. La finale
COURS 2. Algorithmes de structure cyclique. Objectif du cours : Connaissance du concept d'algorithme de structure cyclique. Acquisition de compétences dans la construction d'algorithmes pour une structure cyclique. 5. Algorithmes du cyclique
Conférences sur les mathématiques. Publier. TMM-1 Yu. V. Chebrakov THÉORIE DES MATRICES MAGIQUES Saint-Pétersbourg, 2010 technologie.
Travaux pratiques. Formes de représentation de l'information numérique sur un ordinateur. Partie I. Systèmes de numération. Un système numérique est une façon de représenter n'importe quel nombre en utilisant un alphabet
Institut de physique et de technologie de Moscou Faculté d'innovation et de hautes technologies Mathematical Logic and Theory of Algorithms, automne 2018 Séminaire 1 : un langage d'écriture d'énoncés formels, avec des solutions à certains
Conférence 16
16 (niveau élevé, temps min) Sujet : Codage des nombres. Systèmes de numération. Ce que vous devez savoir : les principes d'encodage des nombres dans les systèmes de nombres positionnels afin de traduire un nombre, par exemple 15, à partir du système
2015 Expressions régulières Solutions aux problèmes du tour de qualification (deux options) Option 1 Construire une expression régulière qui décrit l'ensemble des mots à partir des lettres a et b, d'où tous les mots spécifiés par les lettres régulières
