====== Problème de l'arrêt ======

===== Y a-t-il des fonctions non calculables ? =====

La réponse est **OUI** et c'est facile de le justifier : Il y a plus de fonctions que de machines de Turing.

  * Une machine de Turing doit pouvoir est décrite avec un nombre de symbole fini. Le nombre de machines de Turing est un infini semblable à $card(\mathbb{N})$.
  * Avec un argument semblable à la diagonale de Cantor, on prouve que le nombre de fonctions est comme $card(\mathbb{R})$.

Mais on aimerait, comme Gödel avec sa propriété indémontrable, mettre en avant un exemple de fonction non calculable.

===== Problème de l'arrêt =====

Je note $M$ une machine de Turing quelconque et $m$ sont code pour la machine universelle $U$.

On se demande si la fonction $A$ telle que $A(m,x) = \begin{cases}1\text{ si }M(x)\text{ termine}\\0\text{ sinon}\end{cases}$ **est calculable**. Autrement dit, on se demande si on peut réaliser la machine de Turing $A$.

{{ :nsi:terminales:calculabilite:machine_arret.svg?600x320 |}}

<WRAP tip>
On sait que certains programmes, quand on leur fournit certaines entrées, peuvent entrer dans une boucle infinie et ne jamais terminer. Sur un programme particulier on peut arriver à savoir s'il terminera ou s'il ne terminera pas. La fonction $A$ qui nous intéresse serait une fonction qui ferait ce travail pour **n'importe quel programme $m$, automatiquement**.
</WRAP>

Si on peut réaliser $A$, alors on peut réaliser la machine $Q$ ci-dessous :

{{ :nsi:terminales:calculabilite:machine_q.svg?800x200 |}}

Et si la machine $Q$ est réalisable, alors elle a un code $q$ sur la machine universelle.

<WRAP box>**Question :** Que se passe-t-il si on place $q$ en entrée de $Q$ ?</WRAP>

  * Soit l'exécution de $Q(q)$ termine $\Rightarrow A(q,q) = 1 \Rightarrow $ le dernier étage de $Q$ lance une boucle infinie et $Q(q)$ ne termine pas.
  * Soit l'exécution de $Q(q)$ ne termine pas $\Rightarrow A(q,q) = 0 \Rightarrow$ le dernier étage de $Q$ se termine et rien n'empêche $Q(q)$ de terminer...

**Conclusion :** la machine $A$ n'est pas réalisable, la fonction $A$ n'est pas calculable. On peut dire aussi que l'arrêt est indécidable.

===== Le paradoxe du menteur =====

Tous les paradoxes rencontrés, Russell, Richard, Gödel, l'arrêt, consistent à énoncer une contradiction autoréférente.

Cela rappelle le cas du **menteur qui dit « je mens »**.

Dans tous les cas, ces paradoxes ne cassent pas la connaissance. Ils permettent de délimiter avec plus de finesse ce qui est faisable et ce qui ne l'est pas.