Machine de Turing et algorithmes de Markov. Résolution de problème. La pensée est matérielle : Alan Turing comme « calculateur universel » Description de la machine de Turing
Programmes car les machines de Turing sont écrites 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 (l'alphabet interne). Le contenu du tableau représente les 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 quelle commande exécuter. La commande est déterminée par l'intersection des caractères des alphabets externe et interne dans le tableau.
Pour définir une machine de Turing spécifique, vous avez besoin décrivez les composants suivants pour cela:
Alphabet externe. Un ensemble fini (désigné par la lettre A), dont les éléments sont appelés lettres (symboles). L'une des lettres de cet alphabet (par exemple a0) doit être un caractère nul.
Par exemple, l'alphabet d'une machine de Turing binaire est donné par A = (0, 1, a0).
Une chaîne continue de symboles sur une bande est appelée en un mot.
Automatique appelé un appareil qui fonctionne sans intervention humaine. Un automate dans une machine de Turing possède plusieurs états et, sous certaines conditions, passe d'un état à un autre. L’ensemble des états d’un automate est appelé l’alphabet interne.
Alphabet interne. Un ensemble fini d'états d'un chariot (automate). Désigné par la lettre Q=(q1,q2...). L'un des états - q1- doit être initial (lancement du programme). Un autre des états (q0) doit être final (terminant le programme) - l'état d'arrêt.
Tableau de transition. Description du comportement de la machine (chariot) en fonction de l'état et du symbole lu.
L'automate d'une machine de Turing lors de son fonctionnement est contrôlé par un programme, au cours de chaque étape duquel les éléments suivants sont exécutés séquentiellement : Actions:
Écrivez un caractère d'un alphabet externe dans une cellule (y compris une cellule vide), en remplaçant celui qui s'y trouve (y compris une cellule vide).
Déplacez une cellule vers la gauche ou la droite.
Changez votre état intérieur.
C'est pourquoi lors de l'élaboration d'un programme pour chaque paire (symbole, état), vous devez déterminer trois paramètres: symbole ai de l'alphabet A sélectionné, sens de déplacement du chariot ("←" - gauche, "→" - droite, "point" - pas de mouvement) et le nouvel état de la machine qk.
Par exemple, équipe 1 "←” q2 signifie « remplacez le caractère par 1, déplacez le curseur vers la gauche d'une cellule et passez à l'état q2 ».
On suppose qu'un exécuteur universel doit être capable de prouver l'existence ou la non-existence d'un algorithme pour une tâche particulière.
Question 28
La thèse de Turing est une position fondamentale de la théorie des algorithmes, acceptée sans preuve, selon laquelle tout algorithme peut être représenté sous la forme d'une machine de Turing.
Programme de la machine de Turing (R) - la totalité de toutes les commandes. Le programme est présenté sous forme de tableau et s'appelle Circuit fonctionnel de Turing.
| un 0 | un 1 | un 2 | |
| q1 | une 0 Pq 1 | une 1 Pq 1 | une 2 Lq 2 |
| q2 | un 1 Pq 2 | une 2 Нq 0 | une 0 Нq 0 |
Question 29
Machines de Turing à deux sorties
Supposons que nous étendions la définition d'une machine de Turing en ajoutant un certain état q* au dispositif de contrôle de la machine. Nous dirons que si le dispositif de contrôle passe à l'état q0 pour un mot d'entrée x donné, alors la machine admet x. Si le dispositif de contrôle atteint l'état q*, alors la machine inhibe x. Nous appellerons un tel dispositif une machine de Turing à deux sorties.
Il s'avère que si l'on dispose de deux machines de Turing T1 et T2, qui admettent respectivement des ensembles disjoints de mots X1 et X2, alors il est toujours possible de construire une machine de Turing T3 avec deux sorties, qui admettra X1 et interdira X2. Ces machines de Turing nous seront utiles pour examiner la question de la décidabilité.
Un ensemble est décidable s’il existe une machine de Turing à deux sorties qui admet tous les éléments de l’ensemble et refuse les éléments qui n’y appartiennent pas.
Question 30
Une machine de Turing multi-bandes consiste en une commande finie avec k têtes de bande, une sur chaque bande (Figure 6.4).
Chaque bande est sans fin dans les deux sens. D'un seul mouvement, en fonction de l'état du contrôle final et du symbole scanné de chacune des têtes de bande, la machine peut : 1) changer d'état ; 2) imprimer un nouveau caractère sur chacune des cellules numérisées ; 3) déplacer chacune de ses têtes de bande indépendamment les unes des autres d'une cellule vers la gauche, vers la droite, ou la laisser au même endroit.
Au début, la chaîne d'entrée n'est disponible que sur la première bande et toutes les autres bandes sont vides. Nous ne définirons pas ce dispositif de manière plus formelle, le laissant au lecteur.
Théorème 6.2. Si une langue L est acceptée par une machine de Turing multi-bande, alors elle est acceptée par une machine de Turing mono-bande. Preuve. Soit un langage L accepté par une machine de Turing T1 avec k bandes. Construisons une machine de Turing T2 à bande unique avec 2 000 pistes, deux pour chacune des bandes de la machine T1. Une piste enregistre le contenu de la bande de la machine T1 correspondante, et l'autre est vierge à l'exception d'un marqueur dans la cellule contenant le caractère et scanné par la tête de la machine T1 correspondante. Un tel dispositif permettant de modéliser trois bandes en utilisant une seule est illustré sur la Fig. 6.5. Le contrôle final de la machine T2 mémorise quels marqueurs de la tête de machine T1 se trouvent à gauche et lesquels se trouvent à droite de la tête T2. Les états de la machine T1 sont également stockés dans le contrôle final de la machine T2.
Pour simuler le mouvement de la machine T1, la machine T2 doit visiter chaque cellule de marqueur de tête, enregistrant tour à tour le caractère scanné par la tête correspondante de T1. Lorsque T2 passe par un marqueur de tête, il doit clarifier la direction dans laquelle rechercher ce marqueur. Après avoir collecté toutes les informations nécessaires, la machine T2 détermine le mouvement de la machine T1. La machine T2 visite ensuite à nouveau tour à tour chacun des marqueurs de tête, en changeant les cellules marquées et en déplaçant les marqueurs d'une cellule si nécessaire. Bien entendu, si le nouvel état est accepté, alors la machine T2 accepte la chaîne d'entrée.
Et, selon la thèse de Church-Turing, capable d'imiter tous les artistes(en spécifiant des règles de transition) qui mettent en œuvre en quelque sorte le processus de calcul étape par étape, dans lequel chaque étape de calcul est assez élémentaire.
Autrement dit, n’importe quel algorithme intuitif peut être implémenté à l’aide d’une machine de Turing.
Appareil
La machine de Turing comprend un nombre illimité 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(aussi appelé tête de lecture-écriture (GZCH)), 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 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 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 (pour une machine de Turing non déterministe, il peut y avoir plus de règles). 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.
Exemple
Un exemple de machine de Turing pour multiplier des nombres dans le système numérique unaire. L'entrée de la règle « q i a j →q i1 a j1 R/L/N » doit être comprise comme suit : q i est l'état dans lequel cette règle est exécutée, a j est les données de la cellule dans laquelle se trouve la tête, q i1 est l'état vers lequel aller, a j1 - ce qui doit être écrit dans la cellule, R/L/N - la commande pour se déplacer.
La machine fonctionne selon l'ensemble de règles suivant :
| q 0 | q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | q 0 1 → q 0 1R | q 1 1 → q 2 aR | q 2 1 → q 2 1L | q 3 1 → q 4 aR | q 4 1 → q 4 1R | q 7 1 → q 2 aR | |||
| × | q 0 × → q 1 × R | q 2 × → q 3 × L | q 4 × → q 4 × R | q 6 × → q 7 × R | q 8 × → q 9 × N | ||||
| = | q 2 = → q 2 = L | q 4 = → q 4 = R | q 7 = → q 8 = L | ||||||
| un | q 2 a → q 2 aL | q 3 a → q 3 aL | q 4 a → q 4 aR | q 6 une → q 6 1R | q 7 une → q 7 aR | q 8 a → q 8 1L | |||
| * | q 0 * → q 0 * R | q 3 * → q 6 * R | q 4 * → q 5 1R | ||||||
| q 5 →q 2 *L |
Description des états :
| Commencer | |
| q 0 | Etat initial. Nous recherchons le « x » à droite. Une fois trouvé, nous passons à l'état q1 |
|---|---|
| q1 | remplacez « 1 » par « a » et passez à l’état q2 |
| On transfère tous les « 1 » du premier chiffre au résultat | |
| q2 | en recherchant le « x » à gauche. Une fois trouvé, nous passons à l'état q3 |
| q3 | On cherche « 1 » à gauche, on le remplace par « a » et on passe à l'état q4. Si « 1 » est terminé, recherchez « * » et passez à l'état q6 |
| q4 | allez jusqu'à la fin (recherchez « * » à droite), remplacez « * » par « 1 » et passez à l'état q5 |
| q5 | ajoutez « * » à la fin et passez à l'état q2 |
| Nous traitons chaque chiffre du deuxième nombre | |
| q6 | On cherche « x » à droite et on passe à l’état q7. Pendant que nous cherchons, remplacez « a » par « 1 » |
| q7 | cherchez « 1 » ou « = » à droite quand on trouve "1", remplacez-le par "a" et passez à l'état q2 quand on trouve "=" on passe à l'état q8 |
| Fin | |
| q8 | en recherchant le « x » à gauche. Une fois trouvé, nous passons à l’état q9. Pendant que nous cherchons, remplacez « a » par « 1 » |
| q9 | état terminal (arrêt de l'algorithme) |
En utilisant MT, nous multiplions 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é).
Commencer. Nous sommes dans l'état q 0, nous avons entré les données dans la machine : *111x11=*, la tête de la machine est située sur le premier caractère *.
1ère étape. Nous regardons le tableau des règles pour voir ce que fera la machine lorsqu'elle sera dans l'état q 0 et au-dessus du symbole « * ». C'est la règle de la 1ère colonne de la 5ème ligne - q 0 *→q 0 *R. Cela signifie que nous passons à l'état q 0 (c'est-à-dire que nous ne le modifions pas), le symbole deviendra « * » (c'est-à-dire qu'il ne changera pas) et nous nous déplaçons le long du texte que nous avons entré « *111x11=* " vers la droite d'une position (R), puis il y a un 1 sur le 1er symbole. À son tour, l'état q 0 1 (1ère colonne 1ère ligne) est traité par la règle q 0 1→q 0 1R. Autrement dit, encore une fois, il y a simplement une transition vers la droite d'une position. Cela se produit jusqu'à ce que nous nous trouvions sur le symbole « x ». Et ainsi de suite : on prend l'état (index en q), on prend le symbole sur lequel on se tient (le symbole souligné), on les connecte et on regarde le traitement de la combinaison résultante selon le tableau des règles.
En termes simples, l'algorithme de multiplication est le suivant : on marque la 1ère unité du 2ème facteur en la remplaçant par la lettre « a », et on transfère la totalité du 1er facteur derrière le signe égal. Le transfert s'effectue en remplaçant alternativement les unités du 1er multiplicateur par « a » et en ajoutant le même nombre d'unités en fin de ligne (à gauche du « * ») le plus à droite. Ensuite, nous remplaçons tous les « a » jusqu’au signe de multiplication « x » par des uns. Et le cycle se répète. En effet, A multiplié par B peut être représenté comme A+A+A B fois. Maintenant, nous marquons la 2ème unité du 2ème multiplicateur avec la lettre «a» et transférons à nouveau les unités. Lorsqu'il n'y a pas d'unités avant le signe « = », la multiplication est terminée.
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'un petit fragment de données en mémoire (dans le cas d'une machine de Turing, une seule cellule), et le nombre d'actions possibles n'est pas infini. 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'opérations é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. ré (style d'affichage D) et données d'entrée X (style d'affichage 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 (style d'affichage 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.
Une machine de Turing peut simuler une machine postale, des algorithmes de Markov normaux et tout programme pour ordinateurs ordinaires qui convertit les données d'entrée en données de sortie selon 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 à 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 fini. Limite théorique de la quantité d'informations pouvant être contenue dans une surface donnée, jusqu'à un facteur 1 / ln 2 (\displaystyle 1/\ln (2))égale à l’entropie d’un trou noir de même surface.
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 (c'est-à-dire une bande infinie dans une direction).
simulateur pour apprendre l'interprète universel
Ce que c'est?
Le simulateur Turing Machine est un modèle de formation d'un exécuteur universel (machine informatique abstraite), proposé en 1936 par A. Turing pour clarifier le concept d'algorithme. Selon la thèse de Turing, n'importe quel algorithme peut être écrit sous forme de programme pour une machine de Turing. Il a été prouvé que la machine de Turing est équivalente dans ses capacités à la machine Post et aux algorithmes de Markov normaux.
Une machine de Turing est constituée d'un chariot (tête de lecture et d'écriture) et d'une bande sans fin divisée en cellules. Chaque cellule de la bande peut contenir un caractère d'un alphabet A=(a 0 ,a 1 ,…,a N ) . Tout alphabet contient un caractère espace, noté 0 ou Λ. Lors de la saisie de commandes, l'espace est remplacé par un trait de soulignement "_".
Une machine de Turing est un automate contrôlé par une table. Les lignes du tableau correspondent aux caractères de l'alphabet sélectionné A, et les colonnes correspondent aux états de la machine Q=(q 0 ,q 1 ,…,q M ) . Au début de son fonctionnement, la machine de Turing est dans l'état q 1 . L'état q 0 est l'état final : une fois dedans, la machine termine son fonctionnement.
Dans chaque cellule du tableau, correspondant à un symbole a i et à un état q j, il y a une commande composée de trois parties :
- caractère de l'alphabet A;
- sens de déplacement : > (à droite),
- nouvel état de la machine
Nouvelles
- Falina I.N. Le sujet « Machine de Turing » dans le cours d'informatique de l'école (inf.1september.ru).
- Mayer R.V. Machines Post et Turing (komp-model.narod.ru).
- Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Machine de Turing et algorithmes de Markov. Résolution de problèmes, M. : MSU, 2006.
- Bekman I.N. L'informatique. Conférence 7. Algorithmes (profbeckman.narod.ru)
- Soloviev A. Mathématiques discrètes sans formules (lib.rus.ec)
- Ershov S.S.Éléments de la théorie des algorithmes, Chelyabinsk, SUSU Publishing Center, 2009.
- Varpakhovsky F.L.Éléments de théorie des algorithmes, M : Prosveshchenie, 1970.
- Vereshchagin N.K., Shen A. Fonctions calculables, M : MTsNMO, 1999.
Que faire à ce sujet ?
En haut du programme se trouve un champ d'édition dans lequel vous pouvez saisir la condition problématique sous forme libre.
Le ruban se déplace de gauche à droite à l'aide des boutons situés à gauche et à droite de celui-ci. En double-cliquant sur une cellule du ruban (ou en cliquant avec le bouton droit), vous pouvez modifier son contenu.
Utilisation du menu Ruban vous pouvez stocker l'état de la bande dans le tampon interne et restaurer la bande à partir du tampon.
Sur le terrain Alphabet Les caractères de l'alphabet sélectionné sont spécifiés. Un espace est automatiquement ajouté aux caractères saisis.
Le programme est saisi dans le tableau en bas de la fenêtre. La première colonne contient des caractères alphabétiques et est remplie automatiquement. La première ligne répertorie tous les états possibles. Vous pouvez ajouter et supprimer des colonnes de tableau (état) à l'aide des boutons situés au-dessus du tableau.
Lorsque vous saisissez une commande dans une cellule du tableau, vous devez d'abord saisir un nouveau caractère, puis le sens de la transition et le numéro d'état. Si un caractère est omis, il reste inchangé par défaut. Si le numéro d'état est omis, par défaut l'état de la machine ne change pas.
Directement sur le terrain Un commentaire Vous pouvez saisir des commentaires libres sur la solution. Le plus souvent, cela explique ce que signifie chaque état d’une machine de Turing.
Le programme peut être exécuté en continu (F9) ou par étapes (F8). La commande qui va maintenant être exécutée est mise en évidence sur un fond vert. La vitesse d'exécution est réglable à l'aide du menu Vitesse.
Les problèmes de la machine de Turing peuvent être enregistrés dans des fichiers. La condition de la tâche, l'alphabet, le programme, les commentaires et l'état initial de la bande sont enregistrés. Lorsqu'une tâche est chargée à partir d'un fichier et enregistrée dans le fichier, l'état de la bande est automatiquement mis en mémoire tampon.
Si vous remarquez une erreur ou avez des suggestions, des commentaires, des plaintes, des demandes ou des déclarations, écrivez.
Les pré-requis techniques
Le programme fonctionne sous les systèmes d'exploitation de la ligne les fenêtres sur n'importe quel ordinateur moderne.
Licence
Le programme est gratuit pour une utilisation non commerciale. Le code source du programme n'est pas distribué.
Le programme vient " comme si", c'est-à-dire que l'auteur n'assume aucune responsabilité pour toutes les conséquences possibles de son utilisation, y compris les pertes morales et matérielles, les pannes d'équipement, les blessures physiques et mentales.
Lors de la publication du programme sur d'autres sites Web, un lien vers la source originale est requis.
- 1) publication de documents sous quelque forme que ce soit, y compris la publication de documents sur d'autres sites Web ;
- 2) distribution de documents incomplets ou modifiés ;
- 3) inclusion de matériaux dans des collections sur n'importe quel support ;
- 4) obtenir des avantages commerciaux de la vente ou d'une autre utilisation de matériaux.
Le téléchargement de matériel signifie que vous acceptez les termes de cet accord de licence.
Télécharger
Après décompression de l'archive, le programme est en état de marche et ne nécessite aucune installation supplémentaire.
Introduction
Une machine de Turing est un appareil informatique très simple. Il se compose d'une bande d'une longueur infinie, divisée en cellules, et d'une tête qui se déplace le long de la bande et est capable de lire et d'écrire des caractères. En outre, une machine de Turing possède une caractéristique telle qu'un état, qui peut être exprimé sous la forme d'un nombre entier allant de zéro à une valeur maximale. Selon l'état, une machine de Turing peut effectuer l'une des trois actions suivantes : écrire un symbole dans une cellule, déplacer une cellule vers la droite ou la gauche et définir l'état interne.
La conception d’une machine de Turing est extrêmement simple, mais elle peut exécuter presque tous les programmes. Pour effectuer toutes ces actions, un tableau spécial de règles est fourni, qui précise ce qui doit être fait pour diverses combinaisons d'états actuels et de symboles lus sur la bande.
En 1947, Alan Turing a élargi la définition pour décrire une « machine de Turing universelle ». Plus tard, pour résoudre certaines classes de problèmes, une variante de celui-ci a été introduite, ce qui a permis d'effectuer non pas une tâche, mais plusieurs.
Description de la machine de Turing
Le contexte de la création de cet ouvrage est lié à la formulation de problèmes mathématiques non résolus par David Hilbert lors du Congrès international de mathématiques à Paris en 1900. L'un d'eux était la tâche de prouver la cohérence du système d'axiomes de l'arithmétique ordinaire, que Hilbert a ensuite clarifié comme le « problème de décidabilité » - trouver une méthode générale pour déterminer la satisfiabilité d'un énoncé donné dans le langage de la logique formelle.
L'article de Turing a précisément donné la réponse à ce problème : le deuxième problème de Hilbert s'est avéré insoluble. Mais l’importance de l’article de Turing allait bien au-delà du problème pour lequel il avait été rédigé.
Voici une description de ce travail, appartenant à John Hopcroft : " En travaillant sur le problème de Hilbert, Turing a dû donner une définition claire du concept même de méthode. Partant de l'idée intuitive d'une méthode comme une sorte d'algorithme, c'est-à-dire une procédure qui peut être exécutée mécaniquement, sans intervention créative", il a montré comment cette idée pouvait être incarnée sous la forme d'un modèle détaillé du processus de calcul. Le modèle de calcul résultant, dans lequel chaque algorithme était décomposé en une séquence composée d'étapes simples et élémentaires, était la construction logique qui fut plus tard appelée la machine de Turing. »
Une machine de Turing est une extension du modèle de machine à états finis, une extension qui inclut une mémoire potentiellement infinie avec la possibilité de se déplacer (se déplacer) de la cellule actuellement visualisée vers sa voisine gauche ou droite.
Formellement, une machine de Turing peut être décrite comme suit. Soit donné ce qui suit :
un ensemble fini d'états - Q, dans lesquels une machine de Turing peut se trouver ;
ensemble fini de symboles de bande - Г ;
fonction d (fonction ou programme de transition), qui est spécifiée en mappant une paire du produit cartésien Q x Г (la machine est dans l'état qi et visualise le symbole i) dans un triplet du produit cartésien Q x Г x (L ,R) (la machine passe à l'état qi, remplace le caractère i par le caractère j et se déplace d'un caractère de bande vers la gauche ou la droite) - Q x Г-->Q x Г x (L,R)
un caractère de Г-->е (vide) ;
le sous-ensemble У є Г - -> est défini comme un sous-ensemble des symboles d'entrée de la bande, et е є (Г - У) ;
l'un des états - q0 є Q est l'état initial de la machine.
Le problème à résoudre est spécifié en enregistrant sur bande un nombre fini de symboles de l'ensemble U є Г - Si є У :
eS1S2S3S4... ... ...Sné
après quoi la machine est transférée à l'état initial et la tête est installée sur le symbole non vide le plus à gauche (q0,w) -, après quoi, conformément à la fonction de transition spécifiée (qi,Si) - ->(qj, Sk, L ou R), la machine commence à remplacer les symboles visualisés, déplace la tête vers la droite ou la gauche et passe à d'autres états prescrits par les fonctions de transition.
La machine s'arrête si la fonction de transition pour le couple (qi,Si) n'est pas définie.
Alan Turing a proposé que tout algorithme au sens intuitif du terme puisse être représenté par une machine de Turing équivalente. Cette hypothèse est connue sous le nom de thèse de Church-Turing. Chaque ordinateur peut simuler une machine de Turing (opérations de réécriture de cellules, comparaison et déplacement vers une autre cellule voisine, prise en compte des changements d'état de la machine). Par conséquent, il peut modéliser des algorithmes dans n'importe quel formalisme, et de cette thèse il résulte que tous les ordinateurs (indépendamment de leur puissance, de leur architecture, etc.) sont équivalents en termes de capacité fondamentale à résoudre des problèmes algorithmiques.
Propriétés de la machine de Turing en tant qu'algorithme
En utilisant la machine de Turing comme exemple, les propriétés des algorithmes peuvent être clairement vues. Demandez aux élèves de montrer qu’une machine de Turing possède toutes les propriétés d’un algorithme.
Discrétion. Une machine de Turing ne peut passer à la (k + 1)ème étape qu'après avoir terminé chaque étape, puisque c'est chaque étape qui détermine ce que sera la (k + 1)ème étape.
Clarté. A chaque étape, un symbole de l'alphabet est écrit dans la cellule, l'automate effectue un mouvement (L, P, N) et la machine de Turing passe dans l'un des états décrits.
Déterminisme. Chaque cellule du tableau de la machine de Turing ne contient qu'une seule option pour une action. À chaque étape, le résultat est déterminé de manière unique, par conséquent, la séquence d'étapes pour résoudre le problème est déterminée de manière unique, c'est-à-dire Si une machine de Turing reçoit le même mot d’entrée, alors le mot de sortie sera le même à chaque fois.
Productivité. En termes de contenu, les résultats de chaque étape et la séquence entière d'étapes sont déterminés de manière unique ; par conséquent, une machine de Turing correctement écrite ira à l'état q0 en un nombre fini d'étapes, c'est-à-dire en un nombre fini d’étapes, la réponse à la question problématique sera obtenue.
Caractère de masse. Chaque machine de Turing est définie sur tous les mots admissibles de l'alphabet, c'est la propriété du caractère de masse. Chaque machine de Turing est conçue pour résoudre une classe de problèmes, c'est-à-dire Pour chaque problème, sa propre (nouvelle) machine de Turing est écrite.
Transcription
1Université d'État 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 de formation) Moscou, 2006
2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Machine de Turing et algorithmes de Markov. Résolution de problème. (Manuel pédagogique) - M. : Université d'État de Moscou, p. Département d'édition de la Faculté de mathématiques computationnelles et de mathématiques de l'Université d'État de Moscou (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 mathématiques computationnelles et Mathématiques de l'Université d'État de Moscou dans la discipline « Algorithmes et langages algorithmiques ». Il s'agit de problèmes de composition d'algorithmes sous la forme d'une machine de Turing et d'algorithmes de Markov normaux, ainsi que de problèmes de nature théorique. Le manuel fournit les informations nécessaires sur la théorie des algorithmes, explique en détail les méthodes 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é de mathématiques computationnelles et de mathématiques de l'Université d'État de Moscou et pour les enseignants qui animent des séminaires sur la programmation. Réviseurs : Professeur agrégé Baula V.G. Professeur agrégé Korukhova L.S. Publié par décision du Conseil de rédaction et d'édition de la Faculté de mathématiques computationnelles et de cybernétique de l'Université d'État de Moscou. M.V. Lomonossov. ISBN ??? Département d'édition de la Faculté de mathématiques computationnelles et de cybernétique de l'Université d'État de Moscou. M.V. Lomonossov,
3 1. Machine de Turing Cette section traite des problèmes de création d'algorithmes pour une machine de Turing. Une brève description de cette machine est donnée, les techniques de base pour compiler de tels algorithmes sont expliquées avec des exemples et des problèmes sont proposés pour une solution indépendante. 1.1 Brève description d'une machine de Turing Structure d'une machine de Turing Une machine de Turing (MT) se compose de deux parties, une bande et un automate (voir à gauche) : bande : a b b Λ Λ a b b Λ Λ automate : q q La bande est utilisée pour stocker information. Il est sans fin dans les deux sens et est divisé en cellules qui ne sont ni numérotées ni nommées. Chaque cellule peut contenir un caractère ou rien du tout. Le contenu de la cellule peut changer, vous pouvez y écrire un autre symbole ou effacer le symbole qui s'y trouve. Mettons-nous d’accord pour appeler le contenu vide d’une cellule le symbole « vide » et désignons-le par le signe Λ (« lambda »). Pour cette raison, l’image de la bande affichée dans l’image de droite est la même que celle de gauche. Cet accord est pratique dans la mesure où l'opération d'effacement d'un symbole dans une certaine cellule peut être considérée comme l'écriture du symbole Λ dans cette cellule, donc, au lieu de la longue phrase « écrire un symbole dans une cellule ou effacer un symbole qui s'y trouve », vous pouvez simplement dire « écrire un symbole dans une cellule ». La machine est la partie active du MT. A chaque instant, il se situe sous l'une des cellules de la bande et en voit le contenu ; il s'agit d'une cellule visible, et le symbole qu'elle contient est un symbole visible ; La machine ne voit pas le contenu des cellules voisines et autres. De plus, à chaque instant l'automate est dans l'un des états, que nous désignerons par la lettre q avec des chiffres : q1, q2, etc. Dans un certain état, l'automate effectue une opération spécifique (par exemple, se déplace vers la droite le long de la bande, en remplaçant tous les symboles b par a), tout en étant dans un état différent, une autre opération. Nous appellerons une paire composée d'un symbole visible (S) et de l'état actuel de la machine (q) une configuration et notons
4 Cycle de fonctionnement de la machine de Turing MT fonctionne en cycles exécutés les uns après les autres. A chaque cycle d'horloge, l'automate MT effectue les trois actions suivantes, et toujours dans l'ordre spécifié : 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 (désignation L, en partant de la gauche), ou d'une cellule vers la droite (désignation R, en partant de la droite), ou reste immobile (désignation N). 3) passe à un état q (en particulier, il peut rester dans l'état précédent). Formellement, nous écrirons les actions d'une barre sous la forme d'un triplet : S, , q où la construction entre crochets signifie qu'il est possible d'écrire n'importe laquelle des lettres L, R ou N à cet endroit. Par exemple, barre *,L,q8 signifie écrire le symbole * dans une cellule visible, décaler une cellule vers la gauche et passer à l'état q8. Le programme pour une machine de Turing MT en lui-même ne fait rien. Pour que cela fonctionne, vous devez écrire un programme correspondant. Ce programme s'écrit sous la forme du tableau suivant : q 1 q j q m S 1 S 2 S i S n Λ S, , q A gauche se trouvent tous les états dans lesquels peut se trouver la machine, en haut se trouvent tous les symboles (y compris Λ) que la machine peut voir sur la bande. (Les symboles et états indiqués dans le tableau sont déterminés par l'auteur du programme.) Aux intersections (dans les cellules du tableau), les cycles que la machine doit effectuer lorsqu'elle est dans l'état approprié et voit le symbole correspondant sur le ruban adhésif sont indiqués. En général, le tableau définit les actions du MT pour toutes les configurations possibles et précise ainsi complètement le comportement du MT. Décrire un algorithme sous forme de MT signifie présenter un tel tableau. (Remarque : un MT est souvent défini comme étant constitué d'une bande, d'une machine et d'un programme, donc différents programmes aboutissent à différents MT. Nous supposerons, dans l'esprit des ordinateurs modernes, qu'il existe 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, vous devez effectuer les étapes préliminaires suivantes. Tout d’abord, vous devez écrire sur la bande le mot d’entrée auquel le programme sera appliqué. Le mot d'entrée est une séquence finie de symboles écrits dans des cellules adjacentes de la bande ; Il ne doit y avoir aucune cellule vide à l'intérieur du mot saisi, et il ne doit y avoir que des cellules vides à gauche et à droite de celui-ci. Un mot d'entrée vide signifie que toutes les cellules de la bande sont vides. Deuxièmement, vous devez régler l'automate sur l'état q 1 (indiqué en premier dans le tableau) et le placer sous le premier caractère du mot d'entrée : a b b q 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. Dans le tableau, une cellule se trouve à l'intersection de la première ligne (puisque la machine est dans l'état q 1) et de la colonne qui correspond au premier caractère du mot saisi (ce n'est pas forcément la colonne de gauche du tableau) , et le cycle spécifié 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 correspondant à l'état et au symbole de cette configuration se retrouve dans le tableau, et un cycle est exécuté à partir de cette cellule. Et ainsi de suite. Quand le programme se termine-t-il ? Introduisons le concept de cycle d'arrêt. C'est une étape qui ne change rien : la machine écrit dans la cellule visible le même symbole qui s'y trouvait auparavant, ne bouge pas et reste dans le même état, c'est-à-dire c'est l'horloge S,N,q pour la configuration
6 2) Le deuxième résultat est « mauvais » : c'est lorsque le MT avance par cycles, sans jamais atteindre le chronomètre (par exemple, la machine 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, nous disons que MT n’est pas applicable au mot d’entrée donné. On ne peut parler 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 non applicable à 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 à ceux qui concernent les données initiales admissibles du problème à résoudre, pour lesquelles le problème a un sens. Mais tous les mots saisis peuvent être écrits sur la bande, y compris ceux pour lesquels la tâche n'a pas de sens ; Le comportement de l'algorithme n'est pas figé sur de tels mots : il peut s'arrêter (pour n'importe quel résultat), ou il peut avancer par cycles. Conventions pour raccourcir la notation Mettons-nous d'accord sur certaines conventions qui raccourcissent la notation du programme pour MT. 1) Si le symbole visible ne change pas dans une mesure, ou si la machine ne bouge pas, ou si l'état de la machine ne change pas, alors nous n'écrirons rien dans la position correspondante de la mesure. Par exemple, lors de la configuration
7 1.2 Exemples d'écriture de programmes pour MT Examinons des exemples d'écriture de programmes pour MT afin de démontrer quelques techniques de programmation typiques pour MT. Pour raccourcir la formulation des problèmes, nous introduisons les deux conventions suivantes : la lettre P désignera le mot d'entrée ; La lettre A désignera l'alphabet du mot saisi, c'est-à-dire un ensemble de symboles à partir desquels et seulement à partir desquels P peut consister (notez cependant que d'autres symboles peuvent apparaître dans les mots intermédiaires et de sortie). Exemple 1 (déplacement de la machine, remplacement des symboles) A=(0,1,2,3,4,5,6,7,8,9). Soit P un mot non vide ; Cela signifie que P est une séquence de chiffres décimaux, c'est-à-dire écrire un entier non négatif dans le système décimal. Il est nécessaire d'obtenir sur 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éplacez la machine jusqu'au dernier chiffre du numéro. 2. S'il s'agit d'un chiffre de 0 à 8, remplacez-le par un chiffre 1 de plus et arrêtez ; par exemple : S'il s'agit du chiffre 9, alors remplacez-le par 0 et déplacez la machine au chiffre précédent, puis augmentez cet avant-dernier chiffre de 1 de la même manière ; par exemple : Cas particulier : P ne contient que des neuf (par exemple, 99). Ensuite, la machine se déplacera vers la gauche, remplaçant les neuf par des zéros, et finira par se retrouver sous une cellule vide. Il faut écrire 1 dans cette cellule vide et arrêter (la réponse sera 100) : Sous forme de 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 un état dans lequel la machine « fonctionne » jusqu'au dernier chiffre du numéro. 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 particularité : lorsque la machine a moins de 7 ans
8 est le dernier chiffre, alors il ne le sait pas encore (après tout, il ne voit pas ce qui est écrit dans les cellules voisines) et ne le déterminera que lorsqu'il atterrira sur une cellule vide. Ainsi, ayant atteint la première cellule vide, la machine revient au dernier chiffre et passe à l'état q2 (il n'est pas nécessaire de se déplacer vers la droite). q2 est un état dans lequel la machine ajoute 1 au chiffre qu'elle voit actuellement. C'est d'abord le dernier chiffre du numéro ; s'il est compris entre 0 et 8, alors la machine le remplace par un nombre égal à 1 de plus et s'arrête. Mais s’il s’agit du chiffre 9, alors la machine le remplace par 0 et se déplace vers la gauche, restant dans l’état q2. Ainsi, il ajoutera désormais 1 au chiffre précédent. Si ce chiffre est également 9, alors la machine le remplace par 0 et se déplace vers la gauche, restant dans l'état q2 comme auparavant, car doit effectuer la même action et augmenter d’1 chiffre visible. Si la machine s'est déplacée vers la gauche et qu'il n'y a pas de numéro dans la cellule visible (mais qu'il y a « vide »), alors elle écrit 1 ici et s'arrête. Notez que pour un mot d'entrée vide notre tâche n'est pas définie, le MT peut donc se comporter comme on le souhaite sur ce mot. Dans notre programme, par exemple, si le mot d'entrée est vide, le MT s'arrête et donne la réponse 1. Ci-dessus, nous avons donné le programme dans son intégralité et dans son intégralité. Nous présentons maintenant l'enregistrement du programme sous une forme abrégée et plus visuelle, tandis qu'à droite nous donnons une brève explication des actions qui sont mises en œuvre dans les états correspondants de la machine : Λ q1,r,r,r,r,r, r,r,r,r,r, l,q2 sous le dernier chiffre q2 1,! 2,! 3,! 4,! 5,! 6,! 7,! 8,! 9,! 0,L,1,! nombre visible + 1 C'est ainsi que nous écrirons des programmes à l'avenir. Exemple 2 (analyse des symboles) A=(a,b,c). Déplacez le premier caractère d'un mot non vide P jusqu'à 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 étapes suivantes : 1. Mémoriser le premier caractère du mot P, puis effacer ce caractère. 2. Déplacez la machine vers la droite sous la première cellule vide au-delà de P et écrivez-y le symbole mémorisé. Nous savons déjà comment « courir » vers la droite grâce à l’exemple précédent. Mais comment vous souvenez-vous du premier personnage ? Après tout, en MT il n'y a pas d'autre périphérique de stockage que la bande, et mémoriser un symbole dans une cellule de la bande ne sert à rien : dès que la machine se déplace vers la gauche ou la droite de cette cellule, elle oubliera immédiatement ce symbole. Ce qu'il faut faire? La solution ici est d'utiliser différents états de la machine. Si le premier caractère est un, alors vous devez passer à l'état q2, dans lequel la machine 8
9 court vers la droite et écrit à la fin de a. Si le premier symbole était b, alors vous devez passer à l'état q3, où la même chose est faite, seul le symbole b est écrit à la fin. Si le premier symbole était c, alors on passe à l'état q4, dans lequel la machine ajoute le symbole c après le mot d'entrée. Par conséquent, nous corrigeons le premier symbole en transférant la machine vers différents états. Il s’agit d’une technique typique lors de la programmation sur MT. En tenant compte de ce qui précède, le programme sera comme ceci : a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, analyse du 1er caractère, suppression, branchement q2,r,r, r, a,! entrée a à droite q3,r,r,r, b,! entrée b à droite q4,r,r,r, c,! enregistrement c à droite Considérons le comportement de ce programme sur des mots d'entrée ne contenant pas plus d'un caractère. S'il y a un mot vide, qui est « mauvais » pour la tâche, le programme entrera en boucle ; la machine, étant dans l'état q1 et se retrouvant constamment sur des cellules vides, se déplacera sans cesse vers la droite. (Bien sûr, dans ce cas, le programme pourrait être arrêté, mais nous avons spécifiquement créé une boucle pour démontrer cette possibilité.) S'il y a exactement un caractère dans le mot saisi, alors la machine effacera ce caractère, déplacera une cellule vers la droite. et écrivez-y ce caractère : c c q1 q4 ! Ainsi, un mot d'un caractère déplacera simplement une cellule vers la droite. C'est acceptable. Après tout, les cellules de la bande ne sont pas numérotées, donc l'emplacement du mot sur la bande n'est en aucun cas fixé et le mouvement du mot vers la gauche ou la droite ne peut pas être remarqué. A cet égard, il n'est pas obligatoire que le mot de sortie soit nécessairement au même endroit où se trouvait le mot d'entrée ; le résultat peut être soit à gauche, soit à droite de cet endroit. Exemple 3 (comparer des caractères, effacer un mot) A=(a,b,c). Si les premier et dernier caractères du mot (non vide) P sont identiques, alors ne changez pas ce mot, sinon remplacez-le par un 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 saisi sans l'effacer. 2. Déplacez la machine sous le dernier symbole et comparez-la avec celui mémorisé. S’ils sont égaux, ne faites rien de plus. 3. Sinon, détruisez l'intégralité du mot d'entrée. Nous savons déjà comment mémoriser un symbole et comment déplacer la machine jusqu'au dernier symbole d'un mot à partir des exemples précédents. L'effacement du mot d'entrée est implémenté 9
10 en remplaçant tous ses symboles par le symbole Λ. Dans ce cas, 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. symbole avec a, ne sont pas égaux à q8 (effacer P) q4,r,r,r, L,q5 similaire pour le 1er symbole b q5, q8,!, q8 q6,r,r,r, L,q7 similaire pour le 1er caractère c q7, q8, q8,! q8 Λ,L, Λ,L, Λ,L,! effacer le mot entier en se déplaçant de droite à gauche Exemple 4 (supprimer un caractère d'un mot) A=(a,b). Supprimez le deuxième caractère du mot P, s'il y en a un. Solution. Il semblerait que ce problème soit simple à résoudre : il faut déplacer la machine sous la cellule avec le deuxième symbole puis effacer cette cellule : a b b a a b b a a b a Cependant, rappelez-vous 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, vous devez « compresser » le mot en déplaçant le premier caractère d'une cellule vers la droite. Pour ce faire, la machine doit revenir au premier symbole, le mémoriser 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, le « déplacement » initial 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 déplacer le premier symbole vers une cellule vide ou vers une cellule avec un symbole ? Par conséquent, on se souvient immédiatement du premier caractère, on l'efface et on écrit à la place du deuxième caractère : a b b a b b a a b a Sous la forme d'un programme pour MT, tout cela s'écrit ainsi : a b Λ q1 Λ,R,q2 Λ,R,q3, ! analyse et suppression du 1er caractère, branchement q2,! un,! un,! en remplaçant le 2ème caractère par un q3 b,!,! b,! remplacer le 2ème caractère par b Exemple 5 (compression de mots) A=(a,b,c). Supprimez la première occurrence du caractère a du mot P, s'il y en a une. Solution. Dans l'exemple précédent, nous avons déplacé un seul symbole vers la position à droite - 10
11 tomes. Dans cet exemple, dans une boucle nous allons déplacer vers la droite tous les caractères initiaux b et c du mot saisi vers le premier caractère a ou vers une cellule vide : b c b c b a a b b a a b c a a b c b a Le point central ici est de savoir comment déplacer le caractère x depuis la gauche cellule vers la cellule suivante, où se trouve un caractère y, de sorte que ce symbole y puisse ensuite être déplacé vers la cellule de droite ? Si par q x on désigne l'état dans lequel le symbole x doit être écrit dans la cellule visible, qui se trouvait auparavant dans la cellule de gauche, alors cette action peut être représentée comme suit : x y y z x z q x Pour ce faire, il est proposé de effectuer l'étape x,r,q y, qui combine les trois actions suivantes : d'abord, le symbole x extrait de la cellule de gauche est écrit dans la cellule visible ; deuxièmement, la machine se déplace vers la droite sous la cellule, dans laquelle il faudra alors écrire le symbole y nouvellement remplacé ; troisièmement, l'automate passe à l'état q y, dans lequel il effectuera cette saisie. La répétition de tels cycles dans une boucle entraînera un décalage vers la droite d'une position des caractères initiaux du mot d'entrée. Ce cycle devrait se terminer lorsque la cellule suivante contient le symbole a ou Λ (y=a ou y=λ), et au début du cycle on peut supposer que le symbole « vide » (x=λ) est déplacé à la place du premier symbole à 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 déplace-le vers la droite q2 b,!,r, b,r,q3 b,! q b : écrire b, déplacer le caractère précédemment visible vers la droite q3 c,! c,r,q2,r,c,! q c : écrire c, déplacer vers la droite un caractère précédemment visible. Dans ce programme, faire attention au cycle Λ,R,!, qui est exécuté dans la configuration
12 le premier caractère (vous n'êtes pas obligé de le supprimer à l'ancien emplacement pour l'instant), puis, en revenant à l'ancien emplacement, écrivez le caractère a : b c a b c a b b c a b a c a Déplacer un caractère d'une position vers la gauche est similaire à déplacer a caractère à droite, comme indiqué dans les deux exemples précédents, nous présentons donc 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 forcément le premier caractère du mot d'entrée, mais pas une cellule vide. a b c Λ q1,l,q2,l,q3,l,q4,! analyse du 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,! un,! un,! remplacez l'ancien 1er caractère par un exemple 7 (extension de mot) A=(a,b,c). Insérez le caractère a dans le mot P après la première occurrence du caractère c, s'il y en a un. Solution. On scanne le mot saisi 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, il faut faire de la place au caractère inséré a, pour lequel on décale 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 jusqu'au début du mot, puisque la machine se situe sous ce symbole. De plus, pour ne pas revenir ensuite à la position libérée, on commence ce décalage en écrivant a à la place du symbole trouvé c. Puisque ce décalage cyclique vers la gauche est mis en œuvre de la même manière que le décalage cyclique vers la droite de l'exemple 5, nous ne l'expliquerons pas, mais présenterons immédiatement le programme pour MT : a b c Λ q1,r,r, a,l,q4, moi,! à droite vers c, insérez a au lieu de c, déplacez 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éplacer b vers la droite q4 c,l,q2 c,l,q3,l, c,! déplacer c depuis la droite Exemple 8 (former un mot à un nouvel endroit) A=(a,b,c). Supprimez toutes les occurrences du caractère a de P. Solution. Les exemples précédents montrent qu'en TA, il est assez difficile de mettre en œuvre l'insertion de caractères dans les mots et la suppression de caractères dans les mots. Par conséquent, il est parfois plus facile de ne pas étendre ou compresser le mot d'entrée, mais de former une couche de sortie - 12
13 dans un autre endroit libre sur la bande. C'est exactement ce que nous ferons pour résoudre ce problème. Plus précisément, il est proposé d'effectuer les actions suivantes : 1. Nous allons construire le mot de sortie à droite du mot d'entrée. Pour distinguer ces mots, on les sépare 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 enregistrés 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 est de déplacer en boucle tous les caractères du mot d'entrée, sauf a, vers la droite au-delà du signe = dans le mot de sortie généré. Pour ce faire, nous analysons le premier caractère du mot saisi. 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 Encore une fois, nous revenons vers la gauche au symbole qui est devenu le premier dans le mot d'entrée et répétons les mêmes actions, mais par rapport à ce symbole (voir étapes 6 à 9). c = b = b = b c Cette boucle se termine lorsque nous revenons vers la gauche et voyons le signe = 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 dans le mot de sortie généré à droite. Vous devez effacer ce signe, vous déplacer vers la droite sous le mot de sortie et 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, on note qu'en plus des symboles a, b et c, en train de résoudre le problème, le signe = apparaît sur la bande, le tableau doit donc avoir une colonne pour ce signe. a b c = Λ q1,r,r,r, =,q2 écrire à droite le signe = q2,l,l,l,l,r,q3 à gauche au 1er caractère du mot q3 Λ,R, Λ ,R,q4 Λ, R,q5 Λ,R,! l'analyser et le supprimer, brancher q4,r,r,r,r, b,q2 en écrivant b à droite, en revenant à gauche (dans la boucle) q5,r,r,r,r, c,q2 en écrivant c la droite, revenant à gauche (faire du vélo) 13
14 Exemple 9 (fixation d'un endroit sur la bande) A=(a,b). Doublez le mot P en plaçant un signe = entre lui et sa copie. Par exemple : a a b a a b = a a b Solution. Ce problème se résout de manière similaire au précédent : on écrit le signe = à la fin du mot saisi, puis on revient au début du mot et dans une boucle on copie tous ses caractères (y compris a) dans des cellules vides du à droite : a a b a a b = a a b = a a b = 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 saisi à la position de ce caractère puis se déplacer vers la droite jusqu'au caractère suivant pour le copier. Mais comment savoir à quelle position du mot saisi vous devez revenir ? Par exemple, comment savons-nous dans notre exemple qu'après avoir copié le premier caractère a, nous devons revenir au premier caractère du mot saisi, et non au deuxième ou au troisième ? Dans le problème précédent, nous revenons toujours au premier caractère restant du mot saisi, mais maintenant nous enregistrons tous les caractères, il n'est donc pas clair quels caractères nous avons déjà copiés et lesquels nous n'avons pas encore copiés. Nous notons également que dans MT, les cellules de la bande ne sont en aucun cas numérotées et qu'il n'y a pas de compteurs dans 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 à laquelle nous devrons revenir plus tard ? Ce problème est généralement résolu comme ceci. Lorsque nous nous trouvons pour la première fois dans cette position, nous remplaçons le symbole qui s'y trouve avec son double par un nouveau symbole auxiliaire, et nous remplaçons différents symboles par des doubles différents, par exemple a par A et b par B. Après cela , nous effectuons certaines actions à d'autres endroits de la bande. Pour revenir ensuite à notre position, il suffit de retrouver la cellule de la bande où se trouve le symbole A ou B. Ensuite dans cette cellule on peut restaurer le symbole précédent si on n'a plus besoin de fixer cette position (c'était pour restaurer le symbole précédent que nous devions remplacer différents symboles pour différents doubles). Utilisons cette technique dans notre tâche en effectuant les étapes suivantes : 1. Comme déjà dit, 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 saisi (voir étape 2 ci-dessus). 3. Ensuite, remplacez le symbole visible a par un double A (voir étape 3 ci-dessous), « courez » vers la droite jusqu'à la première cellule libre et écrivez-y le symbole a (voir étape 4). Après cela, nous retournons à gauche dans la cellule avec le double A (voir. étape 5), restaurer le symbole a précédent et passer vers la droite au symbole suivant (voir étape 6). 14
15 a a b = A a b = A a b = a A a b = a a a b = a a A b = a a A b = a a a a B = a a b a a b = a a b 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 saisi. 4. Lorsque nous copions le dernier caractère du mot d'entrée et revenons à son double (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 a été complètement copié, le travail du MT doit donc être terminé. Compte tenu de tout ce qui a été dit, on obtient le programme suivant pour MT : a b = A B Λ q1,r,r, =,L,q2 mettre = à droite du mot q2,l,l,r,q3 à 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, récupération, au suivant. symbole Notez que dans ce programme vous pouvez vous débarrasser de l'état q6 si vous le combinez avec l'état q2, en fournissant dans q2 un retour à gauche à la fois à la cellule vide et aux symboles A et B : a b = A B Λ... q2 ,l,l ,l, a,r,q3 b,r,q3,r,q3 à gauche de Λ, A ou B Problèmes pour solution indépendante Notes : 1) Les problèmes ne considèrent que des entiers non négatifs, sauf indication contraire. 2) Par système numérique « unité », nous entendons l'écriture d'un entier non négatif à l'aide de bâtons ; il faut écrire autant de bâtons que la valeur du nombre ; par exemple : 2, 5, 0<пустое слово>. 1.1 A=(a,b,c). Ajoutez le symbole b (P bp) à gauche du mot P. 1.2 A=(a,b,c). Ajoutez les symboles bc (P Pbc) à droite du mot P. 1.3 A=(a,b,c). Remplacez un caractère sur deux dans le mot P par a. 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,5 A=(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éterminez si P est le 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 ne contient pas le caractère a, alors remplacez tous les caractères b de P par c, sinon, en réponse, donnez un mot composé d'un caractère a. 1,9 A=(a,b,0,1). Déterminer 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 un nombre binaire (un mot non vide composé uniquement des chiffres 0 et 1). Réponse : mot 1 (oui) ou mot A=(0,1). Considérant qu'un mot non vide P est l'enregistrement d'un nombre binaire, supprimez-en les zéros insignifiants, s'il y en a A=(0,1). Pour un mot non vide P, déterminez s'il s'agit d'une puissance de deux (1, 2, 4, 8,) en binaire. Réponse : mot 1 (est) ou mot A=(0,1,2,3). Considérant qu'un mot non vide P est 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 un nombre dans le système binaire, obtenir un nombre binaire égal à quadrupler le nombre P (par exemple :) A=(0,1). Considérant qu'un mot non vide P est un nombre dans le système binaire, obtenez un nombre binaire égal au quotient partiel 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 donnez la réponse a, sinon un mot vide A=(0,1,2). Considérant qu'un mot non vide P est un nombre dans le système de numérotation 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 une longueur impaire. Ne laissez dans P que le symbole du milieu A=(a,b,c). Si le mot P a une longueur paire, alors n’y laissez que la moitié gauche A=(a,b,c). Ajoutez son premier caractère à gauche du mot non vide P. 16
17 1.21 A=(a,b). Pour un mot non vide P, déterminez si son premier caractère apparaît à nouveau. Réponse : a (oui) ou le mot vide A=(a,b). Dans un mot non vide P, échangez ses premier et dernier caractères A=(a,b). Déterminez si P est un palindrome (mot inversé et symétrique) ou non. Réponse : a (oui) ou le mot vide A=(a,b). Remplacez chaque occurrence de a dans P par bb A=(a,b,c). Remplacez chaque occurrence de ab dans P par c A=(a,b). Doublez le mot P (par exemple : abb abbabb) A=(a,b). Doublez chaque caractère du mot P (par exemple : bab bbaabb) A=(a,b). Inversez le mot P (par exemple : abb bba) A=(0,1). En considérant un mot non vide P comme un nombre binaire, obtenez le même nombre, mais dans le système quaternaire. (Remarque : gardez à l'esprit qu'un nombre binaire peut avoir un nombre impair de chiffres.) 1,30 A=(0,1,2,3). Considérant qu'un mot non vide P est un nombre dans le système de numération quaternaire, obtenez un enregistrement de ce nombre dans le système binaire A = (0,1,2). Considérant qu'un mot non vide P est l'enregistrement d'un nombre positif dans le système numérique ternaire, réduisez ce nombre de A=( ). Considérant que le mot P est l'enregistrement d'un nombre dans le système de numérotation des unités, obtenez un enregistrement de ce nombre dans le système ternaire. (Recommandation : dans un cycle, il faut retirer un bâton du nombre « unité » et à chaque fois ajouter 1 au nombre ternaire, initialement fixé égal à 0.) 1,33 A=(0,1,2). Considérant qu'un mot non vide P est l'enregistrement d'un nombre dans le système numérique ternaire, obtenez un enregistrement de ce nombre dans le système unitaire. Soit le mot P ayant la forme suivante : (... (... n m où l'un des signes est +, /, ou, à gauche duquel sont indiqués n bâtons , et à droite il y a m bâtons. Effectuer l'opération correspondante dans le système de numérotation des unités (en réponse, donner le mot indiqué au à droite de la flèche) : a) addition : (... + (... (... (n 0, m 0) n m n+ m b) soustraction : (... (... (... (n m 0) n m n m c) multiplication : (... (... (... (n 0, m 0) n m n m d) division par un entier : ((... /... (... (n 0, m >0, k=n div m) n m k d) en prenant le reste : (... (... (... (n 0, m>0, k=n mod m) n m k 17
18 f) maximum : (... (... (... (n 0, m 0, k=max(n,m)) n m k f) minimum : (... (... (... ( n 0, m 0, k=min(n,m)) k n m 1,35 A=( ) En considérant le mot P comme un nombre dans le système d'unités, déterminez 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 seul bâton sinon A = ( ) En considérant le mot P comme un enregistrement du nombre n dans le système d'unités, obtenir dans le même système le nombre 2 n A = ( ) Soit le mot P un enregistrement du nombre 2 n (n=0, 1, 2,) dans le système d'unités. Obtenons le nombre n dans le même système. Soit P ayant la forme Q+R, où Q et R sont des mots non vides issus des symboles 0, 1 et 2. En traitant Q et R comme des nombres d'enregistrements dans le système numérique ternaire (éventuellement avec des zéros insignifiants), donnez comme réponse un enregistrement de la somme de ces nombres dans le même système ternaire. Soit P avoir la forme Q R, où Q et R sont des mots non vides issus des symboles 0, 1 et 2. Interpréter Q et R comme des enregistrements de nombres dans le système numérique ternaire (éventuellement avec des zéros insignifiants) et en supposant que Q R, donnez comme réponse un enregistrement de la différence de ces nombres dans le même système ternaire. Soit P avoir la forme Q=R, où Q et R sont des mots quelconques des symboles a et b. Donnez la réponse a si les mots Q et R sont identiques, et un mot vide dans le cas contraire. Soit P de la forme Q=R, où Q et R sont des mots non vides des caractères 0 et 1. Traiter Q et R comme notations de nombres binaires (éventuellement avec des zéros insignifiants), donner comme réponse le mot 1 si ces nombres sont égaux, et sinon le mot 0. Soit P sous la forme Q>R, où Q et R sont des mots non vides de les symboles 0 et 1. Traiter Q et R comme des enregistrements de nombres binaires (éventuellement avec des zéros insignifiants), sortir le mot 1 comme réponse 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 b caractères, alors affichez la réponse a ; s'il y a moins de caractères a que de b caractères, affichez la réponse b ; sinon, affichez un mot vide comme réponse. 2. Algorithmes de Markov normaux Cette section discute des problèmes de construction d'algorithmes de Markov normaux. Une brève description de ces algorithmes est donnée, les principales méthodes de compilation sont expliquées avec des exemples et des problèmes sont proposés pour une solution indépendante. 18
19 2.1 Brève description des algorithmes de Markov normaux Substitutions Une caractéristique intéressante des algorithmes de Markov normaux (NAM) est qu'ils n'utilisent qu'une seule action élémentaire, la substitution, qui est définie comme suit. Une formule de substitution est une notation de la forme α β (lire « remplacer α par β »), où α et β sont des mots quelconques (éventuellement vides). Dans ce cas, α est appelé le côté gauche de la formule et β est le côté droit. La substitution elle-même (en tant qu'action) est spécifiée par la formule de substitution et appliquée à un certain mot P. L'essence de l'opération est que dans le mot P, la partie qui coïncide avec le côté gauche de cette formule (c'est-à-dire avec α) est trouvé et il est remplacé 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 la substitution n'est pas effectuée. 2. Si le côté gauche α 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 β : P x α y α z R x β y α z 3. Si le le côté droit de la formule de substitution est un mot vide , alors la substitution α revient à supprimer la partie α de P (notons au passage que dans les formules de substitution il n'est pas d'usage de désigner un mot vide de quelque manière que ce soit) : P x α y R x y 4. Si un mot vide est indiqué à gauche de la formule de substitution, alors la substitution β se réduit, 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 avec une queue (a). Une formule avec une flèche régulière est appelée formule régulière, et une formule avec une flèche avec une queue est appelée formule finale. La différence entre eux est expliquée ci-dessous. Écrire un algorithme sous forme de NAM signifie présenter un tel ensemble de formules. Règles d'exécution de NAM Tout d'abord, on donne un mot d'entrée R. L'endroit exact où il est écrit n'a pas d'importance, cette question n'est pas spécifiée dans NAM. Le travail du NAM se résume à effectuer une séquence d’étapes. A chaque étape, les formules de substitution incluses dans le NAM sont revues 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 le côté gauche est inclus dans P. 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 celui d'origine et la même procédure lui est appliquée, c'est-à-dire : les formules sont à nouveau parcourues de haut en bas en commençant par celle du haut 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 : R R R Une attention particulière doit être portée payé au fait qu'à chaque étape de la formule dans NAM, ils sont toujours visualisés à partir de la toute première. Précisions nécessaires : 1. Si à l'étape suivante la formule habituelle (α β) a été appliquée, alors le travail du NAM continue. 2. Si à l'étape suivante la formule finale (α a β) a été appliquée, 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 habituelles et finales ne se manifeste que par le fait qu'après l'application de la formule habituelle, le travail du NAM continue et après la formule finale, il s'arrête. 3. Si à l'étape suivante aucune formule n'est applicable au mot actuel, alors dans ce cas, le travail du NAM s'arrête et le mot actuel 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 au travail du NAM. Dans les deux cas, nous disons que NAM est appliqué au mot d'entrée. 20
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. Branche de Chouïa
ADDITION Ajouter 1 à un nombre signifie obtenir le nombre qui suit 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. SOUSTRAIT Soustraire 1 d'un nombre signifie
Problèmes et solutions du tour de qualification de l'Olympiade DMIT 2014-2015 Tous les problèmes, manipulateurs et solutions sont à la disposition des participants sur le site de l'Olympiade. Toutes les tâches proposées ont été évaluées avec le même nombre de points. Graphiques.
Machine de Turing 1 La machine de Turing est un concept mathématique, pas une véritable machine informatique. MT est un modèle mathématique d'un appareil informatique. MT a été proposé par Alan Turing en 1936
Résoudre les problèmes sur la machine de Turing en ligne >>> Résoudre les problèmes sur la machine de Turing en ligne Résoudre les problèmes sur la machine de Turing en ligne Le contenu de la cellule peut changer, vous pouvez y écrire un autre symbole ou l'effacer
Systèmes numériques De nos jours, les gens rencontrent constamment des chiffres. Depuis l'enfance, nous connaissons tous la notation généralement acceptée des nombres à l'aide de chiffres arabes. Cependant, cette méthode d'enregistrement était loin d'être utilisée
Algorithme implémenté Nous utilisons la variante suivante de l'algorithme euclidien 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, les solutions contiennent des images de leurs interfaces)
Chapitre B. Leçon d'arithmétique informatique B3. Arithmétique binaire Voyons comment vous avez réalisé les exercices de la leçon B2. Voici leurs solutions. Exercices B2-2 a) Le tableau de placement des poids ressemble à ceci : en numérotation
Leçon 23 Dans les conditions des problèmes, M, x signifient respectivement une description de la machine de Turing et le mot d'entrée dans le format qui a été introduit dans le cours (et écrit dans le projet de manuel). Problème 23.1. Prouve-le
Section 6. Théorie des algorithmes. Concept informel d'un algorithme, ses principales caractéristiques et propriétés. Alphabet, mots, algorithme dans l'alphabet. Des algorithmes tout à fait équivalents. Définition d'un algorithme normal (algorithme
SYSTÈMES NUMÉRIQUES DE POSITION Il existe de nombreuses façons de représenter les nombres. Dans tous les cas, un nombre est représenté par un symbole ou un groupe de symboles (un mot) d'un alphabet. Nous appellerons ces symboles
Devoirs pour l'étape de qualification de 11e année. Premier tour 1. Codage des informations. Systèmes numériques (2 points) [Permutations] Combien y a-t-il de nombres hexadécimaux à trois chiffres pour lesquels il y aura les deux
Résoudre des problèmes sur le thème « Représenter des nombres dans un ordinateur » Types de problèmes : 1. Nombres entiers. Représentation des nombres au format virgule fixe. 2. Nombres fractionnaires. Représentation des nombres au format virgule flottante.
1. Chevaliers et valets. Schéma logique - 1. Problèmes et solutions de l'épreuve à temps plein des Jeux olympiques Dmitry-2017-2018 Quatre personnes sont assises à une table ronde. Chacun d'eux est soit un chevalier, soit un menteur. Les chevaliers parlent toujours seulement
Systèmes numériques Un système numérique est une manière d'écrire des nombres en utilisant un ensemble donné de caractères spéciaux (chiffres). En informatique, on utilise des systèmes de numérotation positionnelle dans lesquels la valeur d'un chiffre est
CONFÉRENCE 3. Algorithmes de traitement de tableaux unidimensionnels. Objectif du cours : Introduction au concept de tableau. Acquérir des compétences dans la construction d'algorithmes destinés au traitement de tableaux unidimensionnels. 6. Algorithmes
Version de démonstration de l'examen d'État unifié 2019, tâche 6 Un nombre naturel N est fourni à l'entrée de l'algorithme. L'algorithme construit un nouveau nombre R à partir de celui-ci comme suit. 1) Un enregistrement binaire du nombre N est construit. 2) À cet enregistrement
Introduction aux systèmes numériques Vylitok Le système numérique est un moyen d'enregistrer des nombres à l'aide d'un ensemble donné de caractères spéciaux (chiffres). Il existe des systèmes de numérotation positionnels et non positionnels. En non positionnel
Partie III Langues, grammaires, automates 137 Chapitre 10 Langages et automates finis 10.1 Langage de Dick Comme nous le savons, les structures régulières par parenthèses sont énumérées par des nombres catalans. Écrivons toutes les parenthèses correctes
Étape municipale de l'Olympiade panrusse pour les écoliers en informatique Moscou, 0 décembre. Tâches pour les classes 7 et 8 Chaque tâche reçoit 0 point. La note finale est donnée 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 un article dans le Journal of Symbolic Logic, « Finite Combinatorial Processes, Formulation ! (son
Lycée de physique et de mathématiques Yugra VP Chuvakov Problème C6 (Théorie des nombres à l'examen d'État unifié) Manuel pédagogique et méthodologique Khanty-Mansiysk 0 VP Chuvakov Problème C6 (Théorie des nombres à l'examen d'État unifié) : Manuel pédagogique et méthodologique, - Khanty-Mansiysk,
9 ANNÉE 1. Dans l'une des cellules de papier à carreaux infinis, il y a un robot, qui peut recevoir les commandes suivantes : vers le haut (le robot se déplace vers la cellule adjacente par le haut) ; vers le bas (le robot se déplace vers
Systèmes numériques Un système numérique est une manière d'écrire des nombres en utilisant un ensemble donné de caractères spéciaux (chiffres). Il existe des systèmes de numérotation positionnels et non positionnels. Dans les systèmes non positionnels, le poids
Systèmes numériques Un système numérique est une manière de décrire les nombres en utilisant les signes d'un certain alphabet selon des règles connues. Systèmes de numérotation positionnelle Dans un système de numérotation positionnelle, la valeur d'un chiffre dépend
K. Polyakov, 009-06 6- (niveau de base, durée 4 min) Sujet : Recherche d'un algorithme de durée minimale pour l'interprète. Ce qu'il faut savoir : l'artiste interprète ou exécutant est une personne, un groupe de personnes, un animal, une machine ou tout autre objet,
Cours 5 Bases de la présentation de l'information dans les machines numériques Systèmes de numérotation positionnelle Un système de numérotation est un ensemble de techniques et de règles pour écrire des nombres dans des signes numériques. Tout prévu
Éléments de la théorie de la complexité Machine de Turing Alan Turing (23/06/1912-07/06/1954) (Alan Mathison Turing) Mathématicien, logicien, cryptographe anglais. En 1936, il proposa une « machine de Turing » informatique abstraite,
Ministère de l'Éducation et des Sciences de la Fédération de Russie Établissement d'enseignement public de formation professionnelle de la Fédération de Russie « Université d'État de Rostov » M. E. Abrahamyan
10e ANNÉE 1. Les nombres réels satisfont les relations : Trouver tous les triplets possibles de nombres, où Solution. Notez que notons et soustrayons ces égalités les unes des autres, nous obtenons Supposons que toutes
Annexe à l'article Gorbunov K.Yu., Lyubetsky V.A. « Algorithme linéaire pour une restructuration minimale des structures » Preuve du lemme 3. Un bloc délimité de part et d'autre par des gènes communs est appelé rigide, semi-rigide
Annexe 1 Travaux pratiques du chapitre 2 « Représentation d'informations sur un ordinateur » Travaux pratiques du paragraphe 2.1 Exemple 2.1. Présentez les nombres 2466,675 10, 1011,11 2 comme une extension des puissances de la base.
Lycée de physique et de mathématiques par correspondance "Avangard" E. N. Filatov ALGEBRE 8 Manuel expérimental Partie 1 MOSCOU 2016 CONTENU 1. Divisibilité. 2. Pair impair 3. Ensembles. 4. Tâches amusantes. 5. Combinatoire
Cahier de problèmes en informatique pour élève(s) de 11e classe de physique et de mathématiques du secondaire 36 à Vladimir Partie II 2016-2017 2 1. Algorithmisation. 1.1 Quelques opérations sur deux arbitraires
Thème 7. Pré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é nécessaire pour distinguer deux événements équiprobables.
I. V. Yakovlev Matériel sur les mathématiques MathUs.ru Sommaire 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 Département d'algèbre et de mathématiques discrètes Algèbre et géométrie pour ingénieurs physiciens
Chapitre 5 Éléments de la théorie des algorithmes 31 Clarification du concept d'algorithme Mots clés : algorithmique théorie des algorithmes exécuteur universel Machine de Turing Post machine algorithme de Markov normal Pourquoi est-ce nécessaire
Résoudre des problèmes sur le thème « Représenter des nombres dans un ordinateur ». Types de tâches. 1. Nombres entiers. Représentation des nombres au format virgule fixe. 2. Nombres fractionnaires. Représentation des nombres au format flottant
A. Shen Jeux et stratégies du point de vue mathématique, MCSME Jeux simples et classement des positions Il y a 12 matchs sur la table. Les joueurs à tour de rôle peuvent jouer 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 notation de la forme P Q, où P et Q sont des mots de l'alphabet A. Final
CONFÉRENCE 2. Algorithmes de structure cyclique. Objectif du cours : Introduction au concept d'algorithme de structure cyclique. Acquérir des compétences dans la construction d'algorithmes pour une structure cyclique. 5. Algorithmes cycliques
Cours de mathématiques. Vol. TMM-1 Yu. V. Chebrakov THÉORIE DES MATRICES MAGIQUES Saint-Pétersbourg, 2010 UDC 511+512 BBK 22 Ch345 RÉVISEURS : Docteur en Sciences Physiques et Mathématiques, Professeur Saint-Pétersbourg. technologie.
Travaux pratiques. Formulaires pour représenter des informations numériques sur un ordinateur. Partie I. Systèmes numériques. Un système numérique est une manière de représenter n’importe quel nombre à l’aide d’un alphabet.
Institut de physique et de technologie de Moscou Faculté d'innovation et de hautes technologies Logique mathématique et théorie des algorithmes, automne 2018 Séminaire 1 : un langage pour enregistrer des énoncés formels, avec des solutions à certains
Cours 16. Machine de Turing universelle Mathématiques discrètes, École supérieure d'économie, Faculté d'informatique (automne 2014, printemps 2015) La propriété la plus importante des fonctions calculables est l'existence d'une fonction calculable universelle
16 (niveau avancé, temps min) Thème : Codage numérique. Systèmes numériques. Ce que vous devez savoir : les principes de codage des nombres dans les systèmes de numérotation positionnelle pour convertir un nombre, disons 15, 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 un ensemble de mots à partir des lettres a et b, de laquelle tous les mots spécifiés par l'expression régulière ont été supprimés
Il est tout à fait possible de gagner de l’argent « en étant allongé sur le canapé » si l’on connaît les principes du travail à distance.
Perception humaine de l'information Types d'informations en informatique par signification sociale
Machine de Turing et algorithmes de Markov
Qui sont les designers UX et que font-ils ?
Pourquoi est-ce nécessaire et qu’est-ce qu’un crash test ?
Gta 5 où mettre les mods. Mods avec extensions .asi et .ini
IDEF0 : modélisation fonctionnelle des processus métiers