===== II. Indécidabilité =====
==== II.1 Thèse de Church-Turing ====
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.
=== Thèse ===
Un __algorithme__ traduit une fonction qu'on sait implanter avec une machine de Turing qui s'arrête pour toutes les entrées.
==== II.2 Machines de Turing Universelles ====
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,
\Sigma_M = \left\{ \triangleright, \sqcup, 0, 1, ; \right\} \mapsto \left\{ a000, a001, a100, a101, a110 \right\}
si \triangleright \equiv a000, \sqcup\equiv a001, à\equiv a100, 1\equiv a101, ; \; \equiv a110 sont les définitions des représentations.
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 :
* Initialisation
* on commence avec "M" _ "w" sur le premier ruban (programme=fonction de transitions, blanc, données)
* on recopie "M" sur le 3ième ruban
* on garde "w" sur le premier ruban : \triangleright \sqcup w
* on écrit "s" sur le 2ième ruban
* Marche :
* on lit le symbole courant sur le premier ruban
* on lit l'état courant sur le 2ième
* on cherche la transition sur le 3ième
* si la transition n'existe pas (le cas est imprévu) U s'arrête
* si la transition existe, U fait l'action définie (écriture ou mouvement) en 4ième position, puis passe à l'état défini dans la 3ième position.
==== II.3 Le "Halting Problem" ====
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 :
* halt(programme, entrée) = oui, si le programme s'arrêterait avec l'entrée, et non si le programme ne s'arrêterait pas.
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
H = \left\{ "M"\quad "w"\quad| M \in MT, w\in \Sigma_M^*, \text{M s'arret avec w en entree} \right\} \in \left(\Sigma_U^* \cup \sqcup \right)^*
=== Propriétés de H ===
* H est __récursivement énumérable__ (\exists une MT qui semi-décide : U)
* H n'est pas récursif et donc il existe des langages récursivement énumérables qui ne sont pas récursifs. __Preuve__ : haltbis = HU FIXME exercice
* si H était récursif, alors tout langage récursivement énumérable serait récursif.
== Preuve ==
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.
----
==== Navigation ====
[[c_et_c_8|]] <--> [[c_et_c_a|]]