Diagonal de Cantor et développement décimal...

[thepasboss]

Bonjour,

je poste ici à propos d'un petit truc qui me turlupine à propos de l'argument diagonal de Cantor pour montrer que les réels ne sont pas dénombrables et qui me parait relativement profond :
sans rentrer dans les détails de l'argument que beaucoup ici connaissent, lorsque l'on prend une liste de réels et que l'on manipule leur développement décimal pour construire un réel qui n'est pas dans la liste, n'y a t il pas une hypothèse implicite faite, ou en tout cas l'utilisation d'un petit quelque chose un peu exotique ? En effet, il me semble bien que pour la "majorité" des réels, on a pas de moyen de connaitre/calculer le développement décimal des dits réels. Donc le manipuler revient à faire une manipulation "à priori" sujet à discussion, puisque l'objet manipulé est inaccessible concrètement, non ?

J'imagine bien que cela doit toucher du doigts les histoires de constructivisme et autres affaires de goûts personnels, mais je trouve la chose amusante et j'imagine qu'il y a du avoir des gens qui se sont amusé autour de ce genres de choses, donc si vous avez de la doc, des avis/connaissances sur le sujet, ou des choses approchantes, je serais ravi de les lire !

Merci d'avance.
-----

[Médiat]

Bonjour,

il me semble bien que pour la "majorité" des réels, on a pas de moyen de connaitre/calculer le développement décimal des dits réels.

Et si on ne le peut pas c'est justement parce que les réels n'est pas un ensemble dénombrable (on ne peut mettre au point qu'un nombre dénombrable de calculs).

[thepasboss]

Ah tiens d'ailleurs une petite question :

qu'est se qui m'empêche de faire le même argument diagonal en se bornant à considérer des listes de nombres calculable et arriver à la même conclusion ? J'imagine bien que le caractère dénombrable des nombres calculable doit venir d'une histoire de réunion dénombrable d'ensembles dénombrables, mais donc où est le hic que je ne vois pas ?

[Médiat]

Dans le cas des nombres calculables, le problème est un peu plus subtil :

Si on ne considère que les nombres calculables par une fonction primitive récursive, le procédé diagonal fournit un exemple de nombre "intuitivement" défini par une fonction calculable qui n'est pas primitive récursive (qui donc, existent).

Si on considère les nombres calculables au sens de Turing, l'argument diagonal a permis à Turing d'énoncer que le problème de l'arrêt des machines de turing n'est pas décidable.

[A voir en vidéo sur Futura]

[thepasboss]

Hmmm pourriez vous me communiquer un peu de doc sur ces notions de "fonction primitive récursive" et de "calculable au sens de Turing" ? Histoire que je vois un peu le sens de votre explication (ce n'est pas du tout mon domaine, mais ça m'intéresse beaucoup !)

[Médiat]

C'est très facile à trouver sur le net, par exemple : http://www.ulb.ac.be/di/ssd/jfr/slid...complexite.pdf