Je viens de trouve ca existe deja ?
Soit f fonction calculable de l'ensemble des mots infinis dans {0,1} dans {0,1} alors il existe une entier n et une fonction g de {0,1}^n dans {0,1} tel que pour tout m mot infinis de {0,1}: f(m)= g(m|[0;n])

tu t'es planté dans les quantificateurs à mon avis, c'est plutôt que pour tout m dans {0,1}^ω, il existe un entier n tel que [...]. C'est l'exemple classique pour illustrer la notion de continuité de Scott en théorie des domaines.

https://en.wikipedia.org/wiki/Scott_continuity
https://en.wikipedia.org/wiki/Domain_theory

Un contre exemple à ta version c'est (par exemple) la fonction f qui renvoie la parité du nombre de zéros avant le premier 1.

Le 25 février 2021 à 19:52:53 Jacana a écrit :
tu t'es planté dans les quantificateurs à mon avis, c'est plutôt que pour tout m dans {0,1}^ω, il existe un entier n tel que [...]. C'est l'exemple classique pour illustrer la notion de continuité de Scott en théorie des domaines.

https://en.wikipedia.org/wiki/Scott_continuity
https://en.wikipedia.org/wiki/Domain_theory

Un contre exemple à ta version c'est (par exemple) la fonction f qui renvoie la parité du nombre de zéros avant le premier 1.

merci pour le contre exemple j'etais sur d'avoir la preuve en tete je vais la rediger pour voir ce qui deconne

non en fait ca marche pas ton contre exemple: le mot 00000000000000000000....

voila je viens de taper la preuve pour etre sur:

Il est evident qu'a un mot infini m fixe ce n existe, c'est simplement le rang du mot m le plus grand ou le programme se rend.
Appelons h la fonction qui a un mot infini m associe son n.
On va raisonner par recursivite, soit h non borne sur l'ensemble des mots commencant par 0,
soit non borne sur l'ensemble des mots commancant par 1. Imiginons non borne sur l'ensemble des mots commancant par 1
alors on recommence soit h non borne sur l'ensemble des mots commencant par 10 ou 11...
On obtient un mot infini: L. Notons h de ce mot = k, alors h de n'importe quelle completion de L|[0;k] est egale a k. Or on a vu qu'il devait exister des completion de L|[0;k] de h aussi grande que voulue: contradiction.

T'as raison, ma fonction f est pas calculable. Peut être que ton énoncé est vrai du coup, si c'est le cas ça doit être une conséquence de la théorie des domaines de Scott je pense (je vérifie après, là je dois faire les courses avant que ça ferme)

(Si ça t'intéresse, un pdf en français ici, l'exemple des mots infinis est à la section 7 : https://www.irif.fr/~mellies//mpri/mpri-m2/mpri-mellies-notes-de-cours-1.pdf )

en confiance je vais essayer d'affaiblir les hypotheses en passant de f calculable a:

Soit f programme qui ne s'arrete pas forcement et changeant sa sortie mais
tel que pour tout mot m, il existe un temps t tel que la sortie soit fixe apres t.

alors peut etre ca marche encore. SpoilAfficherMasquer

J'ai feuillete ton lien jacana, bon forcement pour moi c'est super dur a lire mais de ce que j'ai compris ca traite plutot de fonction calculable de l'ensemble des suites dans l'ensemble des suites

ca marche pas obv jacana je t'enjoint a essayer a essayer de trouver le theoreme qui marche avec la nouvelle hypothese

Ta preuve est ok. Je ne connais pas d'endroit où ce théorème soit écrit (je suis pas du tout expert en calculabilité), mais à mon avis ça doit être considéré comme du « folklore » (ce qui veut pas dire qu'il soit trivial, c'est assez contre-intuitif, d'ailleurs je me suis fait avoir). En gros ça dit que la notion de calculabilité que tu utilises n'est pas vraiment bien adaptée pour travailler avec des mots infinis. C'est sans doute pour ça que d'autres notions de calculabilité existent (« type I computability » et « type II computability »). Il existe aussi des machines de Turing à temps infini (« ITTM »).
Le livre Computable Analysis de Klaus Weihrauch a l'air d'être une bonne source pour la calculabilité sur des données infinies, peut être que ton résultat y est (je l'ai pas lu)

J'ai feuillete ton lien jacana, bon forcement pour moi c'est super dur a lire mais de ce que j'ai compris ca traite plutot de fonction calculable de l'ensemble des suites dans l'ensemble des suites

Oui l'exemple qui est donné n'est pas le même que le tien, mais c'est une théorie générale qui s'applique aussi bien à des fonctions des suites dans {0,1}. Mais c'est toujours pas la même chose que ce que tu fais toi (mon dernier lien dit "calculable au sens paresseux", quoi que ça veuille dire). Entre autres, les domaines de Scott parlent de fonctions partielles qui peuvent soit renvoyer un résultat, soit boucler à l'infini. Auquel cas mon « contre-exemple » avec la parité du nombre de zéros fonctionne, où f est pas définie sur l'entrée 0^ω.
Tu fais quoi comme études par curiosité ?

j'ai fais des etudes de maths mais pas tres poussees (capes)

j'aurais du dire je t'invite au lieu de je t'enjoins dans mon dernier post lol

Le 25 février 2021 à 21:57:25 _I_I_I_ a écrit :
j'aurais du dire je t'invite au lieu de je t'enjoins dans mon dernier post lol

a priori je vois pas le problème avec ton nouvel énoncé pour moi ça change rien, mais je sais pas exactement ce que tu veux dire par un programme qui "change sa sortie"

Le 25 février 2021 à 22:30:20 Jacana a écrit :

Le 25 février 2021 à 21:57:25 _I_I_I_ a écrit :
j'aurais du dire je t'invite au lieu de je t'enjoins dans mon dernier post lol

a priori je vois pas le problème avec ton nouvel énoncé pour moi ça change rien, mais je sais pas exactement ce que tu veux dire par un programme qui "change sa sortie"

exemple soit un programme qui lit dans l'ordre les chiffres du mot infini et qui a chaque etape du calcul "donne 1 en sortie" si il n'a jusqu'a present vu qu'un seul 1 et qui "donne 0 en sortie sinon" . Alors ce programme finit par valoir 1 indefinement sur les mots contenant 1 seul 1 et 0 sinon.
Mais ce n'est pas la calulabilite classique le programme tournant indefiniment. Pour preuve l'ensemble des mots ne contenant qu'un seul n'est 1 pas calculable classiquement

On s'en branle

Avec juste les hypotheses donnees un resultat se rapprochant d' il existe
un nombre (meme infini) de prefixe sur lesquelles f est constante tel que chaque mot infini soit dans une des classe de prefixe est tres peu probable (j'ai certain contre exemple a un resultat que je croyais juste et qu'est plus faible).
Neanmoins en rajoutant une hypothese j'ai trouve un resultat tres contre intuitif.
L'hypothese rajoute est l'insenbilite au condition initiale. C'est a dire qu'un mot infini
m a la meme image que m troncature d'un nombre fini de ses premiers termes.
Notations:
* soit m prefixe de M mot infini on dit que f change de sortie en m si f change de sortie la premiere
fois qu'elle atteint le dernier caractere de m. Notion bien definie independante de M.
Par un gros abus de notation soit E un ensemble de mot on dit que f change de sortie en E si il existe un mot de E ou f change de sortie.
*soit m fini on note Cf(m) l'ensemble des completions fini de m

Theoreme: sous les hypotheses: f est constante (!)

preuve: supposons f non constante. Alors necesseraiment il existe un mot m fini ou f change de
sortie. Si f ne change de sortie sur Cf(m) qu'en m ou avant, alors f etant insensible au condition intiale, par troncature de m,elle ne change pas de sortie sur l'ensemble des mots finis, et donc aussi des mots infinis et est donc constante .
Il existe donc un element de Cf(m) ou f change de sortie. Notons le m1. Par le meme argument
f change de sortie en Cf(m1) en un mot m2. En repetant l'operation on obtient une suite infinie de mot:
m,m1,m2...., tel que mn+1 est une completion de mn et tel que pour tout n, f change de sortie en mn.
En notant M le mot limite on a que f change une infinite de fois de sortie sur M, contradiction car f doit stabilisee.

C'est fou non ?

mes amities a quine