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

 
m1ilc/c_et_c_9.txt · Dernière modification: 2010/01/06 11:32 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki