====== Dédidabilité et calculabilité ======

<WRAP info>
**Problème décidable en informatique :** Il existe un algorithme de longueur finie et de temps d'exécution fini qui répond oui ou non à la question posée.
</WRAP>

=== Exercice 1 ===

  - Le problème de savoir si 442 est pair est-il décidable ?
  - Le problème de savoir si 443 est premier est-il décidable ?

<WRAP info>
On parle aussi d'**ensemble décidable**. Un ensemble est décidable quand la question de savoir si tel élément appartient à l'ensemble est un problème décidable.
</WRAP>

=== Exercice 2 ===

  - L'ensemble des nombres pairs est-il décidable ?
  - L'ensemble des nombres premiers est-il décidable ?

<WRAP tip>
On utilise parfois le terme **ensemble récursif** au lieu de ensemble décidable. Dans ce sens, récursif n'a absolument rien à voir avec l'idée de fonction récursive qui s'appelle elle-même. Ces termes sont très utilisés dans la théorie des langages informatiques qui est à la base de notions importantes comme les expressions régulières ou encore la conception de langages de programmation.
</WRAP>

===== Calculabilité =====

{{ :nsi:terminales:calculabilite:church.jpeg?nolink&200|Alonzo Church 1903 - 1995}}

Dans les années 1930, Alonzo Church (1903 - 1995) invente le $\lambda$-calcul. C'est un langage informatique théorique ou tout est fonction. Les langages de programmation [[langages:lisp:start|Lisp]], [[langages:haskell:start|Haskell]], [[nsi:langages:ocaml:start|oCaml]] sont influencés par le $\lambda$-calcul.

Church et son équipe étudient la **calculabilité**. Une fonction $f$ est calculable si le calcul de $f(x)$ se termine en un nombre fini d'étape.

<WRAP box>
==Calculabilité et décidabilité==
La notion est liée à la **décidabilité**. En effet, soit $E$ un ensemble. On peut toujours définir la fonction $f_E$ telle que $f_E(x) = V \Leftrightarrow x \in E$. Si $f_E$ est calculable, alors on peut décider si $x \in E$ et alors $E$ est décidable.
</WRAP>

Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.

Nous allons poursuivre avec les **machines de Turing** bien que historiquement, les résultats qui nous intéressent ont d'abord été formulés dans le cadre du $\lambda$-calcul de Church. Les deux approches sont équivalentes.