Prouver qu'un ensemble est récursif primitif

Raskolnikov · July 2021

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 ? 125328

christophe c · August 2021

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)

Raskolnikov · August 2021

Bonjour, merci pour ta réponse.

christophe c a écrit:

pourquoi as-tu besoin de le prouver dans ton contexte?

En fait, je trouvais le premier volume du Cori Lascar clair (y compris les démonstrations). J'ai beaucoup plus de difficultés à suivre dans ce cinquième chapitre du deuxième tome. Sans doute que les notions abordées y sont plus difficiles (en tout cas pour moi). Il y a beaucoup de passages du style "le lecteur intéressé vérifiera sans peine que" ou "il est évident que". Ce que j'aurais aimé, c'est au moins une preuve détaillée dans un cas (pour bien saisir la méthode générale). J'ai trouvé des exemples sur le net, mais les auteurs prennent justement appui sur le Cori Lascar et considèrent de la même manière que c'est "évident". Dans le même esprit, il est demandé de trouver (par exemple) une machine de Turing calculant $\lambda x.x^{2}$. Je ne parviens pas à le faire et j'ai beau chercher un peu partout, peu d'auteurs ont la même description d'une machine de Turing (même si j'ai cru comprendre que tous les modèles sont équivalents et calculent les mêmes fonctions). J'aurais aimé voir sur un exemple une telle construction détaillée. Ce n'est pourtant pas faute d'avoir cherché et compulsé de nombreux ouvrages.

christophe c · August 2021

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 machine

Raskolnikov · August 2021

Merci pour la réponse. Cela ne m'aide pas beaucoup cependant à construire une machine de Turing calculant le carré d'un nombre entier.

christophe c · August 2021

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.

Raskolnikov · August 2021

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.

christophe c · August 2021

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).

Prouver qu'un ensemble est récursif primitif

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24