Thèse de Church

marco · October 2015

Bonjour,

Il me semble, que la thèse de Church dit que toute fonction $f$ de $\N$ dans $\N$ calculable par un procédé physique P est en fait calculable par une machine de Turing.
N'y a-t-il pas un problème ? En effet, le procédé physique P devra avoir une mémoire infinie pour mémoriser le nombre $n$ que l'on lui soumet en entrée, et qui peut être aussi grand que l'on veut.
Dans ce cas, si P a le droit d'avoir une mémoire infinie, on peut peut-être réfuter la thèse de Church comme suit. On considère une mémoire infinie, qui est initialisée comme cela: pour tout $n \in \N$, dans la case $n$, il y a $-1$.
Ensuite, si on soumet à P une entrée $k$: si dans la case $k$, il ya $-1$, on tire au hasard un nombre $m$ valant $0$ ou $1$ par un procédé quantique, et on le met dans la case $k$ et on renvoie $m$ en sortie. Si dans la case $k$, il y a un nombre $ m \geq 0$, on renvoie en sortie le nombre $m$.

Alors, si on entre deux fois au cours du test le nombre $k$, le nombre $m$ de sortie sera deux fois le même, donc P calcule bien une fonction. Pourtant, dans presque tous les cas, la fonction ne sera pas calculable par une machine de Turing.

christophe c · October 2015

Non ce n'est pas ça la thèse de church. C'est l'identification entre la notion d'algorithme (qui n'est pas une notion mathématique) et la notion de fonction calculable (qui a une définition mathématique). Autrement dit, elle dit:

Toute fonction $f$ telle qu'il existe un algorithme qui la calcule est récursive

Si tu tiens absolument à la rapprocher d'une notion physique, je l'ai traitée dans ma thèse (enfin dans l'article de 98 qui était un peu plus complet, mais sale), ça donne la chose suivante:

soit le jeu où deux potes vont être séparés chacun par exemple dans un trou noir différent du trou noir de l'autre.

Au pote1 on peut ou bien proposer un couple (0,n) ou bien proposer un couple (1,n) où $n$ est un entier. Au pote2, on propose un nombre entier $n$.

Ils doivent chacun répondre un entier.

Soit une partie où on a proposé au pote1 le couple (i,n) (il a répondu $r$) et au pote2 le nombre p (il a répondu $s$)

Alors cette équipe de potes gagne dans les conditions suivantes: si $i=1$ et $n$ le numéro de la fonction calculable $f$ alors la réponse $s$ du pote2 doit être différente de $f(r)$ ou le nombre $p$ doit être différent de $r$.

si $i=0$ et $n=p$ alors $r$ doit être égale à $s$.

(Dans tous les autres cas, l'équipe de potes gagne)

La thèse de Church dit alors qu'il n'existe pas de stratégie "humainement accessible" pour gagner à ce jeu (quand on est l'équipe de potes)

Jer anonyme · October 2015

Bien que béotien, j'y vais de ma vulgarisation. Je dirais que la thèse de Church affirme que tous les modèles de calcul sont équivalents : qu'on décrive ce qu'est une fonction calculable par une machine de Turing, par le lambda-calcul ou tout autre procédé, on aboutira à la même classe de fonctions. Mais Church n'a démontré que l'équivalence entre les deux modèles de calcul qui existaient à son époque, celui de Turing et le sien.

marco · October 2015

Merci pour vos réponses.
@Christophe: je comprends le cas $i=0$: cela veut dire que l'association $n \mapsto r$ et $p \mapsto s$ est la même fonction, mais les deux potes ne peuvent se concerter. Donc, ça invalide mon exemple de machine.
Pour le cas $i=1$, il doit vouloir dire que la fonction du pote2 $p \mapsto s$ n'est pas calculable. En effet, si elle était calculable égale à $f_{n_0}$, on proposerait $(1,n_0)$ au pote1 que l'on sait avoir l'habitude de répondre $r_0$ à ce couple. Au pote2, on propose $r_0$, et il répond $f_{n_0}(r_0)$. Donc les potes perdent. C'est ça ?
De plus, la fonction du pote2 est la même dans le cas $i=0$ et $i=1$, car il ignore la valeur de $i$.
Est-ce que c'est toi qui a formalisé la thèse de Church comme ça (ou c'est Penrose :-D) ?
@Jer anonyme: merci pour l'éclairage.

christophe c · October 2015

Oui tu as compris. Et oui c'est moi qui l'ai formalisée ainsi, je ne suis même pas sûr que Penrose connait la thèse de Church (probablement que oui).

marco · October 2015

C'est vraiment bien conçu.

marco · February 2017

@christophe: si tu as précisé que les deux potes étaient séparés par des trous noirs différents l'un de l'autre, est-ce pour éviter qu'ils ne gagnent en utilisant des particules intriquées ?

christophe c · February 2017

Non, en fait, j'ai juste écrit: par exemple dans un trou noir différent du trou noir de l'autre

Mais la description du jeu est une description "de principe". La non-localité quantique ne peut pas être combattue "à priori" juste en disant qu'on utilise des trous noirs. Si, d'une manière ou d'un autre, il existe une stratégie pour les être humains de réussir un jour le même "prodige" que ce que font les téléphones prédits par la TQ, de toute façon la thèse de Chruch sera probablement" violée à ce moment-là même.

marco · February 2017

D'accord, merci !

Georges Abitbol · July 2017

Bonsoir,
je suis tombé.e par hasard sur cet article, qui, je l'espère, apportera des informations utiles !

marco · November 2017

@Georges: Merci. Je n'avais pas vu ton message.

Thèse de Church

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 6