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.

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$.

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

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

• 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.

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.