On a vu au chapitre précedent plusieurs modèles de calcul qui étaient tous équivalents aux MT standard. Church et Turing cherchaient à caractériser ce qu'on savait calculer mécaniquement: calcul booléen, décidabilité des langages récursifs. En même temps, il y avait du travail fondamental sur la formalisation des mathématiques (Hilbert, notamment) et les (possibilité de) preuves mécaniques.
Un algorithme traduit une fonction qu'on sait implanter avec une machine de Turing qui s'arrête pour toutes les entrées.
Jusqu'ici il nous a fallu une MT faite sur mesure pour exécuter chaque algorithme. Pourquoi pas faire une machine de Turing universelle? L'idée est de stocker le codage d'une MT (qu'on aurait construite) sur “le” ruban, ce qui nécessite un langage de “programmation” pour écrire \delta
Rappelons que dans la définition d'un MT, M=\left(K,\Sigma, \delta,s,H\right), K et \Sigma sont des ensembles finis mais potentiellement énormes. Alors, comment avoir des alphabets et ensembles d'états aussi grands qu'on veut? Par un codage, avec préfixe a
pour les lettres (alpha) et q
pour les états, suivi d'en numéro (en binaire). Par exemple,
Ensuite, on notera qu l'on peut coder toute Machine de Turing sur l'alphabet \Sigma_U = \left\{ a, q, 0, 1, , , (, ) \right\} par sa table (ou fonction) de transition exprimée sous la forme d'une liste de quadruplets : (état courant, lecture, état après, action)
Par exemple, pour une très simple MT :
\delta | état courant | lecture | conséquence | en d'autres termes… |
---|---|---|---|---|
1 | s | a | q,\sqcup | si dans l'état initial on lit 'a' on écrit un blanc et passe à l'état q |
2 | s | \sqcup | h,\sqcup | si on lit (toujours dans l'état initial) un blanc, on s'arrête. |
3 | s | c | s,\rightarrow | si on est au début du raban, on se déplace à droite (et reste dans l'état initial) |
4 | q | a | s,a | lecture d'un a dans l'état q ⇒ remettre le a et passer à l'état s |
5 | q | \sqcup | s, \rightarrow | |
6 | q | \triangleright | q,\rightarrow | si on est au début du raban, on se déplace à droite (et reste dans l'état initial) |
Pour encoder notre Machine, prenons
symbole | s | q | h | \sqcup | \triangleright | ← | → | a |
---|---|---|---|---|---|---|---|---|
encodage | q00 | q01 | q11 | a000 | a001 | a101 | a011 | a100 |
Notre table de transitions (delta) devient :
1 | q00 | a100 | q01 | a000 |
---|---|---|---|---|
2 | q00 | a000 | q11 | a000 |
3 | q00 | a001 | q00 | a011 |
4 | q01 | a100 | q00 | a100 |
5 | q01 | a000 | q00 | a011 |
6 | q01 | a001 | q01 | a011 |
et ”\triangleright a a \sqcup a” s'exprime a001a100a100a000a100
La machine de Turing Universelle qu'on définit ici a pour alphabet \Sigma_U\;\cup\;\left\{\triangleright, \sqcup\right\} et est définie comme une MT à 3 rubans.
> | codage de la bande de M |
---|---|
> | codage de l'état courant de M |
> | codage de la fonction de transitions de M |
On suit ces étapes :
Maintenant nous abordons une question d'autoréférence, en programmation en particulier. Concevons une fonction (ou son programme) qui réalise la chose suivante :
Est-ce qu'un tel programme peut exister?
Voici l'autoréférence qui arrive : définissons haltbis( “p” )
, une fonction qui boucle si halt(“p”,”p”) est “oui”, et répond “oui” si halt(“p”,”p”) est “non”. Alors, que fait haltbis(“haltbis”)
?
haltbis(“haltbis”)
bouclerait si halt(“haltbis”,”haltbis”)=oui
, ce qui correspond au cas où haltbis(“haltbis”) s'arrête (donc ce cas ne peut pas arriver).haltbis(“haltbis”)
répondrait “oui” si halt(“haltbis”,”haltbis”)=non
, ce qui correspond au cas où haltbis(“haltbis”) ne s'arrête pas (donc ce cas ne peut pas arriver non plus).
halt()
ne peut donc pas être réalisée.
Plus formellement, on pose
Supposons H récursif. Il existerait une machine SuperU le décidant. C'est à dire, SuperU(“H”, “w”) = “oui” si M s'arrête, “non” sinon.
Soit L un langage énumérable semi-décidé par M', c'est à dire w\in L ⇔ M'(w) s'arrête. Alors la MT correspondant w \mapsto SuperU(“M'”, “w”) décide L.