Question sur les fonctions calculables

[Igor21]

Bonjour a tous,

Voilà çà fait quelques jours que cette question me trotte dans la tête, mais comme mes connaissances en mathématiques sont limitées, je ne trouve pas s'il y à déjà eut une réponse.

Voici la question en question :lol3: :

Existe t-il un sous ensemble E non vide de l'ensemble des fonctions calculables C, tel que :

Pour tout couple (e1,e2) de E x E :
- la composition de e1avec e2 n'appartient pas à E.
- la composition de e2 avec e1 n'appartient pas à E.
- tout éléments de C peut s'écrire comme une suite finie de composition d'éléments de E.

( Autrement dit, existe-t-il des fonctions calculables non décomposables? )

Si oui, existe-t-il un moyen de trouver une ou plusieurs de ces fonctions?

Ces fonctions seraient à l'ensemble des fonctions calculables par rapport à la composition ce que les nombres premiers sont aux naturels par rapport à la multiplication.

Merci de votre aide...

[vincentroumezy]

Comment définis tu une fonction calculable ?

[Igor21]

C'est un fonction qui peut être calculée par une machine de Turing (et donc par un ordinateur) en un temps fini.
Elles sont aussi appelées fonction récursives.

[Ben314]

Salut,
Perso, c'est surtout la question que je n'ai pas comprise.
Vu la formulation, il me semble que E=ensemble_vide donne une solution.
On peut aussi prendre E={f} où f est n'importe quelle fonction telle que fof soit différent de f...

[Igor21]

Salut Ben merci de ta réponse,

Oui tu as raison ce sont deux solutions, mais j'ai très mal formulé le problème.

Voici une seconde tentative :

L'ensemble C des fonctions calculables muni de la composition forme un groupe. Ce que je cherche à trouver, c'est la plus petite partie génératrice E de ce groupe, c'est à dire le plus petit ensemble qui permet d'exprimer n'importe quel élément de C comme une suite finie de compositions d'éléments de E.

Ps: Je viens de corriger le premier post

[Doraki]

Les fonctions calculables et les fonctions récursives ce n'est pas la même chose.

Ensuite, si un tel ensemble E de fonctions existe, cet ensemble est "incalculable" au sens où la fonction E * N -> N qui à (f,x) associe f(x) ne peut pas être calculable.

J'ai un peu relu ton premier post, imagine que ton groupe c'est (Q,+).
Trouve moi une partie génératrice minimale de Q, ça m'intéresse.

[Igor21]

Les fonctions calculables et les fonctions récursives ce n'est pas la même chose.

D'après la thèse de Church-Turing, toute fonction calculable est récursive.

J'ai un peu relu ton premier post, imagine que ton groupe c'est (Q,+).
Trouve moi une partie génératrice minimale de Q, ça m'intéresse.

Ce n'est pas la plus petite partie génératrice de (Q,+), mais l'ensemble { | a {-1,1} , b N+ } U {0} me semble un bon début.
Quand bien même il n'y aurait pas de solution pour (Q,+), je ne vois pas en quoi cela influe sur le problème avec (C,o).

Ensuite, si un tel ensemble E de fonctions existe, cet ensemble est "incalculable" au sens où la fonction E * N -> N qui à (f,x) associe f(x) ne peut pas être calculable.

Alors là, je ne comprends pas comment tu arrive à cette conclusion. Si E est un sous-ensemble de C, tout élément de E est calculable, alors pourquoi E * N* -> N qui à (f,x) associe f(x) ne serait pas calculable ?
De plus savoir si un tel ensemble est calculable ou non n'est pas la question. Je ne cherche pas à savoir si on peut calculer ses éléments mais savoir si on peut en trouver.

[Doraki]

D'après la thèse de Church-Turing, toute fonction calculable est récursive.

Ah oui pardon j'ai confondu avec primitive récursive.
L'ennui avec les fonctions récursives partielles c'est qu'on peut pas décider si elle est totale ou si elle l'est pas.

Alors là, je ne comprends pas comment tu arrive à cette conclusion. Si E est un sous-ensemble de C, tout élément de E est calculable, alors pourquoi E * N* -> N qui à (f,x) associe f(x) ne serait pas calculable ?

Plus précisément, je dis que si tu as une fonction de N dans E, alors soit la fonction N*N -> N qui à (x,y) associe (;)(x))(y) n'est pas calculable, soit l'image de ne permet pas d'obtenir toutes les fonctions calculables, donc est incomplet.

(preuve : il est bien connu qu'il existe une bijection calculable entre N et les suites finies de N.
on définit f(x) = (x1) ° (x2) ° ... ° (xn) (x) + 1, où (x1,...,xn) = (x).
Alors f est calculable, et si f = (y1) ° (y2) ° ... ° (ym) pour une certaine suite finie (y1...ym) = (y) pour un certain entier y,
alors (y1) ° (y2) ° ... ° (ym) (y) = f(y) = (y1) ° (y2) ° ... ° (ym) (y) + 1.
Donc f(y) = f(y)+1, ce qui est impossible)

Donc tout ça pour dire que tu n'as aucune chance de pouvoir obtenir une description calculable d'un tel ensemble (s'il existe).

savoir si on peut en trouver

Ben ça dépend de l'ensemble en entier.
Si f est une fonction, si succ(x) = x+1, et si pred(x) = 0 si x=0, = x-1 si x>0,
tu peux toujours décomposer f en (f ° pred) ° succ.
Donc pour peu que (f ° pred) et succ soient dans l'ensemble, ça élimine f.
Si de tels ensembles existent, il n'y a aucune fonction f particulière qui aurait une raison profonde d'y être.