Suite récursive
Bonjour, je me demande si, pour toute suite d'entiers positifs, alors il existe une suite récursive tel que la proportion de termes appartenant à la première suite est non nulle :-)
Je suis donc je pense
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour tous $p,q$, on pose $\overline u_p(q):=u_p(q)$ si $u_p$ est définie en $q$, et $\overline u_p(q)=0$ sinon.
On pose pour tout entier $n\in \N$, $v_n := 1+ \max \{\overline u_p(q) \mid 0 \leq p,q\leq n\}$.
Alors pour tout entier $n$ et tout $k\geq n$, $u_n$ n'est pas définie en $k$ ou bien $v_k > u_n(k)$.
Donc pour toute suite récursive il n'y a qu'un nombre fini de termes où cette suite coïncide avec $v$.
Mais la suite que tu vient de définir est elle même récursive
Pour toute fonction $p:\N \to \{0,1\}$ et pour tout $n\in \N$, on pose $f_p(2n):=f_p(2n+1):= 2n+2+p(n)$.
Alors la suite $x^{(p)}$ définie par récurrence par $x^{(p)}_0:=0$ et $x^{(p)}_{n+1}:= f_p \left (x^{(p)}_n \right )$ est telle que $x^{(p)}_n = p(n-1)$ modulo $2$ pour tout $n\geq 1$. Ces suites sont donc toutes différentes.
(après ça dépend si elle doit être récursive ou pas
Ce n'est pas possible.
Cette suite n'est pas récursive.
"La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle"
Si ce n'est pas possible, bien meilleure est la définition "une suite récursive est une fonction de $\N$ dans $\N$ calculable par un programme informatique". La réalisation de ce que certaines choses sont, pour des raisons fondamentales, impossibles à faire via des programmes informatiques est l'une des découvertes les plus importantes de toute l'histoire des sciences. Cela provient des travaux de Turing, de Church et de Gödel dans les années 30 et d'autres.
Plus généralement, les fonctions récursives se définissent à partir des fonctions récursives primitives et la définition de ces dernières est donnée ici https://fr.wikipedia.org/wiki/Fonction_récursive_primitive
on peut éviter ce formalisme (nécessaire évidemment pour que tout puisse correctement être défini), en disant juste que cela revient à considérer des fonctions calculables par algorithmes (par exemple, dans le langage informatique de son choix).
Du coup, un ensemble E de $\mathbb{N}$ est récursivement énumérable s'il existe un algorithme capable de l'énumérer, c'est-à-dire de sortir les uns après les autres les éléments de E. Et un ensemble est récursif si un algorithme peut dire si un élément de $\mathbb{N}$ est dans E ou non (en clair, on introduit un élément de E dans l'algorithme et celui-ci sort 0 ou 1).
@l
0°) Préliminaires
0.1°) Si $A,B$ sont des ensembles nous noterons $FP(A,B)$ l'ensemble des fonctions partielles de $A$ dans $B$ c'est à dire les fonctions définies sur une partie de $A$ et à valeurs dans $B$.
0.2°) Soit $(E_i)_{i \in I}$ une famille d'ensembles. Il existe une famille $(E'_i)_{i\in I}$ d'ensembles deux à deux disjoints, tels que pour tout $j\in I$, $E_j$ est en bijection avec $E'_j$ (il suffit de poser pour tout $k\in I$, $E'_k := E_k \times \{k\}$).
La réunion des $(E'_i)_{i \in I}$ ($= \bigcup_{i \in I} E_i \times \{i\}$)s'appelle "union disjointe des $(E_i)_{i\in I}$" et se note $\coprod_{i\in I} E_i$. Ci-dessous nous identifierons pour tout $i$, $E_i$ et la partie $E_i \times \{i\}$ de cette union disjointe qui est en bijection avec lui.
1°) Fonctions récursives:
1.1°) Définissons des notations (nous ne donnons pas les ensembles de définition des fonctions considérées; ils sont évidents d'après le contexte quoique lourds à écrire mais le lecteur pourra les reconstituer sans peine):
(i) On note $s$ l'application qui à $n\in \N$ fait correspondre $n+1$.
(ii) On note $z$ l'application constante qui à $n\in \N$ fait correspondre $0$.
(iii) Pour tous entiers $p,q$ avec $p\leq q$ on note $\pi_p^q$ l'application qui à $(a_1,...,a_q)\in \N^q$ fait correspondre $a_p$ (autrement dit la projection sur la $p$-ième coordonnée).
(iv) (opérateur de composition) pour tous entiers $p,q$ et tous éléments $f_1,f_2,...,f_q\in FP(\N^p,n)$ et $g\in FP(\N^q,\N)$, on désigne par $C_{p,q} (g,f_1,...,f_q)$ la composée de $g$ et de l'application $x\in \N^p \mapsto \left (f_1(x_1,...,x_p), f_2(x_1,...,x_p)... f_q(x_1,...,x_p) \right )$. $C_{p,q} (g,f_1,...,f_q)$ appartient à $FP(\N^p,\N)$.
(v) (operateur de définition des fonctions par récurrence) pour tout entier $n$, tout $u \in FP(\N^n,\N)$et tout $v\in FP(\N^{n+2},\N)$ on note $Rec_n(u,v)$ l'élément de $FP(\N^{n+1},\N)$ défini pour tous entiers $x_1,...,x_n$ par $Rec_n(u,v) (0,x_1,x_2,...,x_n):= u(x_1,x_2,...,x_n)$ et $Rec_n(u,v)(k+1,x_1,...,x_n):= v \left (k, Rec_n(u,v)(x_1,...,x_n),x_1,...,x_n \right)$
(vi) (plus petit entier annulant une expression) Pour tout entier $n$, tout élément $w\in FP(\N^{n+1},\N)$ et tous $(x_1,...,x_n)\in \N^n$, $\mu_n w (x_1,...,x_k)$ désigne l'unique entier $\ell$, s'il existe, tel que $w(\ell,x_1,...,x_n)=0$ et $w(k,x_1,...,x_n)\neq 0$ pour tout entier $k$ strictement inférieur à $\ell$ (autrement dit c'est le plus petit entier $j$ tel que $w(j,x_1,...,x_n)$ s'annule, sous réserve que ces quantités soit toutes définies pour des indices inférieurs à $j$).
1.2°) Définition des fonctions récursives:
On appelle fonctions récursives partielles (ou tout simplement fonctions récursives) les éléments du plus petit sous-ensemble de $\coprod_{n \in \N} FP (\N^n,\N)$ contenant $s,z$ et $\pi_p^q$ pour tous $p,q\in \N$, et stable par les opérations $C_{p,q}$, $Rec_n$ et $\mu_n$ pour tous $p,q,n\in \N$.
Autrement dit ce sont les fonctions qui peuvent s'écrire entièrement avec des $\pi_p^q,s,z,C_{p,q},\mu_n,Rec_n$ pour tous $p,q,n$ (et des parenthèses). Cette liste d'opérations de base peut être vue comme la liste des instructions d'un langage de programmation rudimentaire.
Comme un programme écrit dans ce langage est de longueur finie, l'ensemble des fonctions récursives est dénombrable (NB: le fil part très loin alors que c'est la SEULE propriété dont on a eu besoin pour répondre aux interrogations de Quentino37 ;-))
Cependant:
Pour tout entier $d$, toute fonction $\N^d\to \N$ qui peut être définie par un langage de programmation quelconque, est récursive.
(admis car technique).
Un langage de programmation permettant (en faisant abstraction des problèmes concrets de limitation de mémoire des appareils) d'exprimer toutes les fonctions récursives est dit Turing-complet.
Exemples de fonctions récursives:
-somme, produits, puissances de nombres entiers (ils sont successivement définis par récurrence à partir de $s$). La soustraction l'est aussi mais c'est plus délicat.
-test d'égalité d'un nombre avec zéro (c'est la fonction $n\mapsto 0^n$).
Il existe moult autres façons de définir les fonctions récursives, plus efficaces (le laïus ci-dessus est un peu lourd) notamment en exploitant la remarque ci-dessus (exemple: les fonctions récursives sont les fonctions définissables par les termes du lambda-calcul, ou mieux, de sa soeur aînée la logique combinatoire. Vite un moteur de recherche). Mais ceci est la définition historique sauf erreur, apparue (années 30) alors même que l'invention de l'ordinateur n'était pas encore achevée. Je pense que c'est cette définition est celle qui capture le mieux l'idée qu'une fonction récursive est une fonction programmable sur les nombres entiers.
NB: le sous-ensemble des fonctions récursives qui s'écrivent sans minimiseur $\mu_n$ est appelé "ensemble des fonctions récursives primitives". Elles sont toutes définies partout (seul $\mu_n$ entraîne des problèmes de non-définition et correspond en programmation à des boucles qui ne s'arrêtent pas). Ce n'est pas une équivalence cependant (une fonction récursive célèbre de $\N^2$ dans $\N$ - la fonction d'Ackermann - est partout définie et non récursive primitive).
Livres conseillés:
-"Les démonstrations et les algorithmes - Introduction à la logique et à la calculabilité" de Gilles Dowek
-le tome 2 de "Logique mathématique" de Lascar et Cori contient un chapitre sur ces notions.
Bonne journée.
Fr. Ch.