Nous allons montrer comment n'importe qu'elle machine de Turing peut être décrite par une suite de symboles d'un alphabet fixe A. L'intérêt de ce codage est qu'une machine de Turing est décrite par un mot qui peut être donné comme entrée à une autre machine de Turing.
L'alphabet A est choisi égal à l'ensemble {0, 1, (, ), ','} qui contient les cinq symboles '0', '1', '(', ')' et ','. L'idée générale est de tout coder en binaire et d'utiliser le symbole ',' comme séparateur et les parenthèses '(' et ')' pour marquer les blocs. Chaque état de la machine M et chaque symbole de son alphabet de bande est codé par un numéro écrit en binaire sur l'alphabet {0,1}.
Soit M = (Q,Σ, Γ, E, q0, F, #) une machine de Turing. Soit n le nombre d'états de M. Les états sont alors numérotés de 0 à n-1. Soit m le nombre de symboles de l'alphabet de bande Γ de M. Les symboles de Γ sont alors numérotés de 0 à m-1. On suppose que le symbole blanc a le numéro 0 et que les symboles de Σ ont les numéros de 1 à k où k est le nombre de symboles dans Σ. Les écritures en binaires des entiers n, m et k sont respectivement notés <n>, <m> et <k>. Pour un état q, le codage en binaire du numéro de q est noté <q> et pour un symbole de bande a, le codage en binaire du numéro de a est noté <a>.
Le codage de la machine commence par le symbole '(' et se termine avec le symbole ')'. Entre ces deux symboles se trouvent six parties qui sont séparées par des virgules ','. Les trois premières parties sont respectivement les codages en binaire <n>, <k> et <m> des entiers n, k et m. Les quatrième partie code l'ensemble E des transitions. La cinquième partie est le codage de Q0 et la sixième parties est le codage de l'ensemble F des états finaux. Le symbole blanc n'est pas codé puisque par convention, il a le numéro zéro.
Le codage de E commence par le symbole '(' et se termine avec le symbole ')'. Le codage de E est constitué de la suite des codages de ses transitions séparés par des virgules. Chaque transition p,a → q,b,x de E codée par la suite de symboles (<p>,<a>,<q>,<b>,<x>) où <x> vaut 0 si x = L et 1 si x = R.
Le codage de F est constitué des codages <q> pour chaque q dans F, séparés par de virgules ',' et encadrés par des parenthèses '(' et ')'.
Le codage d'une machine M a donc la forme générale
(<n>, <k>, <m>, ((<p1>,<a1>, <q1>,<b1>,<x1>), (<p2>,<a2>, <q2>,<b2>,<x2>) &hellip), <q0>, (<f1>, <f2>, &hellip)).
Avec ce codage, toute machine de Turing peut être codée en une suite de symboles de l'alphabet A. Bien sûr, toute suite de symboles de l'alphabet A n'est pas le codage d'une machine de Turing. Pour être un codage, une suite de symbole doit respecter des règles syntaxiques. Elle doit par exemple commencer par '(' et se terminer par ')' et plus généralement avoir la forme ci-dessus. En outre, cette suite de symboles doit respecter des règles d'ordre sémantique. Par exemple, les numéros des états qui apparaissent dans le codage de E doivent être inférieurs au nombre n d'états de la machine. De même les numéros des symboles qui apparaissent dans le codage de E doivent être inférieurs au nombre m de symboles de bandes. Il n'est pas très difficile de construire une machine de Turing qui prend en entrée une chaîne de symboles de A et teste si cette chaîne est le codage valide d'une machine de Turing.
Comme exemple de codage d'une machine de Turing, nous donnons le codage de la Machine M qui accepte le langage X = { anbn | n ≥ 0} sur l'alphabet Σ = { a, b }.
Afin de faciliter la lecture de ce codage, celui-ci est réparti sur plusieurs lignes. Chaque ligne contient une partie du codage de M et un commentaire.
( // Début du codage de M 101, // Nombre d'états : 5 en binaire 10, // Nombre de symboles de Σ : 2 en binaire 101, // Nombre de symboles de Γ : 5 en binaire ( // Début du codage des transitions (0,1,1,11,1), // Transition (0,a) --> (1,A,R) (0,100,11,100,1), // Transition (0,B) --> (3,B,R) (1,1,1,1,1), // Transition (1,a) --> (1,a,R) (1,10,10,100,0), // Transition (1,b) --> (2,B,L) (1,100,1,100,1), // Transition (1,B) --> (1,B,R) (10,1,10,1,0), // Transition (2,a) --> (2,a,L) (10,11,0,11,1), // Transition (2,A) --> (0,A,R) (10,100,10,100,0), // Transition (2,B) --> (2,B,L) (11,100,11,100,1), // Transition (3,B) --> (3,B,R) (11,0,100,0,1), // Transition (3,#) --> (4,#,R) ), // Fin du codage des transitions 0, // Codage de l'état initial ( // Début du codage de l'ensemble F des états finaux 100 // Le seul état final est l'état 4 ) // Fin du codage de l'ensemble F des états finaux ) // Fin du codage de M