Paradoxe algorithmique, problème de l'arrêt
Bonjour,
Je rencontre un problème pour lequel j'ai deux raisonnements qui me semblent correctes mais qui aboutissent à des conclusions différentes. Après avoir longtemps réfléchis sur le sujet, je ne vois pas lequel de mes deux raisonnements est incorrecte.
Voici le problème:
Soit E l'ensemble des algorithmes se terminant pour tout entier en entré (si on exécute un algorithme de cette ensemble avec un entier, par exemple 3, l'algorithme se termine, il ne boucle pas à l'infini).
Cet ensemble est dénombrable (par exemple, on ordonne les algorithmes par nombre de ligne). On peut donc écrire la liste de ces algorithmes.
Soit A l'algorithme suivant:
Entré: un nombre n
Algorithme:
exécuter le n ième algorithme de E avec comme entré n
La question est : Est-ce que A appartient à E ?
Les deux raisonnements que j'ai trouvés sont les suivants:
Argument 1: A appartient à E
Soit k un entier.
L'exécution de A avec comme entré k est l'exécution du K ième algorithme de E avec comme entré k.
Les algorithmes de E se terminent pour tout entier, donc en particulier le k ième algorithme de E avec comme entré k se termine.
Donc A avec comme entré k se termine.
Donc A se termine pour tout entier et appartient donc à E.
Argument 2: A n'appartient pas à E
Si A appartient à E, alors il existe k tel que "A est le k ième algorithme de E".
Alors, l'exécution de A avec comme entré k donne:
exécuter A(k):
exécuter A(k):
exécuter A(k):
exécuter A(k):
...
Cet algorithme ne termine jamais, donc A n'appartient pas à E.
Voilà ou j'en suis. J'ai ces deux raisonnements qui aboutissent à des conclusions différentes mais les deux raisonnements me semblent totalement correctes. Il y a certainement un endroit où je me trompe mais je n'arrive pas à trouver ou... Si quelqu'un à une idée, je suis preneur.
Quelques petites infos en plus:
Ce "paradoxe" m'est apparu en regardant la vidéo de science4all: https://www.youtube.com/watch?v=mFCLGBZSHA8&t=7s
Un élément de réponse que j'ai trouvé dans cette vidéo est que l'ensemble E est dénombrable mais non calculable. Donc la liste que j'utilise ne peut pas être obtenue de manière algorithmique. On pourrait dire que c'est un problème car je me pose une question sur un algorithme en lui fournissant quelque chose qui ne peut pas être calculé par un algorithme. Mais cet ensemble est dénombrable donc en soit il existe. Rejeter le problème sous prétexte qu'il fait intervenir un élément non calculable n'est pas acceptable. En effet, la plupart des théorèmes mathématiques font intervenir des éléments non calculables.
Un autre élément auquel j'ai pensé est le problème de l'infini: E est de taille infinie. Cela peut poser quelques problèmes et j'ai réfléchis à une manière de conserver le paradoxe uniquement avec des ensembles finis:
On considère N fixé (par exemple 10 000).
On considère E, le même ensemble que plus haut mais avec comme condition supplémentaire: « les algorithmes de E ont moins de N lignes ».
Alors E devient finis et A est composé de moins de N lignes (si on prend N suffisamment grand).
Merci d'avance
-----
Envoyé par Tryss2 
