Discussion:Suite de Specker
Dernier commentaire : il y a 12 ans par Epsilon0 dans le sujet Mise en évidence de la non-calculabilité
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Mise en évidence de la non-calculabilité
modifierMerci beaucoup pour le travail de refonte. J'ai une interrogation (je n'avais pas lu l'article attentivement avant) sur la phrase La limite de cette suite n'est pas un réel calculable, puisque son développement décimal contient 4 à sa ne place si le calcul de {n}(n) termine, et 3 sinon, ce qui est une représentation du problème de l'arrêt.. Il me semble que ce n'est pas la bonne raison. Le nombre Oméga a des propriétés similaires, et n'est pas un nombre calculable. La raison tient au fait que le module de convergence ne peut pas être calculé. Mais il faudrait une référence. Cordialement --Jean-Christophe BENOIST (d) 29 juillet 2012 à 12:50 (CEST)
- Si, je crois que c'est juste (et je ne comprends en quoi ta phrase sur Omega contredirait cela).
- Du coup, on en déduit que le module de convergence de cette suite ne peut pas être calculé, mais prouver cela ne serait pas suffisant car il pourrait exister une meilleure suite ayant même limite.
- J'ai rajouté ce qu'il faut (en sourçant) dans Nombre calculable#Définitions.
- Je trouve aussi que la section "Exemple 2" manque de source, mais peut-être pas pour la même raison que toi. C'est juste que ça me semble un TI (très bon, mais complètement arbitraire dans ses choix).
- Cordialement, Anne (d) 29 juillet 2012 à 13:31 (CEST)
- Mmmm.. Cela me parait trop une "démonstration" comme : ce nombre est à l'évidence non calculable (puisque certaines de ses décimales sont par définition non calculable), donc ce nombre est non calculable, ce qui est un peu récursif. Normalement c'est module de convergence non calculable => nombre non calculable, et tu sembles dire nombre non calculable => module non calculable. Je ne sais pas s'il y a équivalence entre les deux d'ailleurs, ce serait intéressant de le savoir. En fait, ce qui me gêne est que on ne parle pas du tout du module de convergence, qui est à la base de tout je pense, surtout pour cette suite. Ce serait beaucoup plus convainquant s'il y avait une démo sur le module de convergence.
- Pour Oméga, ce que je voulais dire, c'est que c'est bien le module de convergence qui est à la base de la démo de sa non-calculabilité (qui n'est pas évidente a priori puisqu'il existe une suite calculable convergente vers Oméga). On ne se contente pas de dire "le problème de l'arrêt est à la base du nombre Oméga donc ce nombre est non calculable", comme c'est un peu le cas ici. De plus, le nombre Oméga (qui est calculé jusqu'à un certain point pour certaines machines) montre qu'il est possible de calculer, ou démontrer mathématiquement, le non-arrêt de certaines machines de Turing (voir la fin de Oméga_de_Chaitin#Calculabilit.C3.A9_d.27un_nombre_Om.C3.A9ga). Donc on peut difficilement dire "ce nombre est non calculable car sinon on saurait calculer le non-arrêt de certaines machines"[réf. souhaitée], ce qui est le cas. Ce n'est pas aussi simple. --Jean-Christophe BENOIST (d) 29 juillet 2012 à 16:15 (CEST)
- Non non, c'est bien [module de convergence calculable => nombre calculable] (et donc par contraposée : [nombre non calculable => module de convergence non calculable]), et non pas la réciproque (un réel calculable peut très bien être limite d'une « bonne » suite par définition, mais aussi d'une « mauvaise » par ailleurs, donc ces histoires de module de convergence seraient absolument hors sujet ici). Si ce nombre-ci n'est pas calculable, ce n'est pas parce que « certaines » (lesquelles ?) de ses décimales sont non calculables, mais bien parce que la suite des ses décimales n'est pas calculable. Et pour montrer que Omega n'est pas calculable, il ne suffirait pas de montrer que le module de convergence de la suite qui le définit n'est pas calculable (ça ne prouverait pas qu'il n'est pas limite d'une « meilleure » suite). Par contre l'argument qu'il code le problème de l'arrêt (pour la diagonale toute entière, et pas seulement « pour certaines machines ») est valide (et de même, le nombre de Turing n'est déjà pas calculable). Anne (d) 29 juillet 2012 à 16:44 (CEST)
- Oui, je vais méditer sur tout cela. Je crois voir ce que tu veux dire. Un devoir de vacance aussi --Jean-Christophe BENOIST (d) 29 juillet 2012 à 21:22 (CEST)
- Bonnes vacances ! Anne (d) 29 juillet 2012 à 21:43 (CEST)
- Itou, et voici un livre de plage. --Epsilon0 ε0 29 juillet 2012 à 22:06 (CEST)
- Bonnes vacances ! Anne (d) 29 juillet 2012 à 21:43 (CEST)
- Oui, je vais méditer sur tout cela. Je crois voir ce que tu veux dire. Un devoir de vacance aussi --Jean-Christophe BENOIST (d) 29 juillet 2012 à 21:22 (CEST)
- Non non, c'est bien [module de convergence calculable => nombre calculable] (et donc par contraposée : [nombre non calculable => module de convergence non calculable]), et non pas la réciproque (un réel calculable peut très bien être limite d'une « bonne » suite par définition, mais aussi d'une « mauvaise » par ailleurs, donc ces histoires de module de convergence seraient absolument hors sujet ici). Si ce nombre-ci n'est pas calculable, ce n'est pas parce que « certaines » (lesquelles ?) de ses décimales sont non calculables, mais bien parce que la suite des ses décimales n'est pas calculable. Et pour montrer que Omega n'est pas calculable, il ne suffirait pas de montrer que le module de convergence de la suite qui le définit n'est pas calculable (ça ne prouverait pas qu'il n'est pas limite d'une « meilleure » suite). Par contre l'argument qu'il code le problème de l'arrêt (pour la diagonale toute entière, et pas seulement « pour certaines machines ») est valide (et de même, le nombre de Turing n'est déjà pas calculable). Anne (d) 29 juillet 2012 à 16:44 (CEST)
Specker zurichois
modifier- Simplement parce que Specker, contrairement à Victor Hugo, a passé sa vie dans une seule ville, et que cette précision est un « plus » qui ne coûte rien.
- Il serait bon de rétablir aussi la mise en forme détruite à l'occasion de ce revert.
- Anne, 14/2/16,15h50