Prouver qu'un ensemble est récursif primitif
Bonjour,
je bute sur ce genre d'exercices. Comment prouve-t-on de manière rigoureuse que l'ensemble $I_{p}$ est récursif primitif ? J'imagine qu'il faut montrer qu'il est l'intersection d'ensembles eux-mêmes récursifs primitifs. L'ensemble $\{x\mid \beta_{3}^{1}(x) \geq p+1\}$ est récursif primitif. Ensuite, il faudrait que je prouve que l'ensemble $\{x\mid \beta_{3}^{3}(x)=u\}$ est aussi récursif primitif, et donc que $u$ peut s'écrire comme une fonction récursive primitive de $x$. Est-ce ainsi qu'il faut procéder ?
je bute sur ce genre d'exercices. Comment prouve-t-on de manière rigoureuse que l'ensemble $I_{p}$ est récursif primitif ? J'imagine qu'il faut montrer qu'il est l'intersection d'ensembles eux-mêmes récursifs primitifs. L'ensemble $\{x\mid \beta_{3}^{1}(x) \geq p+1\}$ est récursif primitif. Ensuite, il faudrait que je prouve que l'ensemble $\{x\mid \beta_{3}^{3}(x)=u\}$ est aussi récursif primitif, et donc que $u$ peut s'écrire comme une fonction récursive primitive de $x$. Est-ce ainsi qu'il faut procéder ?
Réponses
-
Comme dit dans la photo, "il serait très ennuyeux".
En gros il suffit pour être primitif récursif que tu saches que le calcul va s'arrêter "assez vite". Autrement dit, dans la programmation, aucun ingrédient ne sera mis de recherche d'un témoin entier, dont l'existence incertaine, nécessite de lancer un process qui s'arrêtera que quand on l'aura trouvé***, avec en plus un "pas sûr qu'il existe".
Le fait de faire ça "se sent" et "se voit" quand tu fais le programme. Le reste ne sont que des itérations, compositions banales dont la borne est déjà dans tes mains. Par exemple si tu programme for i :=1 to 1000 do TRUCDEJAPROUVEPRIMITIFRECURSIF, ca l'est encore
Question du coup, pourquoi as-tu besoin de le prouver dans ton contexte?
*** exemple : démarre à 15 et cherche un entier n dont la somme des diviseurs est 7n-3 n'a pas de raison évidente a priori de terminer. Elle est de la forme :
Function sniffage(x):
if SOMDIV(x)=7x-3 then return x else sniffage(x+1)
et peut boucler (mais tu sais toi-même d'avance que tu prends ce risque)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Bonjour, merci pour ta réponse.christophe c a écrit:pourquoi as-tu besoin de le prouver dans ton contexte?
-
De mon dictaphone.
Je t'explique rapidement pourquoi tout ce que tu sais faire peut être fait par une machine de Turing.
Cette affirmation c'est la thèse de Church.
La preuve que je donne n'est donc pas irréfutable aux bordures puisque l'affirmation est métaphysique mais elle convient à la routine quotidienne.
Quand tu agis, tu as une petite mémoire instantanée qui est très limitée (processeur, registre, états de la machine...)
Mais ça ne t'empêche pas d'utiliser ton environnement par exemple du sable mouillé pour mémoriser des choses. (ruban(s))
Par ailleurs les états dans lesquels tu te trouves en agissant forment des ouverts fermés d'un compact (ta façon d'évoluer dans ton calcul d'un état personnel vers un autre)
Il le partitionnent sont donc en nombre fini.
Conclusion tu es une machine de Turing dans le cadre de ce genre d'action.
Pour construire une telle machine il te suffit donc de psychanalyser ta démarche est de la recopier comme programme de la machineAide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Merci pour la réponse. Cela ne m'aide pas beaucoup cependant à construire une machine de Turing calculant le carré d'un nombre entier.
-
Pur la construire (c'est fastidieux mais trivial), demande-toi juste "comment je ferais, moi, pour calculer le carré d'un nombre entier écrit en binaire sur une place où j'ai le droit de me servir du sable mouillé comme mémoire"
La machine tu l'auras.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Dans le livre, ils n'utilisent pas un codage binaire pour les nombres. Chaque nombre est codé sur une bande ($x$ est représenté par $x$ "bâtons"). Le résultat est écrit sur la dernière bande et ils utilisent éventuellement des bandes supplémentaires pour les calculs intermédiaires. Il faudrait alors que la machine écrive $x^{2}$ bâtons sur la deuxième bande.
-
C'est assez étonnant car tu es prévenu que c'est HYPERFASTIDIEUX, mais facile, mais tu veux le faire quand-même et après tu donnes le sentiment de venir ici non parce que tu n'y arrives pas, mais plutôt pour "implorer" que ça ne dure pas 58H non stop sans dormir ;-)
Je te le dis franchement: si on me demande une machine de Turing qui calcule la fonction carrée et qu'on me file 3000E, je réponds "oui, ok, je suis SÛR de pouvoir vous la livre dans .. 4 jours"
Si on ne paie pas, c'est niet et puis c'est tout.
Sois conscient que tu ressembles à une personne qui "voudrait voir de ses yeux" que le nombre 500000 est fini. Bin, bon courage, car l'argument c'est "on pourrait le prouver sans coupure", mais hélas, n'importe qui te le prouvera AVEC COUPURE si force s'impose. Sans coupure, faudra payer cher les gens.
(Précision: les coupures sont l'analogue des sous-prorgammes et on peut prouver qu'elles ne sont pas NECESSAIRES (d'où les machines de Turing ne sont pas plus pauvres que les machines de Turing à sous-programmes). Cependant, elles sont UTILES pour raccourcir les tâches).Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres