Discussion:Oméga de Chaitin

Introduction

J'ai un peu relu. L'introduction mériterait d'être reprise (pas toujours claire, "un peu promotionnelle"). est-ce que quelque chose d'aussi simple que ce qu'il y a sur la version anglaise conviendrait ? Proz (d) 2 mars 2009 à 01:21 (CET)

J'ai un petit problème à la lecture de l'introduction : l'hypothèse de Riemann n'a-t-elle pas été vérifiée il y a un an ou deux ? - Alexis Chazard (désolé je ne suis pas sur ma machine, et n'ai pas mes identifiants sous la main)

Vous devez confondre. Le jour où elle sera démontrée, cela fera énormément de bruit. Voir hypothèse de Riemann. Cordialement --Jean-Christophe BENOIST (d) 11 novembre 2010 à 13:13 (CET)

Définition

La définition ne correspond pas à la version anglaise, qui est me semble-t-il celle de l'article de Solovay (la fonction universelle a un seul argument obtenu en concaténant le programme et la donnée, il faudrait préciser mais c'est assez clair pour la suite). Ca revient peut-être au même via codage ... D'où vient celle-ci ? Proz (d) 2 mars 2009 à 09:45 (CET)

En fait c'est un peu tout l'article qu'il faudrait reprendre. Je partage ton avis sur la clarté, et pourquoi pas une traduction de l'intro anglaise. Il me semble que la définition est une traduction de l'article anglais, en tout cas celle ici. Donc je ne te suis pas trop quand tu dis qu'elles sont différentes. --Jean-Christophe BENOIST (d) 2 mars 2009 à 10:45 (CET)

Il s'agit de la définition préliminaire de fonction universelle (le paragraphe est initulé "contexte"). Elles sont bien différentes (j'ai écrit en quoi, il est vrai que ça pourrait être plus clair sur en:). Après visite de l'historique, la version anglaise a changé depuis peu, donc ça semble bien une traduction mais de l'ancienne version. Je préfère la version actuelle sur en:, qui me semble plus intuitive, et dont on est sûr qu'elle est correcte (c'est celle de l'article de Solovay). Proz (d) 2 mars 2009 à 22:23 (CET)

Valeur approchée

Oméga de Chaitin a-t-il une valeur approchée et si oui quelle est elle? Xavier Combelle (d) 16 décembre 2010 à 15:12 (CET)

1/ Il y a une infinité de nombres Oméga de Chaitin (voir intro) et non un seul. 2/ On peut parfois en calculer les premières décimales, voir Oméga de Chaitin#Calculabilité d'un nombre Oméga. --Epsilon0 ε₀ 16 décembre 2010 à 15:29 (CET)

Si je comprends bien il y a plusieurs nombre oméga de Chaitin car il y en a un pour chaque machine de turing considéré? Xavier Combelle (d) 17 décembre 2010 à 15:12 (CET)

Pour chaque machine du Turing universelle, oui. Est-ce que tu trouves que ce n'est pas assez clair dans l'article ? (n'hésites pas à le dire !) Cordialement --Jean-Christophe BENOIST (d) 17 décembre 2010 à 15:32 (CET)

Oméga ou Ω?

Dans le début de l'article, on utilise "oméga", alors qu'à la fin on utilise

Ω, je pense qu'il vaudrait mieux utiliser uniquement Ω en précisant au début de l'article la notation. Jean 5 5 (d) 21 juillet 2012 à 20:15 (CEST)☺

Honnêtement, "Oméga" est plus employé dans les sources que "Ω". Je pense qu'il vaut mieux employer "Oméga". --Jean-Christophe BENOIST (d) 21 juillet 2012 à 23:27 (CEST)

Le sujet de la notation revient d'actualité, avec en plus "Omega" vs "omega". En fait, si on considère cette source, d'un spécialiste du sujet, si ce n'est LE spécialiste français, Tarap (d · c · b) n'avait pas pas tort (et c'est pour cela que j'ai laissé la modif). Bien que c'est moi qui ai écrit à l'origine avec un grand "O" par réflexe, je serais plus pour la version de Tarap, en fait. Qu'en penses-tu Dfeldmann (d · c · b) ? Cordialement --Jean-Christophe BENOIST (discuter) 20 juillet 2014 à 10:51 (CEST)

L'usage de Oméga au lieu de $\Omega$ tient simplement à des limitations d'ordre typographique de certaines sources, il n'y a aucun doute que ce soit bien la deuxième version à conserver. Ramzan (discuter) 20 juillet 2014 à 11:40 (CEST)

Mmm... Bon, je précise mon commentaire de diff. 1) <math>\Omega</math> produit $\Omega$, et <math>\omega</math> produit $\omega$. 2) Une source raisonnable est (de Chaitin) The halting probability Omega : Irreductible complexity in pure mathematics, qui, il faut bien le dire, n'utilise Omega que dans le titre, mais n'aurait aucun problème à écrire $\Omega$ (même dans une grande police grasse), me semble-t-il. De même, Delahaye utilise dans ce texte oméga dans les phrases et $\Omega$ (ou $\Omega _{U}$) dans les formules. Je n'ai pas assez de sources sous la main pour être sûr, mais il me semble bien avoir vu plus souvent Oméga (ou Omega) que $\Omega$ (et que oméga), même chez des utilisateurs de (La)TeX...--Dfeldmann (discuter) 20 juillet 2014 à 14:06 (CEST)

Bon, le problème est loin d'être capital (c'est le cas de le dire ). Mais je vais voir ce que fait Chaitin. "Faire comme les sources" reste le mot d'ordre. --Jean-Christophe BENOIST (discuter) 20 juillet 2014 à 15:20 (CEST)

Chaitin et Calude utilisent le plus souvent "Omega" avec un grand O (et surtout $\Omega$). Donc, finalement, l'idéal serait peut-être d'utiliser davantage $\Omega$ dans l'article, et "Omega" quand c'est en toutes lettres. Cordialement --Jean-Christophe BENOIST (discuter) 20 juillet 2014 à 18:25 (CEST)

La voix de la sagesse ! Ramzan (discuter) 20 juillet 2014 à 19:13 (CEST)

TI divers ?

Je prends au hasard la fin du paragraphe sur les résultats démontrables à l'aide de la connaissance de Omega (équivalents, soitit en passant, à la donnée d'un oracle, donc correspondant, dans la hiérarchie arithmétique, au premier niveau au dessus des machines de Turing) : "Cependant, tout cela reste théorique. En pratique, la méthode pour restituer les machines qui s'arrêtent à partir d'un nombre Oméga (autrement dit, pour "décompresser" un nombre Oméga, voir Détermination des programmes qui s'arrêtent à partir du nombre Oméga) est si longue qu'elle est inapplicable en pratique. En effet, il est nécessaire d'attendre que tous les programmes qui doivent s'arrêter s'arrêtent avant de connaitre le statut de chaque programme. Comme il existe jusqu'à 2 ^N programmes de longueur N bits, et qu'un programme individuel peut théoriquement s'arrêter au terme d'un temps arbitrairement long, et que l'ordre de grandeur de N pour les problèmes mathématiques intéressants est de l'ordre du millier, il serait nécessaire d'attendre l'arrêt de jusqu'à 2^1000≃10^301 programmes. Même si la moyenne des temps des programmes qui s'arrêtent est de l'ordre de la nanoseconde (ce qui est déjà en soi inenvisageable), l'âge de l'univers n'y suffirait pas." Ce texte est assez grotesque contestable pour quiconque a lu l'articleCastor affairé (ou, dans un autre genre, Hiérarchie de croissance rapide) ; j'aimerais bien savoir quelle source a été consultée (même si Delahaye se laisse parfois aller à des remarques tout aussi douteuses)--Dfeldmann (d) 27 janvier 2013 à 13:02 (CET)

Il est vraiment dommage que tu aies employé le terme "grotesque". Je ne savais pas que tu te laissait parfois aller à ce genre de qualificatif douteux, qui - justifié ou non - ne devrait jamais être utilisé en PdD, et qui risque de revenir en boomerang à celui qui l'emploie dans le second cas.

Deux choses sont sourçables, et vont être sourcées (par Chaitin lui-même) : 1) La décompression du nombre Oméga est trop longue en pratique 2) Le nombre de bits pour les théorèmes "intéressants" est de l'ordre du millier. Dans les sources, il n'y a pas d'"application numérique", et il est vrai que celle-ci n'est pas sourçable. Cela ne me pose pas de problème de l'enlever, bien que je trouve qu'elle éclaire le propos, et qu'elle est certainement raisonnable. Le propos de ce paragraphe est de souligner 1). Je n'ai pas compris si tu remettais en cause 1), ou l'application numérique qui explique 1).

Je pense que tu n'as pas dû comprendre le paragraphe en question, et il y a peut-être des éclaircissements à apporter. C'est exactement du même ordre que de dire que on ne peut espérer calculer un jour la fonction du Castor affairé au delà de n=10 en un temps physiquement accessible. En fait Castor affairé dit exactement la même chose. Cordialement, tout de même, en espérant que tu laisses l'usage - justifié ou non encore une fois - de ces qualificatif à d'autres, car ils n'apportent JAMAIS quelque-chose de bon dans une discussion. --Jean-Christophe BENOIST (d) 27 janvier 2013 à 16:12 (CET)

Bonjour, en faite on dit que le problème de l’arrêt n'est pas "truth table" réductible à Oméga. Cela implique qu'il n'existe pas d'algorithme travaillant en temps bornnable par une fonction calculable qui permet de transformer les n premiers bits de Omega en les 2^n premiers bits du problème de l’arrêt. La remarque est donc totalement fondé. Cependant je trouve que la façon dont est rédigé la remarque dans l'article n'est pas géniale car le problème est d'attendre que tout les programmes s’arrêtent (et donc d'attendre au moins une fois un temps Castor affairé) mais pas d'attendre un temps 10^300 (qui est un temps gentiment bornnable par une fonction calculable).Antoinetav (d) 27 janvier 2013 à 21:47 (CET)

Je pense que tu dois avoir raison. Disons que prendre 1 nano-seconde par machine qui s'arrête est une borne min calculable, qui déjà donne le résultat à démontrer, donc je pense que on pourrait tout de même mettre CQFD au bout du paragraphe. En revanche, le temps moyen, ou le temps max n'est pas calculable, mais le résultat est déjà démontré avec la borne min. Il est vrai que je pensais pas que cette application numérique pourrait être problématique : je vais l'enlever, c'est le plus simple, et c'est dommage que les sources ne donnent pas d'illustration de cela. Merci pour ton commentaire ! Cordialement --Jean-Christophe BENOIST (d) 28 janvier 2013 à 09:52 (CET)

Numéro d'un programme ?

Je n'ai pas compris certaines de tes modifications d'aujourd'hui, Pierre ([1]). Je ne comprends pas pourquoi tu parles de "numéro" de programme. A moins que l'ensemble du programme soit considéré comme un numéro, ce qui est possible, et même utilisé dans certains procédures de diagonalisation, mais toutes les définitions de Oméga disent bien que |p| est la longueur du programme, pas la longueur du numéro d'un programme (par exemple MathWorld, et beaucoup beaucoup d'autres. Et - de même - c'est bien le programme qui est tiré aléatoirement, et pas le "numéro d'un programme" (à moins, encore une fois que "numéro d'un programme = le programme", mais quel est l'intérêt de présenter les choses ainsi ?). Parler de numéro obscurcit le propos et n'est pas conforme à la formulation habituelle des sources : pourquoi parler de numéro ? Cordialement --Jean-Christophe BENOIST (discuter) 28 août 2013 à 13:28 (CEST)

A la réflexion, je crois voir la portée de ta nuance, mais il y a un problème de toutes manières. Cela me fait rendre compte qu'il y a un point qui n'est pas suffisamment développé/clair dans l'article : est-ce que l'oméga est la probabilité qu'un programme quelconque (y compris invalide syntaxiquement) s'arrête, en supposant qu'un programme invalide s'arrête, ou est-ce la probabilité qu'un programme valide syntaxiquement s'arrête, ce qui implique de les numéroter et de tirer le numéro aléatoirement en effet. Mais dans les deux cas, ce n'est pas la longueur du numéro qui est utilisée (voir MathWorld entre autres). Autre problème : j'ai toujours vu qu'une des raisons pour lesquelles les programmes devaient être auto-délimités était de pouvoir arrêter le tirage aléatoire du programme (et non de son numéro) bit après bit. Ce point est à développer dans l'article. Cordialement --Jean-Christophe BENOIST (discuter) 28 août 2013 à 17:39 (CEST)

Tout à fait, d'ailleurs, ça n'a aucun sens clair de tirer un numéro de programme aléatoirement (quelle est la distribution de probabilité choisie sur N?) ; non, on tire au hasard des bits jusqu'à tomber sur la séquence 000000, mettons, qui est le code de fin de programme (et on se débrouille pour que toutes les séquences se terminant par 000000 (et où 000000 n'apparait pas avant) aient un sens). L'article de Chaitin est très clair à ce sujet. En revanche, les formules données dans l'article sont fausses (je sais, elles sont fausses aussi dans MathWorld), parce que si on autorise des programmes p de même longueur n(p) dans la somme $\Omega =\sum _{p\ halts}2^{-n(p)}$, il n'y a aucune raison que Omega < 1--Dfeldmann (discuter) 28 août 2013 à 18:16 (CEST)

Elle est fausse dans toutes les sources alors ! La somme converge à cause des inégalités de Kraft (en:Kraft's_inequality), étant donné qu'une branche de l'arbre représentant les programmes possibles ne peut être prolongée par un autre programme. Une branche qui se termine "coupe" tout l'arbre en dessous, et les noeuds en dessous ne peuvent contribuer à la somme (programmes auto-délimités).

En revanche, je n'ai aucune source qui parle de se qui se passe si le programme tiré aléatoirement ne fait pas partir du langage. Bizarre. --Jean-Christophe BENOIST (discuter) 28 août 2013 à 20:56 (CEST)

Il y a une allusion "en passant", sans insister, à cela dans cette source [2] « Imaginons maintenant qu’on utilise ce procédé pour engendrer au hasard des programmes de la machine universelle U, et qu’à chaque fois qu’on trouve un programme correct pour U on le fasse fonctionner. Alors, ou bien le programme tourne indéfiniment, ou bien il finit par s’arrêter ».

Il n'y a donc pas besoin de numéroter les programmes corrects pour en tirer un aléatoirement, on se contente d'ignorer les tirages invalides.--Jean-Christophe BENOIST (discuter) 28 août 2013 à 23:19 (CEST)

Oh, oui (enfin, il faut montrer que la somme est <1, pas seulement qu'elle converge); encore un moment de passage à vide (mais c'est bien parce que les programmes sont autodélimités que ça marche). Bref, supprimer cette histoire de numéros s'impose (d'autant qu'elle est pas dans les sources)--Dfeldmann (discuter) 29 août 2013 à 03:51 (CEST)

Bon tu as eu raison de changer mon texte si ce que je dis est erroné. Mais quoique l'article soit assez clair, en général, je pense qu'il a des défauts au niveau de la terminologie. N'étant pas un grand spécialiste de la complexité de Kolmogorov, ( quoique ça me fascine et que je me suis trouvé à faire des recherches assez liées à cette théorie) je ne suis pas sûr que tout ce que j'écris est correct.

• Une machine de Turing universelle exécute d'autres machines (à partir de leur codage) pas des programmes. Il n'y a pas de concept de programme dans la théorie des machines de Turing.
• La limite d'un programme (probablement d'une machine) n'est pas définie et je dois dire que je ne sais pas ce que c'est.
• Il en est de même de la notion de programme auto-délimité.
• La taille d'une machine de Turing (je ne dis pas d'un programme car je ne sais pas ce que c'est), n'est pas précisément définie, ce qui est un comble quand on dit plus loin que le nombre Oméga est parfaitement défini et que c'est ce qui fait son intérêt. Comme je ne connais que le numéro associé à une machine de Turing comme quelque chose qui l'identifie complètement et qui a une taille, j'ai cru qu'en remplaçant programme par numéro (ou codage dans les entiers) j'étais plus correct.

Bref, je pense que si j'ai écrit des choses incorrectes, l'état actuel de l'article n'est pas tellement meilleur. --Pierre de Lyon (discuter) 29 août 2013 à 11:55 (CEST)

La question est surtout : l'état de l'article est-il plus "incorrect" que celui des sources desquelles il s'inspire ? Les remarques que tu fais ne sont-elles pas applicables également aux articles de Delahaye ou Chaitin, qui présentent les choses exactement de la même façon ? Si non, quels sont les points qui plus "incorrects" que les sources, ou quelles sont les sources plus "correctes" que Delahaye/Chaitin ?

Je suis d'accord avec toi que l'on peut approfondir certains points comme la notion de longueur de programme, et que certaines terminologies (comme "programme") sont des abus de langage, mais des abus de langage utilisés par les meilleures sources vulgarisatrices. On peut être plus précis, plus mathématique, éviter les abus de langage, mais l'article sera-t-il plus clair ? Un article de Wikipédia se doit d'être précis, mais aussi vulgarisateur, et je trouve que le niveau de vulgarisation de Delahaye est exactement au bon niveau de compromis entre la rigueur et la vulgarisation, et que Wikipédia devrait être à ce même niveau et le prendre en exemple. D'ailleurs son talent de vulgarisateur est reconnu par un Prix d'Alembert et par Pour la Science. Mais tu peux bien sûr fournir des sources exemple d'un niveau de vulgarisation qui te semblerait plus approprié, sur ce sujet, ce serait très intéressant.

En attendant, on peut développer la notion de longueur, et d'autres notions, mais dans un autre article, peut-être pas dans celui-ci, avec les liens internes qui vont bien. Cordialement --Jean-Christophe BENOIST (discuter) 29 août 2013 à 13:25 (CEST)

Que puis-je dire sinon que je récuse ces arguments d'autorité? En revanche, je dis que moi qui ai lu les premiers chapitres du livre de Li et Vitanyi, j'ai du mal à me retrouver dans ces concepts non définis. J'insiste sur le fait que je ne sais pas ce qu'est un programme auto-délimité, ni ce qu'est la limite d'un programme. Or je pense avoir quelques compétences en machine de Turing et en vulgarisation. Cela m'empêche de comprendre bien ce qu'est ce nombre Oméga. Je doute qu'un lecteur moins bien informé puisse comprendre et ne soit pas effrayé. --Pierre de Lyon (discuter) 29 août 2013 à 16:19 (CEST)

J'ai dit juste au dessus que ces notions devraient en effet être développées par des liens internes. Nous sommes donc tout à fait en accord sur ce point je crois. Sinon, je ne savais pas si tu trouvais l'article actuel "incorrect" (d'après toi) car il reportait mal les sources ou parce-que les sources étaient elles-mêmes "incorrectes", ce qui est une question factuelle et légitime. Et, dans le cas où tu trouvais les sources "incorrectes", j'essayais de les défendre et de montrer leur notabilité par des prix ou des reconnaissances, ce qui n'est pas un argument d'autorité, mais une manière très habituelle de procéder dans WP, où nous devons éviter les jugements personnels sur telle ou telle source, et encore moins les pondérer par nos propres qualités et expertise, mais plutôt mettre en évidence l'avis des autres sur ces sources. Aller, je crois qu'il y a une voie de sortie à tout cela qui est de développer les notions que tu signales, et à juste titre. Cordialement --Jean-Christophe BENOIST (discuter) 29 août 2013 à 16:45 (CEST)

D'autre part, dans ce contexte, les textes de Chaitin lui-même ne sont pas des sources primaires ; d'ailleurs, il s'auto-vulgarise fort bien lui-même... Je n'ai pas en ce moment le temps d'aller relire ça, mais il me semble bien l'avoir à l'époque lu et compris ; reste donc seulement à le restituer sans trop le déformer.--Dfeldmann (discuter) 29 août 2013 à 16:48 (CEST)

Programme et limite d'un programme

J'essaie de me mettre dans la peau d'un lecteur lambda de wikipédia qui lit l'article. Je ne sais pas ce qu'est le domaine d'une machine de Turing universelle, je clique sur le lien et là on me parle d'encodage des tables d'action, mais pas de programme, encore moins de limite d'un programme. Comment améliorer l'article pour qu'il soit plus compréhensible (et si je peux me permettre plus « correct » ) --Pierre de Lyon (discuter) 29 août 2013 à 17:32 (CEST)

Non, le vrai problème, c'est que toute la partie rigoureuse est traitée dans le paragraphe 5. Il faudrait rédiger ça de telle sorte que le lecteur lambda voit les idées "en gros", et soit rassuré par l'annonce d'une section rigoureuse plus loin dans le texte, où les mots mal définis ou ambigus le seront plus précisément. Mais à première vue, cette section 5, bien que non sourcée, semble répondre correctement à vos questions.--Dfeldmann (discuter) 29 août 2013 à 18:44 (CEST)

Peut-être que le fait que le lecteur ne sache pas qu'il lit une partie non rigoureuse est le vrai problème, mais je ne ressens pas ça en lisant l'article. Je pose un autre problème, qui est le suivant: mon lecteur lambda rencontre dès le début de l'article des concepts qu'il ne connaît pas et ne comprend pas, par exemple "programme" et quand il clique pour se les faire expliquer, on lui parle d'autres chose. --Pierre de Lyon (discuter) 31 août 2013 à 16:06 (CEST)

"Non rigoureux" est peut-être un peu exagéré : moins rigoureux que des formules mathématiques, que Oméga_de_Chaitin#D.C3.A9monstration_formelle_de_la_formule, certainement (mais qu'en pense le lecteur lambda ?), mais aussi rigoureux que ceci ou cela (qui convient mieux au lecteur lambda) : je l'espère et c'est le but. Mais cela n'empêche pas que on peut sans aucun doute faire encore mieux que l'état actuel, et que on peut tout à fait développer - en supplément - tout un pan de cette article en notations formelles, qui existe d'ailleurs déjà à l'état d'embryon.

L'intro, qui parle de "programme informatique" (trop général) peut tout à fait être améliorée et précisée : cette expression et le gros de l'intro date d'avant le refonte [3]. Tu as tout à fait raison d'attirer l'attention sur ce point. La notion de "programme" que connait le lecteur lambda est vraiment très proche de la notion dont il est question dans l'article : une chaine de caractères dans un langage donné indiquant à une machine universelle ce qu'elle doit faire et quel résultat elle doit produire. Si quelqu'un pense à cette notion, si un programmeur pense à un programme C++ ou Pascal, il ne sera pas fondamentalement trompé. Et c'est pourquoi ce terme est largement employé aussi par les sources que j'ai cité en exemple ci-dessus, et bien d'autres. Mais cela pourrait être tout de même plus précis. Là ou je suis d'accord avec toi, il faut que le lecteur "non lambda", qui connaît bien les machines de Turing, s'y retrouve aussi et sache exactement et précisément de quoi il est question. C'est clairement une voie d'amélioration de l'article. --Jean-Christophe BENOIST (discuter) 31 août 2013 à 18:08 (CEST)

Pour la notion de "programme", j'ai lié sur la notion de fonction partielle récursive, plus précise que programme informatique. fonction partielle récursive est à l'état d'ébauche : je l'ai un peu augmenté, et sourcé, ce matin, mais il reste du travail. Pour les autres notions, c'est à suivre. --Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 12:16 (CEST)

C'est pas franchement un bon choix je pense, ça définirait la notion de programme par une spécification, et pas directement. Un programme calcule une fonction partielle récursive, mais un programme n’est pas une fonction partielle récursive, c'est plutôt l'implémentation d'un algorithme pour une machine donnée (et qui ne termine pas dans certains cas, ce qu'on perd parce que c'est simplement une valeur indéfinie pour la fonction partielle) ... — TomT0m ^[bla] 1 septembre 2013 à 16:15 (CEST)

Autre manière de le dire là bas : en:Computable function « Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines » Du coup y faire référence alors que l’oméga de Chaitin dépend de la machine c'est maladroit je pense. — TomT0m ^[bla] 1 septembre 2013 à 16:25 (CEST)

Le choix n'est pas de moi, j'ai recherché dans les sources avant de raccorder le concept précis. Calude, dans la source que j'ai utilisé (voir dans fonction partielle récursive), utilise le terme "fonction" aussi bien pour la fonction mathématique que pour un "programme" d'une MTU, et dans le contexte précis du calcul du nombre Oméga, de la complexité de Kolmogorov etc.. « We view a computer as a partial recursive function which reads a string (over some alphabet) as an input and then may or may not print another string, as output. » .. « Definition 3.1 : A computer is a p. r. function $\phi :A^{*}\times A^{*}{\xrightarrow {\text{o}}}A^{*}.A$ » ; dans le contexte, "computer" est dans le sens "Machine de Turing" bien sûr. Pour le moment j'en reste à la définition 3.1 de Calude. Je vais voir dans le Li/Vityani comment la chose est abordée. Quelle serait un meilleur choix d'après toi, et d'après quelle source ? --Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 18:14 (CEST)

Calude parle de ce sujet à un autre endroit du livre, encore plus clairement : « A partial function $\phi :A^{*}{\xrightarrow {\text{o}}}A^{*}$ is called partial recursive if there exists a partial recursive function $f:N{\xrightarrow {\text{o}}}N$ telle que $\phi (x)=string(f(string^{-1}(x)))$ » (p. 3). On passe de la fonction $f$ à la fonction $\phi$ par une conversion de l'entier naturel en chaine, et réciproquement. Je m'en vais d'ailleurs ajouter cet élément dans fonction partielle récursive.--Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 18:24 (CEST)

(Il y a un doublon avec Fonction semi-calculable) C'est surtout les défintions en fait, j’ai pas de sources, je sais bien qu'on peut sans trop de soucis amalgamer une machine avec la fonction qu’elle calcule mais tant qu'on est dans le rigorisme autant y aller jusqu'au bout (j’ai le souvenir d'une discussion sur le Thé sur la différence entre une opération et la valeur calculée, ou un truc dans ce genre, c'est un peu le même genre de distinction ici amha) . Je chercherai des sources mais je pense pas avoir de difficulté à appuyer mon point de vue :) — TomT0m ^[bla] 1 septembre 2013 à 18:33 (CEST)

En tout cas c'est formulé comme ça dans l'article en anglais, et ça me convient parfaitement « Suppose that F is a partial function that takes one argument, a finite binary string, and possibly returns a single binary string as output. The function F is called computable if there is a Turing machine that computes it. » (au passage, l’article en anglais donne une définition que les informaticiens devraient très bien comprendre: un programme prefix-free est un langage reconnu par une grammaire ... ) — TomT0m ^[bla] 1 septembre 2013 à 18:51 (CEST)

Ah oui en effet, il y a un doublon. Quel est le nom que devrait avoir l'article fusionné d'après toi ?

Li/Vitanyi fait en effet le distinguo entre les deux (exemple 1.7.4 p 31) « It is important to distinguish between a function ψ and a name for ψ. A name for ψ can be an algorithm that computes ψ, in the form of a Turing machine T ». On pourrait rendre le lien interne plus subtil et précis encore, pourquoi pas, mais en tout cas on est très proche du but tout de même, et bien mieux que programme informatique. Quel lien interne préconiserais-tu (s'il existe) ? N'hésites pas à modifier l'article, d'ailleurs. --Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 18:54 (CEST)

Pour moi le bon lien c'est programme informatique, même si il est moins théorique :) Mais si tu ne l'aimes pas, ce qu'il faudrait peut être faire c'est l’améliorer plutôt que d'essayer de faire rentrer des choux dans des carottes, et ajouter une section sur les programmes pour les machines de Turing Universelle par exemple. Exemple : Ce billet sur le blog d'un pur théoricien à pour titre programmer les machines de Turing est difficile, c'est bien de ça qu'il s'agit : programmer des machines. Et le résultat est un programme. Ou vraiment si tu est allergique créer un article programme (informatique théoriques) mais ça me semble couper les cheveux en quatre. — TomT0m ^[bla] 1 septembre 2013 à 19:14 (CEST)

C'était plutôt Pierre qui faisait des remarques sur ce lien, et mon action répondait à sa remarque. Bah, chacun a l'impression que l'autre coupe les cheveux en quatre on dirait, comme faire le distinguo (pour reprendre la terminologie de Li/Vitanyi) entre le "name" de ψ et la "fonction" ψ, qui ont beaucoup plus de rapports que des choux et des carottes. C'est plutôt la différence entre un choux et l'image d'un choux, la carte et le territoire, qui ne change pas grand chose pour la compréhension de l'article (même si ce distinguo peut être important dans d'autres circonstances). Je ne suis allergique à rien, je ne vois pas bien pourquoi tu emploies ce genre de termes. Je ne sais pas, en tout cas, s'il est meilleur pour WP de consacrer du temps à peaufiner ce lien interne, ou de procéder à la fusion de fonction partielle récursive et Fonction semi-calculable (quel nom d'article pour la fusion à propos ?), et à son développement. Je pense que je vais plutôt embrayer sur ce chantier, mais n'hésites pas à modifier cet article. Je ne suis allergique à rien, même pas à un retour sur programme informatique. Il faut plutôt demander à Pierre. --Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 19:51 (CEST)

Le nom, pas de préférence tant qu'il y a une redirection et que les deux versions sont mentionnées, peu importe en ce qui me concerne. On va attendre l’avis de Pierre alors sinon :) — TomT0m ^[bla] 1 septembre 2013 à 20:00 (CEST)

Je suis sûr qu'il y a une solution qui satisfait tout le monde, et je pense que on n'est pas loin du but. Sinon, je pense, pour la fusion, conserver fonction partielle récursive comme titre. Saint Google donne une nette prééminence de cette dénomination sur l'autre, mais on peut changer sans pb. Cordialement --Jean-Christophe BENOIST (discuter) 1 septembre 2013 à 20:59 (CEST)

Je sus d'accord avec vous: nous ne sommes pas loin du but. Ceci dit, je veux bien relire les propositions que vous faites et dire ce que j'en pense.--Pierre de Lyon (discuter) 1 septembre 2013 à 21:57 (CEST)

Dans le Calude, il explique pourquoi il assimile un ordinateur à une fonction (d'ailleurs je crois qu’il a une ambiguité entre fonction (informatique) et fonction (mathématique) qui mérite d'être levée. La formulation, si on met le lien vers fonction récursive partielle, doit expliquer cette assimilation aussi bien que la source et ne pas la noyer vers une redirection qui pourrait être pas très claire pour le lecteur néophyte. La fonction informatique porte cette idée de programme et d'exécution par définition, la fonction mathématique non, c'est elle qui peut être calculable ou pas. Autre manière de le dire, la fonction mathématique peut être définie de manière absolument non constructive, la fonction informatique par définition est définie de manière constructive: Une fonction mathématique peut être définie par un prédicat, ce prédicat définirait les pré et post conditions d'une fonctions informatique. Il peut exister une fonction informatique qui calcule la fonction mathématique, c'est comme ça qu'on définit la calculabilité si je ne me trompe pas. — TomT0m ^[bla] 16 septembre 2013 à 18:31 (CEST)

Oui, c'est exactement l'idée de fonction partielle récursive, justement. Essaye de trouver une bonne formulation, je ne vois pas très bien ce que tu veux faire exactement, mais je pense que ce sera bien, et ce sera plus clair en voyant le résultat. Cordialement --Jean-Christophe BENOIST (discuter) 16 septembre 2013 à 22:47 (CEST)

Programme auto-délimité

Cela correspond, formellement, à la notion de "prefix-free set" ou "prefix set". Un des moyens d'obtenir une "prefix-free set" est d'avoir une séquence de fin délimitant la fin de la séquence de bits, et réservée à cet effet. L'article WP anglais qui va bien est en:Prefix code qui pointe sur Code préfixe, qui est insuffisamment développé. Cette source Self-Delimiting Kolmogorov complexity est assez complète et formelle sur le sujet et parle en prime des inégalités de Kraft dont nous savons parlé plus haut. Nous avons du travail ! Cordialement --Jean-Christophe BENOIST (discuter) 30 août 2013 à 00:33 (CEST)

Special:Diff/135695590

Cette image est évidemment inutile. C'est seulement une représentation de la lettre grecque oméga; elle ne contient pas rien pertinent sur le nombre de Chaitin lui-même. Elle est seulement décorative. Keφr (discuter) 23 mars 2017 à 16:28 (CET)

Sur un téléphone ou une tablette, il est bon (agréable) que chaque article ait une image, même si elle n'est que symbolique. --Pierre de Lyon (discuter) 23 mars 2017 à 16:56 (CET)

Grotesque, vous avez dit grotesque ?

En m'excusant à l'avance auprès de Jean-Christophe Benoît, je voudrais tout de même m'insurger quelque peu contre tout le paragraphe consacré à l'utilisation "pratique" du nombre de Chaitin (supposé connu) : d'abord, tous les théorèmes (et pas seulement ceux de la forme "il existe n entier tel que P(n)") sont analysables : il suffit de faire tourner une machine sur toutes les démonstrations possibles... Je m'étonne qu'aucune source ne mentionne cette banalité, signalée dans d'autres contextes par tout le monde, de Gödel à Hofstadter. Ensuite, le castor affairé d'une machine de Turing à 6 états prend déjà bien plus de 10^100000 étapes ; cela rend les minorations données du cas "1000 états" quelque peu dérisoires, non ?--Dfeldmann (discuter) 5 septembre 2017 à 16:03 (CEST)

Le paragraphe en question spécifie bien que l'oméga n'est pas utilisable en pratique. Certes, il ne dit pas que c'est grotesque, mais je suppose que ce n'est pas la modif que tu voudrais voir dans ce paragraphe, et je ne vois pas bien ce que tu voudrais modifier.

Cela dit, il ne faut pas confondre une démo, qui serait probablement beaucoup beaucoup plus grande que 1000 bits (l'article ne parle pas de 1000 états, mais d'une longueur de 1000 bits), avec le programme dont l'arrêt ou le non arrêt démontrerait le théorème. Par exemple la démo du théorème de Fermat est extrêmement longue, mais le programme pour le vérifier (ou l'infirmer) est extrêmement court. Donc lancer un programme de vérification sur toutes les démos possibles jusqu'à des mégabits de longueur (au moins) n'est - a priori - ni plus ni moins grotesque (pas moins en tout cas) que de décompresser un oméga de 1000 bits. --Jean-Christophe BENOIST (discuter) 5 septembre 2017 à 17:31 (CEST)

Non, non  ; je n'ai pas de sources sous la main, mais c'est vraiment trivial (et voir aussi à ce sujet le théorème d'accélération de Gödel) : une machine de Turing qui déroule sous forme codée tous les théorèmes (et teste si elle a trouvé une proposition fixée donnée), c'est "facile" à construire, ça a relativement peu d'états, et c'est une des façons de démontrer les théorèmes d'incomplétude de Gödel. Autrement dit, il ne s'agit pas de vérifier une démonstration (qui pourrait d'ailleurs être fort longue), mais de produire toutes les démonstrations "correctes" possibles par ordre de longueur. Quand à ce que je trouve "grotesque" (c'est un clin d'oeil, hein, en vrai, je trouve juste ça trompeur, voire erroné) c'est a) l'affirmation selon laquelle l'Omega ne permet que de démontrer des théorèmes liés au problème de l'arrêt, alors qu'il permet en fait de savoir si une proposition donnée de ZFC est démontrable, réfutable, indécidable, ou même si ZFC est contradictoire ! b) je maintiens qu'il est bon d'expliquer que cela n'aurait aucune utilité pratique (un Oracle, c'est d'ailleurs vraiment nettement mieux ), mais que l'illustrer par le calcul des 10^300 programmes possibles (de 1000 bits) rate complètement le fait que l'exécution de programmes beaucoup plus courts (6 états, soit, je suppose, moins de 50 bits) peut déjà prendre 10^100000 étapes avant de s'arrêter...--Dfeldmann (discuter) 5 septembre 2017 à 19:12 (CEST)

C'est ce que dit l'article, qui parle du castor. Tout ce que je peux dire c'est que je n'ai pas lu cette contradiction dans mes sources (Chaitin, Delahaye, Calude..), et que c'est présenté tel que dans ces sources. Mais comme tout ce beau monde (sans ironie !) gravite autour de Chaitin, il faut peut-être des sources plus indépendantes, et bien sûr on peut compléter l'article. --Jean-Christophe BENOIST (discuter)

Proposition d'anecdote pour la page d'accueil

Une proposition d'anecdote pour la section « Le Saviez-vous ? » de la page d'accueil, et basée sur cet article, a été proposée sur la page dédiée.
N'hésitez pas à apporter votre contribution sur la rédaction de l'anecdote, l'ajout de source dans l'article ou votre avis sur la proposition. La discussion est accessible ici.
Une fois l'anecdote acceptée ou refusée pour publication, la discussion est ensuite archivée là.
(ceci est un message automatique du bot GhosterBot le 06 mars 2019 à 16:15, sans bot flag)