Question sur le problème de l'arrêt

dylan61
dylan61
dans Logiciels pour les mathématiques
Bonjour à tous,

J'ai une petite question concernant le problème de l'arrêt. On sait bien que ce problème est indécidable, à cause des programmes qui se référencent eux-mêmes. Qu'en est-il de la restriction de ce problème à l'ensemble $\{(code, paramètre) ; code \neq paramètre\}$. C'est-à-dire, qu'en est-il si on interdit l'autoréférence ? Le problème est-il toujours indécidable ?

Merci à vous.

Réponses

  • christophe c
    christophe c
    Il ne suffit pas de mettre un simple $\neq$ pour éviter l'auto-référence :-D Elle est beaucoup plus hégémonique que ça.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Je n'ai pas son nom et je ne crois pas quece soit un nom très connu et c'est dommage même si ce n'est pas très dur à "deviner" ce qu'il a fait. Mais il y a même un gars qui a prouvé que quand $n$ tend vers l'infini, la proportion des programmes de longueur n tels que la théorie T décide s'ils s'arrêtent ou pas tend vers 0. Et ce quelque soit la théorie T que tu choisis, du moment qu'elle est consistante et récursivement énumérable. Une ptite recherche documentaire donnerait le nom du gars et la date d'article.

    Cela dit, pas besoin de cet article, il y a bien plus impressionnant et bien plus trivial et ça ne porte pas de nom d'auteur tant c'est un exercice routinier: quelle que soit la théorie usuelle que tu choisisses, le nombre de suites fnies de 0 et 1 que la théorie est capable de prouver comme ayant un programme qui la génère assez long comparé à sa longueur à elle est fini, purement et simplement (on est sur du plus cash que "proba qui tend vers 0").

    Et la preuve de ça est routinière puisque s'il y en avait une infinité, tu lancerais la production comme suit: find the suivante que T prouve être non courtement générable jusqu'à dépasser 10^500 en longueur puis s'arrêter et tu aurais la contradiction que tu viens de générer une suite en quelques mots programmés sur un pc qui est prouvé par T ne pas pouvoir l'être.

    Bref, tu es cerné, entouré d'indécidable partout, arg, pas de répit. :-D
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • dylan61
    dylan61
    J'avoue ne pas avoir compris la preuve que tu donnes, ni ce qu'on entend par un programme "assez long". Peux-tu donner plus de précision ?
  • christophe c
    christophe c
    oui, soit $A$ l'ensemble des suites finies S de 0,1 telles que le plus court programme qui génère S dépasse en longueur la racine carrée (par exemple) de la longueur de S.

    Programme: fais défiler toutes les preuves de la théorie T et chaque fois que T sort un théorème du genre "S est dans A", mesure la longueur de S. Arrête-toi quand longueur(S) > 10^(10^(10^999)

    Ce programme mesure 494237 symboles. S'il s'arrête un jour, il affichera une suite finie S de longueur > 10^(10^(10^999) dont la théorie T prouve qu'elle ne peut pas être générée par un programme plus court que la racine carrée de 10^(10^(10^999)

    Je te laisse prouver que 494237 est pourtant bien plus petit que la racine carrée de 10^(10^(10^999)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • dylan61
    dylan61
    D'accord, merci. Ma question reste toujours, existe-t-il une preuve que l'ensemble donné dans la question n'est pas récursif ?
  • dylan61
    dylan61
    Finalement ta première réponse m'a aidé à voir plus clair. Pour toute fonction récursive, il existe une infinité de machines de Turing la calculant, on a donc une infinité d'indices de machines de Turing (ou de codes de programme) associés à cette fonction. Encore pire, on peut construire des fonctions récursives (primitives) qui renvoient, à partir de l'indice d'une fonction récursive, un autre indice de cette fonction strictement supérieur au précédent.

    Appelons $\beta$ l'une de ces fonctions et $\phi$$m$ la machine de Turing simulant la fonction récursive à une variable d'indice $m$. On pose alors :

    $ A = \{$ $(m, x)$ $;$ $m \neq x \wedge \phi$$m$$(x)$ est défini $\} $

    $ B = \{$ $(m, x)$ $;$ $m = \beta(x) \wedge \phi$$m$$(x)$ est défini $\} $

    $ C = \{$ $x$ $;$ $\phi$$x$$(x)$ est défini $\} $

    On sait, par la preuve de l'indécidabilité du problème de l'arrêt, que $C$ n'est pas récursif.
    Supposons maintenant que $B$ soit récursif, la fonction $\chi$$c$ suivante serait alors une fonction caractéristique de $C$ :

    $\chi$$c$ $(x) = 1 \Leftrightarrow \chi$$B$$(\beta(x), x) = 1$

    Où $\chi$$B$ serait la fonction caractéristique de $B$. Ceci est absurde car $C$ n'est pas récursif, donc $B$ ne l'est pas aussi.

    De la même manière, on trouve que $A$ n'est pas récursif, car s'il l'était, $B$ le serait aussi en vertu de cette fonction :

    $\chi$$B$$(m, x) = 1 \Leftrightarrow \chi$$A$$(m, x) = 1 \wedge m = \beta(x) $

    Donc $A$ n'est pas récursif. L'autoréférence est bien hégémonique comme tu l'as dit.

    Je voudrais, si possible, avoir ton avis sur cette preuve.
  • christophe c
    christophe c
    <<Mon avis>>, Qu'entends-tu par là? Je le donne facilement en général (euphémisme :-D ) mais là, je ne sais pas quoi te dire, oui, c'est hégémonique.

    Il y a une spécialité (les pauvres je ne sais pas si elle reçoit beaucoup de crédit) qui étudie le préordre de la Turing-réductibilité en dessous du récursivement énumérable universel. Cette structure est superriche et c'est tout un bordel épouvantable. Peut-être en tapant "méthode de priorité de Friedberg" trouveras-tu de quoi jouir (il y a de quoi, ça dépote même si c'est ancien)

    Un exercice simple est de prouver qu'il y a un ensemble énumérable dont les seules parties récursives qui lui sont disjointes sont les parties finies.

    Un autre exemple est qu'en lambda calcul (et c'est naturel!!) aucun ensemble récursif ne respecte la beta-équivalence (sauf le tout le monde et le vide)

    Tu as aussi plein d'ensemble récursifs qui n'ont pas de complexité minimum dans le sens que pour toute complexité $f$ d'un programme qui le calcul, il existe une fonction $g$ qui est aussi une de ses complexités et telle que $2^g\leq f$.

    Etc, etc...

    Si tu veux chercher (compte-tenu de la motivation de ton premier message) des exemples de problèmes ou bien ouverts ou bien fermés mais tordus où on a "la pleine puissance" mais où il y a un peu de taf pour arriver à une contradiction, il y en a plein de le fil "il est facile de". Je peux t'en signaler un ouvert officiel (enfin en 2000 quand j'étais encore au jus):

    1) Existe-t-il un ensemble infini $E$ et une surjection de $E^2$ sur $P(E)$ (axiome du choix interdit)

    Un autre de mon cru. Pas ouvert mais tordu.

    2) Soit $A$ un anneau commutatif non unitaire. On suppose que toute fonction $f$ du premier ordre*** qui associe à un idéal $J$ de $A$ une partie $f(J)$ de $A$ est telle que qu'il existe un idéal $J$ tel que $J = $ l'idéal engendré par $f(J)$. Prouver que tous les éléments sont égaux.

    Ces amusettes sont assez satisfaisantes me semble-t-il pour un esprit qui veut tenter de toucher le bord entre l'autoréférence et le consistant. Bon, elles sont de mon cru, mais j'en ai plein d'autre.

    *** Tu ne peux pas parler des nilpotents, et c'est pas vraiment facile de tenter le radical de Jacobson sans 1.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • dylan61
    dylan61
    Je ne pense pas avoir le niveau pour tout ça. Mais je pense être arrivé à une réponse satisfaisante à ma question. Merci pour ton aide, je vais continuer mon investigation sur l'informatique théorique. (:D
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 35

GaBuZoMeuKarnajMagnéthoraxPaul BroussousShadows AsgardThierry PomaVassilliabiguine_equationgai requinmtho5pappusstfjzeste +22 Invités