Exemples de composition de machines de Turing. Calculabilité correcte des fonctions sur une machine de Turing
La machine de Turing (MT) est un interprète abstrait (machine informatique abstraite).
Les combinaisons d'algorithmes sont le nom qui a été établi pour un certain nombre de méthodes spécifiques permettant de construire de nouveaux algorithmes à partir de plusieurs algorithmes donnés.
Les théorèmes sur les combinaisons d'algorithmes constituent une section importante de la théorie générale des algorithmes. Une fois éprouvés, ils permettent de vérifier ultérieurement la faisabilité d’algorithmes complexes et encombrants sans pour autant écrire les circuits qui les définissent.
Les combinaisons d'algorithmes pour une machine de Turing sont décrites par des opérations sur des machines de Turing.
1. Opération de composition.
Soient M 1 et M 2 des machines de Turing ayant le même alphabet externe A« (a 0 ,a 1 ,...,a p ). Notons respectivement les ensembles de leurs états par Q1 " (q 0 ,q 1 ,...,q n ) et Q2 " (q 0" ,q 1" ,...,q m" ).
Définition.
Une composition de machines M 1 et M 2 est une machine notée M=M 1 × M 2 dont le programme possède un alphabet A, un ensemble d'états Q" (q 0,q 1,...,q n,q n+1,... ,q n+m) et est obtenu à partir des programmes des machines M 1 et M 2 comme suit : partout dans le programme de la machine M 1, où se trouvent des « triples » de symbole q 1 ( l'état final de la machine M 1), il est remplacé par le symbole q 0" (état initial de la machine M 2) ; tous les autres symboles dans les programmes des machines M 1 et M 2 restent inchangés (au final, tout cela reste à renuméroter tous les états de la machine M : (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
La composition commence à "fonctionner" comme une machine M 1, mais dans les cas où la machine M 1 doit s'arrêter, elle passe au programme de la machine M 2, en raison du remplacement de q 1 par q 0". Évidemment, l'opération de composition est associative, mais non commutative.
Son fonctionnement est équivalent au fonctionnement séquentiel des machines T1 et T2.
La figure montre une composition de machines de Turing qui implémente l'opérateur de superposition pour n=1 et m=1.
Image 1.
Définition.
Une itération d'une machine de Turing M sera appelée une machine
2. Opération de branchement.
Soient M 1, M 2 et M 3 des machines de Turing ayant le même alphabet externe A" (a 0,a 1,...,a i,...,a j,...,a p) et, par conséquent, des ensembles de états : Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. . ,ql" ).
Définition.
Le résultat de l'opération de branchement sur les machines de Turing M 1 , M 2 et M3 est appelé machine de Turing M dont le programme est obtenu à partir des programmes des machines M 1 , M 2 et M 3 comme suit : le programme de la machine M1 est écrite, puis les programmes des machines M 2 et M 3 sont attribués. Si dans l'état final q 1 de la machine M1 le symbole a i est observé, alors le contrôle est transféré à la machine M 2, c'est-à-dire le symbole q 1 est remplacé par le symbole q 0" et la machine M 2 commence à fonctionner. Si dans l'état final q 1 de la machine M 1 le symbole a j est observé, alors le contrôle est transféré à la machine M 3, c'est-à-dire que le symbole q 1 est remplacé par le symbole q 0" et la machine M 3 commence à fonctionner. Tous les autres symboles des programmes des machines M 1 et M 2 restent inchangés. La machine M termine son travail dans l'état final q 1 (en conclusion, il reste à effectuer une renumérotation de bout en bout des états de la machine M).
Le résultat d'une opération de branchement sur les machines de Turing M 1, M 2 et M3 est noté comme suit :
Pour les machines de Turing à deux lettres (machines de Turing avec un alphabet à deux lettres), l'opération de branchement sur les machines de Turing arbitraires M1, M2 et M3 est notée comme suit :
ceux. si lorsque la machine M1 fonctionne dans l'état q 1, le symbole a 0 est observé, alors le contrôle est transféré à la machine M2, sinon - à la machine M3.
3. Opération en boucle.
Soit M une machine de Turing d'alphabet A« (a 0 ,a 1 ,...,a p ) et d'ensemble d'états Q« (q 0 ,q 1 ,...,q n ).
Définition.
Le résultat de l'opération de bouclage sera appelé une machine de Turing, notée (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,...,n)
dont le programme est obtenu à partir du programme de la machine M en remplaçant le symbole q 1 dans le conséquent de la commande q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. .p, avec le symbole q s .
2.4 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.
À titre d'exemple d'une telle équivalence, considérons la réduction de n'importe quel MT à un MT fonctionnant sur une bande semi-infinie.
Théorème: Pour toute machine de Turing, il existe une machine de Turing équivalente fonctionnant sur une bande semi-infinie.
Preuve:
Considérons la preuve de Yu. G. Karpov. La preuve de ce théorème est constructive, c'est-à-dire que nous donnerons un algorithme grâce auquel pour toute machine de Turing, une machine de Turing équivalente avec la propriété déclarée peut être construite. Tout d'abord, nous numérotons aléatoirement les cellules de la bande de travail MT, c'est-à-dire que nous déterminons un nouvel emplacement d'informations sur la bande :
Image 1.
Ensuite on renumérote les cellules, et on supposera que le symbole « * » n'est pas contenu dans le dictionnaire MT :
Image 1.
2.5 Calculabilité et décidabilité de Turing
Il a été prouvé ci-dessus que les classes de fonctions calculables à l'aide de fonctions récursives, de machines de Turing ou d'algorithmes de Markov normaux coïncident. Ceci permet de considérer la notion d’« algorithme computationnel » invariante à la méthode de description. Les différences ne sont observées que dans l'utilisation d'objets algorithmiques. Si pour les fonctions récursives les objets sont des nombres et des fonctions numériques et que le processus de calcul est spécifié par les opérateurs de superposition, de récursivité, de minimisation et d'itération, alors pour les machines de Turing, ces objets sont des symboles des alphabets de la mémoire externe et interne, et le calcul Le processus est précisé par un protocole utilisant la sortie, la transition et le mouvement de la tête. Pour un algorithme de Markov normal, ces objets sont des mots ou des séquences de symboles, et le processus de calcul est spécifié par des règles ou des produits de substitution qui modifient la composition et la structure de la séquence originale de symboles jusqu'au résultat souhaité.
Une fonction arithmétique (numérique) est une fonction dont la plage de valeurs est un sous-ensemble de l'ensemble N, et son domaine de définition est un élément de l'ensemble N.
Pour les problèmes algorithmiques, une situation typique est celle où vous devez trouver un algorithme pour calculer une fonction numérique f(x 1, x 2, ..., x n), en fonction des valeurs entières des arguments x 1, x 2 , ..., xn.
Nous appelons une fonction f:N n →N calculable s'il existe un algorithme qui permet à tout ensemble de valeurs de ses arguments de calculer la valeur de la fonction (ou d'indiquer que la fonction n'est pas définie sur un ensemble donné). Étant donné que la définition d'une fonction calculable utilise le concept intuitif d'un algorithme, le terme « fonction calculable intuitive » est souvent utilisé à la place du terme « fonction calculable ». Ainsi, un problème de masse a une solution si la fonction arithmétique correspondant au problème est intuitivement calculable.
Une fonction f(x 1 , x 2 , …, x n) est dite effectivement calculable si pour des valeurs données k 1 , k 2 , …, k n arguments on peut trouver la valeur de la fonction f(k 1 , k 2 , …, k n) en utilisant une procédure mécanique existante (algorithme).
Au lieu de clarifier le concept d’algorithme, nous pouvons envisager de clarifier le concept de « fonction calculable ». Habituellement, ils procèdent selon le schéma suivant :
1. Une classe de fonctions précisément définie est introduite.
2. Assurez-vous que toutes les fonctions de cette classe sont calculables.
3. Acceptez l'hypothèse (thèse) selon laquelle la classe de fonctions calculables coïncide avec la classe de fonctions introduite.
Une fonction est dite calculable s’il existe un algorithme qui la calcule. La « calculabilité » est l'un des concepts de base de la théorie des algorithmes, invariant par rapport à la fonction et à l'algorithme calculés. La différence entre une fonction calculable et un algorithme est la différence entre la description de la fonction et la façon dont elle calcule ses valeurs étant donné les valeurs des arguments indépendants.
La thèse de Turing. Tout algorithme intuitif peut être implémenté à l’aide d’une machine de Turing.
Il découle de la thèse de Turing que si des problèmes algorithmiques surviennent, ils doivent être résolus sur la base de la construction de machines de Turing, c'est-à-dire d'un concept d'algorithme suffisamment formalisé. De plus, dans les problèmes algorithmiques, nous ne parlons souvent pas de la construction d'un algorithme, mais de la calculabilité de certaines fonctions spécialement construites.
Il convient de noter que dans ces cas, il suffit d'utiliser l'alphabet (0,|), où 0 est le caractère vide. Par exemple, les nombres naturels, dont 0, sont codés dans cet alphabet comme suit : 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 fois). Une fonction n-locale numérique partielle f(x1, x2, ..., xn) est appelée calculable de Turing s'il existe une machine M qui la calcule dans le sens suivant : 1. Si l'ensemble des valeurs d'argument
LE PROBLÈME DE L’AUTO-APPLICABILITÉ
Selon la définition d'une machine de Turing, il s'agit d'un triple T=
P : qi un un J un ® qr un comme un St un , une = 1, 2, …, k , Où S1-R, S2-L, S3- C . (*)
Dans ce cas, nous pouvons supposer qu'il existe des alphabets communs Un 0 Et Q0, dans lequel les caractères sont écrits un Et q pour toutes les machines de Turing. Puis les symboles qi un, un J un, qr un, comme un, St un sont des symboles des alphabets Un 0 Et Q0.
Cette approche permet de numéroter toutes les machines de Turing, c'est-à-dire que chaque machine se voit attribuer un certain numéro (code) unique à cette machine, par lequel elle pourrait être distinguée des autres machines. Ici, nous considérerons l'une des méthodes de numérotation.
Numérotation godélienne des machines de Turing. Laisser p1, p2, p3 , ... - une séquence de nombres premiers classés par ordre croissant, par exemple 2, 3, 5, 7, 11, 13, ...
Numéro de machine de Turing avec programme (*) numéro appelé
NT) = .
Exemple
Une machine qui implémente une fonction S(X)= x + 1 , a un programme dans l'alphabet {0, } . Le numéro de ce programme, compte tenu du fait que un 0 = 0 , un 1= | il y aura un numéro :.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Évidemment, tous les nombres naturels ne sont pas des nombres de machine de Turing. En revanche, si n – le numéro d'une certaine machine, en alphabets généraux, alors son programme peut être restauré de manière unique à partir de ce numéro.
Voiture T, applicable au mot n(T)(c'est-à-dire au code de votre propre numéro), dit auto-applicable .
Il est possible de construire à la fois des machines auto-applicables et des machines non auto-applicables. Par exemple, la machine de l'exemple donné est auto-applicable. Voiture T, qui n'a pas de symbole d'arrêt dans les parties droites du programme (dans le corps du tableau), n'est applicable à aucun mot, et donc au mot n(T).
Problème d'auto-applicabilité est la suivante : indiquer un algorithme qui, étant donné n'importe quelle machine de Turing, déterminerait s'il est auto-applicable ou non.
Selon la thèse de Turing, un tel algorithme devrait être recherché sous la forme d'une machine de Turing. Cette machine devrait être applicable aux codes numériques de toutes les machines de Turing et, en fonction du résultat du traitement des codes des machines testées, aurait des configurations finales différentes.
Laissez, par exemple, cette voiture T appliqué au code n(T. * ) . Si la voiture T * auto-applicable, puis la configuration finale de la machine T ressemble à un" q 0 | B", et si la voiture T * n'est pas auto-applicable, alors la configuration finale de la machine T ressemble à un" q 0 0B ". Ici a", B", a", B"- mots.
Théorème Le problème de l’auto-applicabilité est algorithmiquement indécidable, c’est-à-dire qu’il n’existe aucune machine de Turing qui résolve ce problème dans le sens ci-dessus.
Il découle du théorème qu'il n'existe pas d'algorithme général qui résout le problème de l'auto-applicabilité. Dans des cas particuliers, de tels algorithmes peuvent exister.
Utilisons les résultats de ce théorème pour prouver l'indécidabilité du problème de l'applicabilité au mot initial.
Le problème de l'applicabilité au mot initial est la suivante : créer un algorithme qui, selon la machine T et le mot X installerait, machine applicable T d'ailleurs X ou pas (sinon il y a un problème d'arrêt).
En termes de machines de Turing, similaire à la formulation du problème d'auto-applicabilité, ce problème se formule ainsi : est-il possible de construire une machine qui serait applicable à tous les mots de la forme n(T)0 X , Où T machine arbitraire, X – un mot arbitraire, et si la machine T applicable au mot X un" q 0 |B" , et si la voiture T ne s'applique pas au mot X , conduirait à la configuration finale un" q 0 0B" . Ici un B" Et un B"- des mots arbitraires.
Théorème Le problème de l’applicabilité au mot initial est algorithmiquement indécidable, c’est-à-dire qu’il n’existe aucune machine de Turing qui résolve ce problème dans le sens ci-dessus.
Comme indiqué ci-dessus pour le problème de l’auto-applicabilité, la première étape préliminaire est la numérotation. Par conséquent, ce problème est systématiquement examiné et résolu ci-dessous pour les algorithmes et ses trois principaux types de modèles algorithmiques.
Numérotation des algorithmes
La numérotation des algorithmes joue un rôle important dans leur recherche et leur analyse. Puisque tout algorithme peut être spécifié comme un mot fini (représenté comme une séquence finie de symboles d’un alphabet donné) et que l’ensemble de tous les mots finis dans un alphabet fini est dénombrable, alors l’ensemble de tous les algorithmes est également dénombrable. Cela signifie l'existence d'une correspondance biunivoque entre l'ensemble des nombres naturels et l'ensemble des algorithmes, c'est-à-dire la possibilité d'attribuer un numéro à chaque algorithme.
La numérotation des algorithmes est également la numérotation de toutes les fonctions calculables algorithmiquement, et toute fonction peut avoir un nombre infini de nombres.
L'existence de la numérotation permet de travailler avec des algorithmes de la même manière qu'avec des nombres. La numérotation est particulièrement utile dans l’étude des algorithmes qui fonctionnent avec d’autres algorithmes.
Soit un certain problème de masse avec un ensemble d'objets initiaux X et un ensemble d'objets souhaités Y. Pour qu'une solution au problème de masse existe, il faut que les éléments des ensembles X et Y soient des objets constructifs. Par conséquent, les éléments de ces ensembles peuvent être numérotés par des nombres naturels. Soit x∈ X un objet initial, notons son numéro par n(x). Si dans un problème de masse pour l'objet d'origine x il est nécessaire d'obtenir l'objet souhaité y∈ Y avec le nombre n(y), alors nous définissons une fonction arithmétique f : Nn →N telle que f(n(x))=n (o).
Comme exemple de construction de fonctions arithmétiques pour des problèmes de masse, considérons les problèmes de masse.
1. Si un tableau ] de nombres naturels est donné, alors on peut lui attribuer l'entier naturel 2x1, 3x2,... p(n)xn, où p(n) est le nième nombre premier. Prenons un exemple d'un tableau de longueur 5 :
] 2x13x25x37x411x5.
Cette numérotation définit la fonction arithmétique f (par exemple, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Tout nombre rationnel possède un nombre naturel. La numérotation de l'ensemble des objets requis du problème est triviale :
(« oui », « non ») a (1, 0). Pour un problème de masse donné, vous pouvez construire une fonction arithmétique d'un argument en utilisant la technique de l'exemple précédent, ou vous pouvez considérer une fonction de trois arguments (trois nombres d'éléments du triplet original).
3. La numérotation des textes de programme peut être effectuée comme suit : tout programme peut être perçu comme écrivant un nombre dans le système de numérotation 256-ary (si des caractères de table ASCII ont été utilisés pour enregistrer le programme).
Le passage d'un problème de masse à une fonction arithmétique permet de réduire la question de l'existence d'une solution à un problème de masse à la question de l'existence d'un moyen efficace de calculer les valeurs d'une fonction arithmétique à partir de son argument ( arguments).
Numérotation des ensembles de nombres
Dans la théorie des algorithmes, s'est répandue une technique qui permet de réduire l'étude des fonctions de plusieurs variables à l'étude des fonctions d'une variable. Il est basé sur la numérotation d'ensembles de nombres de sorte qu'il existe une correspondance bijective entre des ensembles de nombres et leurs nombres, et les fonctions qui déterminent à partir d'un ensemble de nombres son numéro et à partir du nombre l'ensemble de nombres lui-même sont généralement récursives. Par exemple, pour une fonction contenant deux variables indépendantes (x, y), ce mappage h(x, y) pourrait ressembler à ceci :
Image 1.
Supposons que les paires (x, y) forment un ensemble partiellement ordonné N(2). Si h(x, y) = n, alors il existe une application inverse : x = h -1 1 (n) et y= h -1 2 (n), c'est-à-dire h(h -1 1 (n), h -1 2 (n)) = n. Cela permet de calculer le nombre n pour n'importe quel couple (x, y) et, à l'inverse, d'utiliser le nombre n pour calculer les valeurs de x et y :
A l'aide de ces règles, vous pouvez calculer la numérotation des triplets h 2 (x, y, z) = h(h(x, y), z) = n et, à l'inverse, par le numéro du triple - les valeurs de x, y, z. Par exemple, si h 2 (x, y, z) = n, alors z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ) , h -1 2 (n)). Les triples (x, y, z) forment un ensemble partiellement ordonné N(3). De même, pour un nombre arbitraire de nombres on a :
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Si h n-1 (x1, x2,…, xn)=m, alors xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ...................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
Ayant la numérotation des ensembles d'ensembles N (1) , N (2) ,..., N (i) ,..., N(n, où N (i) est l'ensemble des ensembles (i) de nombres, il est possible d'établir une numérotation combinée d'ensembles arbitraires de nombres M = N (1) N (2) ... N (i) .. N(n) , où M N. Pour tout n N on a h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Si h(x ,1x ,2..., x)n = m, alors h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. En utilisant les formules ci-dessus, vous pouvez restaurer les valeurs de x1, x2,…, xn.
Informations connexes.
Définition, fonctionnement et méthodes de spécification d'une machine de Turing
Une machine de Turing est comprise comme une certaine machine hypothétique (abstraite) composée des parties suivantes (Fig. 3.1.)
1) une bande infinie dans les deux sens, divisée en cellules, dans chacune desquelles un seul caractère de l'alphabet peut être écrit, ainsi que le caractère vide l ;
2) un dispositif de commande (tête de travail), qui à tout moment peut se trouver dans l'un des états de l'ensemble. Dans chaque état, le chef est placé en face de la cellule et peut y lire (réviser) ou y écrire une lettre de l'alphabet UN.
Riz. 3.1. Machine de Turing
Le fonctionnement du MT consiste en une séquence d'étapes élémentaires (cycles). Chaque étape effectue les actions suivantes :
1. la tête de travail lit (examine) le symbole ;
2. en fonction de son état et du symbole surveillé, la tête produit un symbole et l'écrit dans la cellule surveillée (éventuellement =) ;
3. la tête bouge d'une cellule vers la droite (R), gauche (L) ou reste en place (E);
4. La tête entre dans un autre état interne. (peut-être =).
L'état est appelé initial et final. En entrant dans l'état final, la machine s'arrête.
L’état complet de MT est appelé configuration . Il s'agit de la répartition des lettres entre les cellules de la bande, de l'état de la tête de travail et de la cellule surveillée. Configuration intacte t s'écrit sous la forme : , où est le sous-mot à gauche de la cellule surveillée, est la lettre dans la cellule surveillée, est le sous-mot à droite.
La configuration initiale et la configuration finale sont dites standards.
Il existe 3 manières de décrire le fonctionnement de MT :
Système de commande du formulaire
Tableau fonctionnel ;
Graphique (schéma) des transitions.
Regardons-les avec des exemples.
Exemple 1. Construisez un MT qui implémente la concaténation de deux mots de l’alphabet. Les mots sur la bande sont séparés par *. La configuration initiale est standard.
Le système de commande MT ressemble à :
Dans l'état, la tête se déplace vers la droite jusqu'au symbole vide.
Le caractère le plus à droite est effacé.
L'astérisque est effacé si le premier mot est vide.
Le mot de droite est décalé caractère par caractère vers la gauche d'une position.
Transition vers la configuration finale standard.
Tableau des fonctions
| un | b | * | je | |
| - | ||||
| - | ||||
| - | ||||
| - |
Les tirets dans le tableau signifient que le symbole l est introuvable dans les états.
|
|
|||
Configuration finale standard.
Nous comprendrons le calcul d’une fonction dictionnaire sur MT comme suit. Laissez le mot a être écrit sur la bande dans la configuration initiale. Si la valeur est déterminée, alors un nombre fini d'étapes (cycles) la machine doit passer à la configuration finale, dans laquelle le mot est écrit sur la bande. Sinon, le MT devrait fonctionner indéfiniment.
À l'aide de MT, vous pouvez décrire les performances des opérations arithmétiques sur les nombres. Dans ce cas, les nombres sont présentés sur la bande sous forme de mots dans un alphabet composé de chiffres d'un certain système numérique et séparés par un signe spécial non inclus dans cet alphabet, par exemple *. Le système le plus couramment utilisé est unaire, constitué d’un seul symbole –1. Le chiffre X sur la bande est écrit avec le mot (ou abrégé) dans l'alphabet UNE=(1).
Une fonction numérique est correctement calculable (ou simplement calculable par Turing) s'il existe un MT qui mappe la configuration à la configuration lorsque = oui, ou s'exécute indéfiniment lorsqu'il n'est pas défini.
Exemple 2. L'opération d'addition de deux nombres en code unaire.
Configuration initiale :
Configuration finale : c'est-à-dire l'addition revient en fait à attribuer un numéro b au numéro un. Pour cela, le premier 1 est effacé et le * est remplacé par 1.
Nous donnons une description du MT sous forme de tableau fonctionnel :
| * | je | ||
| - | |||
| - | |||
| - |
Les méthodes ci-dessus pour décrire MT ne peuvent pratiquement être utilisées que pour des algorithmes simples, car pour les plus complexes, la description devient trop lourde. De même, décrire des fonctions récursives en utilisant uniquement les fonctions et opérateurs les plus simples de superposition, de récursivité primitive et de minimisation serait extrêmement fastidieux. Par conséquent, la récursivité primitive ou partielle d’une fonction est prouvée à l’aide d’autres fonctions dont la récursivité primitive ou partielle a déjà été prouvée.
De même, les machines de Turing destinées aux algorithmes complexes peuvent être construites à l’aide des MT existantes. Cette construction est appelée composition MT.
Décrivons 4 méthodes principales de composition MT :
Composition séquentielle (superposition) ;
Composition parallèle ;
Ramification
Composition séquentielle machines et fonctions de dictionnaire informatique et dans l'alphabet UN, appelé une voiture T, qui calcule la fonction. La composition séquentielle est représentée comme suit :
et est désigné .
La composition séquentielle est généralement utilisée pour décrire des sections linéaires d'algorithmes.
Preuve du théorème sur la possibilité de construire une machine T, qui est une composition séquentielle de deux machines arbitraires et est réalisée en identifiant l'état final avec l'état initial.
Exemple 3. Construisez un algorithme de multiplication 2*X en code unaire à l'aide d'une photocopieuse qui traduit le mot a en mot a*a et d'une machine d'addition. Le MT requis ressemble à ceci :
| | | |
|||||||||||||
| | |
||||||||||||||
Composition parallèle machines et fonctions de dictionnaire informatique et alphabets UN Et DANS en conséquence, la machine s'appelle T, qui évalue une fonction de dictionnaire. Ici, le signe est utilisé pour séparer les mots dans une composition MT parallèle.
| |
et est désigné : .
En fait, une composition parallèle de deux MT reçoit en entrée un mot composé de 2 mots dans des alphabets différents et sort un mot composé de 2 mots, c'est-à-dire représente deux machines travaillant simultanément et indépendamment.
Pour mettre en œuvre une composition parallèle, une machine avec une bande à deux étages est utilisée. La nécessité de cela est due au fait que le calcul et le temps se produisent séquentiellement et que, calculé, par exemple, en premier, peut nécessiter plus d'espace que a et gâcher le mot b. Le magnétophone à deux étages fonctionne ainsi : le mot b est écrit au deuxième étage et effacé au premier étage, calculé au premier étage, calculé au deuxième étage, puis réécrit au premier étage, éventuellement avec un décalage .
Pour mettre en œuvre une composition parallèle n machines utilisées n– ruban adhésif au sol.
La commande MT avec une bande à deux étages est écrite comme suit :, où sont les lettres écrites respectivement au premier et au deuxième étage.
Exemple 4. Mettre en œuvre une composition parallèle de machines et de fonctions de calcul dans le système de nombres binaires et a+b dans le système unaire.
Le mot d'entrée a la forme : .
Décrivons le fonctionnement du MT avec un système de commandes :
Aller à droite jusqu'au mot b
Réécrire le mot b au deuxième étage
Déplacer vers la gauche jusqu'au mot a
Ajouter 1 au nombre X.
Déplacez-vous vers la droite jusqu'au mot b.
Recensement b au 1er étage avec addition simultanée de chiffres un Et b.T en conséquence. Commandes entre accolades ajoutées au système de commande
L'état final de l'ensemble du MT.
Il est à noter que dans tous les cas, au début de l'algorithme, il est nécessaire d'insérer une vérification des données sources pour des valeurs particulières (le plus souvent 0) ; le non-respect de cette exigence peut conduire à une boucle.
La composition MT peut être utilisée pour créer des algorithmes complexes. La question se pose : n’importe quel algorithme peut-il être implémenté en tant que composition MT ? La réponse à cette question est donnée par La thèse de Turing , un analogue de la thèse de Church : tout algorithme peut être implémenté à l'aide de machines de Turing et vice versa, chaque processus implémenté par une machine de Turing est un algorithme.
La thèse de Turing n'est pas un théorème ; il est impossible de le prouver, car il contient le concept informel " algorithme" Cependant, de nombreuses années de pratique mathématique sont une confirmation fiable de cette thèse : depuis 50 ans, aucun algorithme au sens intuitif n'a été trouvé qui ne puisse être implémenté à l'aide des machines de Turing.
Objectif du travail : acquérir des compétences pratiques dans l'écriture d'algorithmes en utilisant la composition des machines de Turing.
Informations théoriques
Les méthodes ci-dessus pour décrire MT ne peuvent pratiquement être utilisées que pour des algorithmes simples, sinon la description devient trop lourde. Les machines de Turing pour algorithmes complexes peuvent être construites à l'aide de MT élémentaires déjà existants, et cette construction est appelée composition MT.
Décrivons 4 méthodes principales de composition MT :
Composition séquentielle (superposition) ;
Composition parallèle ;
Ramification
1. Composition séquentielle des machines de Turing
Composition séquentielle ou superposition Machines de Turing et 
Et 
en alphabet UN,ça s'appelle une voiture M, calculant la fonction 
.
La composition séquentielle est représentée comme suit :
et est désigné 
ou 
.
2. Composition parallèle des machines de Turing
Composition parallèle
voitures 
Et 
, calcul des fonctions du dictionnaire 
Et 
en alphabet UN Et DANS, en conséquence, la machine s'appelle M, qui évalue une fonction de dictionnaire. Voici le signe 
utilisé pour séparer les mots dans une composition MT parallèle.
Composition parallèle MT 
Et 
est représenté comme suit :
et est désigné : 
.
En fait, une composition parallèle de deux MT reçoit en entrée un mot composé de 2 mots dans des alphabets différents, et sort un mot composé également de 2 mots, c'est-à-dire représente deux machines fonctionnant simultanément et indépendamment. Pour mettre en œuvre une composition parallèle, une machine avec une bande à deux étages est utilisée.
La machine à bande à deux étages fonctionne comme suit :
1) mot 
réécrit au deuxième étage de la bande et effacé au premier,
2) calculé 
au premier étage,
3) calculé 
Au deuxième étage
4)
réécrit au premier étage, éventuellement avec un décalage.
La commande MT avec une bande à deux étages s'écrit comme suit :
,
Où 
– des lettres écrites respectivement aux premier et deuxième étages. Notons les longueurs des mots 
, respectivement, 
.
Démontrons le fonctionnement d'une machine de Turing avec une bande à deux étages. En général, la longueur des mots 
Et 
ne coïncident pas les uns avec les autres, mais pour simplifier l'image, nous supposons qu'ils sont égaux. Ensuite, la mise en œuvre des points 1)-4) sur un MT avec une bande à deux étages s'effectue de cette manière :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pour mettre en œuvre une composition parallèle n Des machines de Turing sont utilisées n– ruban adhésif au sol.
3. Branchement ou transition conditionnelle dans les compositions de machines de Turing
Si des machines de Turing sont données 
Et 
, calcul des fonctions du dictionnaire 
Et 
, et la voiture 
, qui évalue un prédicat P.(
)
avec restauration (c'est-à-dire sans effacer le mot
),
alors une machine de Turing peut être construite pour implémenter le branchement 
, calculant la fonction :
Le branchement des machines de Turing dans les diagrammes de composition est représenté comme suit :
et est désigné 
, Ici 
- le résultat du fonctionnement de la machine 
, en prenant les valeurs "1" si le prédicat P.(
)=
”vrai”
et "0" si le prédicat P.(
)=
“FAUX”
,
– une machine de Turing qui implémente la copie du mot d'entrée 
.
4 . Cycle dans la composition des machines de Turing
Faire du vélo en composition, MT est implémenté selon les mêmes principes que le branchement.
" Au revoir P(
)=
”vrai”
, remplir 
»,
Où
– mot sur bande avant la première exécution 
et après la prochaine exécution .
Pour décrire le cycle, nous introduisons une notation, soit :
– une machine de Turing qui implémente le calcul d'un prédicat P(
)
;
–MT, qui implémente la copie du mot d'entrée 
;
–MT, exécuté en boucle et implémentant 
;
–MT, exécuté à la sortie de la boucle et à l'implémentation 
.
Ensuite, la composition cyclique des machines de Turing, ou cycle, peut être représentée comme suit :
Programmation avec les compositions de la machine de Turing :
1) construction de schémas fonctionnels d'algorithmes complexes d'un niveau de détail tel que leurs blocs correspondent au MT élémentaire ;
2) construction de MT élémentaires qui implémentent des blocs simples ;
3) combiner des MT élémentaires dans une composition MT.
Exemple. Créez une composition MT qui implémente 
.
–Machine de Turing, qui implémente la copie du mot d'entrée ;
–MT, qui implémente la fonction de réglage du zéro constant ;
–MT, prédicat informatique avec restauration 
;
– MT qui implémente la fonction de sélection 
- cet argument de 
arguments;
–MT, implémentant la fonction de réduction d'argument 
par 1 en code unaire (efface le caractère le plus à gauche) ;
– MT, qui effectue l'addition de deux nombres en code unaire.
Il convient de noter que dans tous les cas, il est nécessaire de vérifier l'exactitude des données d'entrée au début de l'exécution de l'algorithme (par exemple, l'égalité de l'argument à 0 lors de la division).
Graphique 1.6
Les notations suivantes sont utilisées dans la figure 1.6 :
T 1, T 2 - Machines de Turing ;
ST 1, ST 2 - systèmes de commande des machines T 1 et T 2, respectivement ;
x - informations initiales pour la machine T 1 ;
T 1 (x) - le résultat du fonctionnement de la machine T 1 ;
T 2 (T 1 (x)) - le résultat du fonctionnement de la machine T 2.
A titre d'exemple, considérons la composition de deux machines, dont la première effectue une opération de copie et la seconde effectue l'opération d'addition de nombres en code unaire. Un schéma de la combinaison de machines et un exemple de bande avec les résultats obtenus sont présentés sur la figure 1.7.
Graphique 1.7
La composition représentée sur la figure 1.7 permet d'effectuer l'opération de doublement d'un nombre à l'aide de machines de copie et d'addition déjà connues. Ainsi, après avoir composé des algorithmes pour les machines de Turing afin de résoudre un ensemble d'opérations spécifiques (par exemple, des opérations arithmétiques), des compositions de machines de Turing peuvent ensuite être composées pour résoudre des problèmes plus complexes. Dans ce cas, le développement d'un algorithme général se résume à sa compilation à partir des opérations pour lesquelles des algorithmes d'exécution sur une machine de Turing sont déjà connus. Cette approche est similaire à l’utilisation de procédures et de fonctions en programmation.
Cependant, l'utilisation de la composition machine suppose de connaître les algorithmes permettant de réaliser les opérations élémentaires, à partir desquels est composé l'algorithme général. Par conséquent, lors de la résolution de problèmes arbitraires, cette approche n'exclut pas la nécessité de composer de nouveaux algorithmes et, par conséquent, de développer des machines de Turing avec différentes unités de contrôle. Il est possible de mettre en œuvre n'importe quel algorithme sans modifier la structure de l'unité de contrôle à l'aide d'une machine de Turing universelle.
1.2.2.Machine de Turing universelle
Si une machine de Turing est donnée (c'est-à-dire que les alphabets des signaux et états d'entrée, de sortie, la position initiale de la tête et l'état initial de la machine sont connus, ainsi qu'un tableau du fonctionnement de la machine et une bande avec les informations initiales ), alors toutes les transformations d'informations peuvent être effectuées manuellement étape par étape, pour lesquelles cette machine est destinée. En fait, dans ce cas, une simulation d’une machine de Turing est réalisée.
En analysant les opérations effectuées lors de la modélisation d'une machine de Turing, on peut établir que la modélisation revient à répéter les actions suivantes à chaque étape :
ÄLecture d'un caractère à partir de la cellule de bande sur laquelle se trouve la tête.
ÄRecherchez une commande dans le tableau des opérations de la machine. La recherche est effectuée en fonction de l'état actuel de la machine et de la valeur du symbole lu.
ÄSélectionner le symbole de la commande qui doit être écrit sur la bande et l'enregistrer.
ÄSélectionnez le symbole de mouvement de la tête dans la commande et déplacez-le.
ÄSélection d'un nouvel état de la machine à partir de la commande et modification de l'état actuel par un nouveau. Ensuite, on passe à l'étape suivante et on répète ces étapes.
|
|
 |
|||||
 |
|||||
Graphique 1.8
La nature de ces actions élémentaires est telle qu'elles peuvent toutes être réalisées à l'aide d'une autre machine de Turing, qui simulera le fonctionnement de la machine d'origine. L'essence de la modélisation est expliquée dans la figure 1.8.
Si la machine T dispose d'un système de commande ST et traite une bande avec les informations X, alors son fonctionnement peut être simulé par une autre machine U, qui possède son propre système de commande SU. Pour simuler l'entrée de la machine U, vous devez soumettre non seulement une bande avec les informations X , mais aussi le système de commande (table de travail) ST. Ce système de commande peut être enregistré sur la même bande que les informations originales.
 |
Graphique 1.9
Une caractéristique importante d'une machine de simulation est que son système de commande SU (et, par conséquent, la structure de l'unité de contrôle) ne dépend pas de l'algorithme de fonctionnement de la machine simulée T. Une machine de Turing capable de simuler le fonctionnement de n'importe quelle autre machine de Turing la machine est dite universelle. Une variante de la structure d'une machine de Turing universelle (UMT) est représentée sur la figure 1.9.
La bande UMT est divisée en trois zones : une zone de données, une zone de mode et une zone de commande.
La zone de données contient les informations initiales qui doivent être traitées par la machine de Turing simulée. Dans la même zone, les résultats de l'opération UMT sont enregistrés.
La zone de mode enregistre l'état actuel Q t et le symbole d'entrée actuel X t , qui est lu dans la cellule de la zone de données au cours d'un cycle donné.
La zone de commande contient le système de commande de la machine simulée. Les commandes sont organisées en groupes. Le premier groupe comprend les commandes commençant par le symbole Q 0, le second - par le symbole Q 1, etc. Au sein de chaque groupe, les commandes sont classées selon la valeur du symbole X t . Ainsi, les commandes sur la bande sont localisées telles qu'elles sont situées dans la table d'opérations de la machine simulée.
La lecture des informations de la bande et l'écriture sur la bande sont effectuées à l'aide de trois têtes : G d - tête de données, G r - tête de mode, G k - tête de commande. Chaque tête peut se déplacer le long de sa propre zone de la ceinture.
Avant que l'UMT commence à fonctionner, les informations pertinentes doivent être enregistrées dans chaque zone de la bande. Les têtes doivent être installées au-dessus du symbole de gauche dans chaque zone.
Le fonctionnement de l'UMT se déroule par cycles, dans chaque cycle l'exécution d'une commande de la machine simulée est simulée. Le graphique de fonctionnement de l'UMT est illustré à la figure 1.10.
 |
Graphique 1.10
Les notations suivantes sont utilisées dans la figure 1.10 :
Q G vers P (G vers L, G r P, G r L, G d P, G d L) - déplacer l'une des têtes
droite ou gauche;
Q (G k), (G d), (G r) - informations lues par l'une des têtes ;
Q (G k) à (G r) - lecture des données par la tête de commande et écriture de ces données
transféré à l'aide de la tête de mode vers la zone du mode bande ;
Q a est une variable auxiliaire qui prend la valeur 1, es-
si les caractères lus par les têtes Гк et Гр coïncident ;
Q in est une variable auxiliaire qui prend la valeur 1, es-
si les symboles des états actuel (Q t) et final (Q z)
Q p - un signal qui prend la valeur 1 si la tête de commande lorsque
le déplacement vers la gauche dépassait les limites de la zone de commandement ;
Dans chaque cycle de fonctionnement de l'UMT, les étapes suivantes sont effectuées :
vous recherchez la zone de commande ;
vous recherchez une équipe dans la zone ;
u simulation de l'exécution de commandes.
La recherche de la zone de commande commence par comparer l'état courant Q t issu de la zone mode avec l'état Q i enregistré au début de la première commande dans la zone de commande. Si ces états ne sont pas égaux, alors la tête de commande passe au début de la commande suivante, pour laquelle cinq pas de la tête sont effectués vers la droite (états U 0 - U 4). Si les symboles Q t et Q i correspondent, la tête de commande se trouve au début de la première commande de la zone souhaitée. Ensuite commence la recherche d'une commande correspondant aux symboles Q t et X t de la zone mode. Pour ce faire, la tête de mode est placée au dessus du symbole X t de la zone de mode, et la tête de commande est placée au dessus du symbole X i dans la commande courante.
La recherche d'une commande dans une zone est similaire à la recherche d'une zone de commande. Dans ce cas, la tête de commande se déplace vers la droite de cinq pas (états U 5 - U 9) jusqu'à ce que les caractères X t et X i soient comparés.
L'exécution de la commande (états U 10 - U 17) commence par déplacer la tête de commande d'un pas vers la droite, après quoi le symbole Y t lu de la commande trouvée est écrit dans la zone de données à l'aide de la tête de données au lieu du symbole X t lu précédemment. Après l'étape suivante de la tête de commande vers la droite, le symbole de déplacement de la tête de données (Y d) est lu à partir de la commande trouvée et la tête de données est déplacée conformément à ce symbole (R, L). En dessous se trouve le prochain symbole traité (X t +1), qui, à l'aide de la tête de mode, est écrit dans la zone de mode pour préparer le cycle suivant. Ensuite, les têtes de commande et de mode sont installées de manière à ce que l'état suivant Q t +1 (états
U14, U15). Dans l'état U16, la condition de fin de solution est vérifiée. Si le symbole de l'état suivant ne coïncide pas avec le symbole de l'état final de la machine modélisée (Q z), alors la solution du problème n'est pas terminée et dans l'état U 17, la tête de commande revient à sa position d'origine ( au début de la première commande de la première zone). Dans ce cas, l'UMT est prêt à effectuer le cycle suivant, c'est-à-dire pour simuler l’exécution de la commande suivante.
Lorsque les symboles Q t et Q z coïncident, la solution du problème se termine et l'UMT passe dans l'état final U z .
Lors de l'analyse du processus de fonctionnement de l'UMT, on peut tirer une conclusion importante selon laquelle l'algorithme de fonctionnement de l'UMT ne dépend pas du problème spécifique résolu par la machine de Turing simulée. Par conséquent, la structure de l'unité de contrôle UMT ne change pas lors de la modélisation de différentes machines, c'est-à-dire ne dépend pas des tâches à résoudre. C'est pourquoi l'UMT est véritablement une machine universelle, à l'aide de laquelle vous pouvez exécuter n'importe quel algorithme sans modifier sa structure.
Étant donné que le processus de sélection de la prochaine commande UMT et de son exécution est associé à une énumération séquentielle des cellules de la bande, la résolution des problèmes sur l'UMT prend trop de temps. Par conséquent, aucune machine de Turing, y compris universelle, n'a jamais été construite, mais il n'est pas difficile d'y voir un analogue des ordinateurs modernes. Ainsi, le système de commande dans la zone de commande UMT s'apparente à un programme machine, avec un couple de symboles Q t et X t jouant le rôle d'adresse de la commande machine.
Cependant, la machine de Turing constitue un moyen assez pratique pour décrire des algorithmes et est largement utilisée en théorie des algorithmes.
Questions de contrôle
ü1.Quelle est la composition des machines de Turing ?
ü2.À quoi sert la composition des machines de Turing ?
ü3.Une machine de Turing peut-elle simuler le fonctionnement d’une autre machine ?
Turing ?
ü4.Quelles actions sont effectuées dans ce cas ?
ü5.Expliquer la structure de la machine de Turing universelle ?
ü6.Quelles informations sont enregistrées dans les zones de la bande UMT ?
ü7.Quel est le système de commande d'une machine de Turing ?
ü8.Quelles sont les étapes du cycle de travail de l'UMT ?
ü9.Expliquez le contenu de l'étape « recherche de zone de commande ».
ü10.Expliquez le contenu de l'étape « exécution de la commande ».
ü11.Quelles sont les caractéristiques du processus de traitement de l'information à l'aide
Le diagramme ressemble à un graphique :
Valeur du tableau machine
Tableau 1
Quelques opérations sur les machines de Turing
Le fonctionnement d'une machine de Turing est entièrement déterminé par les données d'entrée et le système de commande. Cependant, afin de comprendre comment une machine particulière résout un problème, il est généralement nécessaire d'avoir des explications significatives du type de celles qui ont été données pour la machine. 
. Ces explications peuvent souvent être rendues plus formelles et précises en utilisant des schémas fonctionnels et certaines opérations de la machine de Turing. Rappelons que la composition des fonctions 
Et 
fonction appelée 
, qui est obtenu en utilisant 
au résultat du calcul 
. Pour 
a été déterminé à ce moment-là 
, il est nécessaire et suffisant pour 
a été déterminé le 
, UN 
a été déterminé le 
.
Théorème 1. Si 
Et 
sont Turing calculables, alors leur composition 
est également calculable par Turing.
Laisser 
- une machine qui calcule 
, UN 
- une machine qui calcule 
, et l'ensemble de leurs états, respectivement 
Et 
.
Construisons un diagramme de transition de voiture 
à partir de diagrammes 
Et 
comme suit : on identifie le sommet initial 
schémas de machines 
avec sommet terminal 
schémas de machines 
(pour les systèmes de commande, cela équivaut au fait que le système de commande 
affecté au système de commandement 
et pour ça 
en équipes 
remplacer par 
). On obtient un diagramme avec ( 
) États. Etat initial 
nous annoncerons 
et finale 
. Pour simplifier la notation, nous supposerons 
Et 
fonctions numériques d'une variable.
Laisser 
déterminé. Alors 
Et
. Voiture 
passera par la même séquence de configurations à la différence qu'au lieu de 
cela aura lieu dans 
. Cette configuration est la configuration initiale standard de la machine 
, C'est pourquoi 
. Mais puisque toutes les équipes 
contenu dans 
, Que
et donc 
. Si 
n'est pas défini, alors 
ou 
ne s'arrête pas et donc la voiture 
Ne s'arrêtera pas. Alors la voiture 
calcule 
.
La machine ainsi construite 
nous l'appellerons une composition de machines 
Et 
et désigner 
(ou 
(
)), et également représenté dans un schéma fonctionnel :
Composition des machines de Turing
Laisser 
,
,
- trois machines de Turing avec le même alphabet externe 
, avec des alphabets d'états internes 
,
,
et programmes 
,
,
respectivement.
Composition
voitures 
Et 
appelé voitureT
, dont le programme est l'union d'ensembles 
Et
, Où 
désigne un ensemble de commandes reçues de 
remplacer tout 
sur 
.
Dérivation des machines de Turing
Machines à brancher
,
,
Par 
, symboliquement
appelé voitureT
, dont le programme s'obtient comme suit : de 
les équipes sont exclues 
Et 
Pour 
, l'ensemble résultant sera appelé 
; Alors.
Machine de Turing universelle
Le système de commande d'une machine de Turing peut être interprété à la fois comme une description du fonctionnement d'un appareil spécifique et comme un programme, c'est-à-dire un ensemble d’instructions qui mènent clairement à un résultat. Lors de l'analyse d'exemples, la deuxième interprétation est involontairement acceptée, c'est-à-dire nous agissons comme un mécanisme capable de reproduire le travail de n'importe quelle machine de Turing. La confiance que tout le monde fera cela de la même manière (s'ils ne commettent pas d'erreurs, ce qui est d'ailleurs également supposé lorsqu'une machine de Turing fonctionne) est essentiellement la confiance dans l'existence d'un algorithme permettant de reproduire le fonctionnement d'une machine de Turing. machine selon un programme donné, c'est-à-dire système de commande. En effet, il n’est pas difficile de donner une description verbale d’un tel algorithme. Son action principale se répète cycliquement et consiste en ce qui suit : "Pour la configuration actuelle 
trouvez la commande avec le côté gauche dans le système de commande 
. Si le côté droit de cette commande est de la forme 
, puis remplacer dans la configuration actuelle 
sur 
(il s'avère que la configuration 
); si le côté droit a la forme 
, puis remplacez 
sur 
. Une description verbale de l’algorithme peut être inexacte et doit être formalisée. Puisque la machine de Turing est actuellement discutée comme une telle formalisation du concept d'algorithme, il est naturel de poser le problème de la construction d'une machine de Turing qui implémente l'algorithme de reproduction décrit. Pour les machines de Turing qui calculent les fonctions d'une variable, la formulation de ce problème est la suivante : construire une machine de Turing 
, calculant une fonction de deux variables et telle que pour toute machine 
avec système de commande 
, Si 
défini (c'est-à-dire si la machine 
s'arrête aux données initiales 
) Et 
ne s'arrête pas si 
ne s'arrête pas. Nous appellerons toute machine possédant cette propriété machine de Turing universelle. Il n’est pas difficile de généraliser cette formulation à un certain nombre de variables.
Le premier problème qui se pose lors de la construction d'une machine universelle 
, est dû au fait que 
comme toute autre machine de Turing, doit avoir un alphabet fixe 
et un ensemble fixe d'états 
. Par conséquent, le système de commande 
et les données initiales d'une machine arbitraire 
vous ne pouvez pas simplement le transférer sur la courroie de la machine 
(il y a toujours une voiture 
, alphabets 
Et 
qui est supérieur en puissance 
Et 
ou tout simplement ne coïncide pas avec cela).
La solution est d'avoir les personnages de 
Et 
codé par des symboles de l'alphabet 
. Laisser 
,
. Nous supposerons toujours que 
Et 
(ces deux symboles sont toujours dans l'alphabet de toute machine fonctionnant avec des chiffres). Notons les codes 
Et 
à travers 
Et 
et les définir comme 
; pour quelqu'un d'autre 
; pour l'état final 
, Si 
. Code 
pour cette voiture 
a toujours une longueur (format) 
, et le code 
-format 
. Symboles 
,
entrons 
, c'est à dire. 
,
,
. Code de caractère 
, formé par les codes des caractères qui composent ce mot, on note 
. Ainsi, le raffinement final de la formulation du problème d'une machine universelle 
se résume au fait que pour n'importe quelle voiture 
et des mots 
alphabet 
.
L'existence d'une machine de Turing universelle signifie que le système d'instruction 
n'importe quelle voiture 
peut être interprété de deux manières : soit comme une description du fonctionnement de l'appareil d'origine 
, ou comme programme pour une machine universelle 
. Pour un ingénieur moderne qui conçoit un système de contrôle, cette circonstance est naturelle. Il sait bien que tout algorithme de contrôle peut être implémenté soit sous forme matérielle - en construisant un circuit approprié, soit sous forme logicielle - en écrivant un programme informatique de contrôle universel.
Cependant, il est important de comprendre que l'idée d'un dispositif algorithmique universel n'a aucun rapport avec le développement de moyens techniques modernes pour sa mise en œuvre (électronique, physique du solide, etc.) et n'est pas un fait technique, mais mathématique. , décrit en termes mathématiques abstraits, indépendants des moyens techniques et, de plus, fondé sur un nombre extrêmement restreint de concepts initiaux très élémentaires. Il est caractéristique que les travaux fondamentaux sur la théorie des algorithmes (notamment les travaux de Turing) soient apparus dans les années 30, avant la création des ordinateurs modernes.
Cette double interprétation préserve au niveau abstrait les principaux avantages et inconvénients des deux options d’implémentation technique. Voiture spécifique 
fonctionne beaucoup plus vite ; en outre, le dispositif de commande de la machine 
assez lourd (c'est-à-dire que le nombre d'états et de commandes est important). Cependant, sa valeur est constante et, une fois construit, il convient à la mise en œuvre d’algorithmes de taille arbitraire. Tout ce qu'il faut, c'est un grand volume de bande, qui est naturellement considéré comme moins cher et plus simple à construire que le dispositif de contrôle. De plus, lors du changement d'algorithme, vous n'aurez pas besoin de créer de nouveaux appareils, il vous suffit d'écrire un nouveau programme.