Récursivité et complexité

Bonjour,

J'ai dis une bêtise ?
Les différents niveaux de récursivité ne peuvent-ils pas donner une mesure de la taille (disons de la "taille en calcul") d'un ensemble, d'une certaine façon ?

Cordialement,
johann

Bonsoir,

C'est vrai que les théories d'axiomatique non récursivement énumérable ne sont pas fascinantes, puisqu'on ne peut même pas déterminer l'appartenance d'une proposition à cette axiomatique, mais elles existent !

Bon, après qu'on aie pas envie d'appeler ça une théorie, c'est compréhensible...

Par exemple, une théorie dont les propositions tenteraient d'exhiber de façon constructive des parties du nombre de Chaitin Omega* (ou tout autre nombre réel incalculable) n'est pas axiomatisable puisque le seul moyen d'en construire une est d'exhiber l'ensemble des digits de ce nombre, formant un ensemble incompressible.

De la même manière, la théorie des corps finis, ou des sous-corps de C, n'est pas axiomatisable, je me trompe ?

* probabilité qu’un calculateur universel s’arrête lorsqu’on lui donne un programme tiré au hasard. Ses digits sont incalculables car le problème de l'arrêt est indécidable.

Que ces question ne soient pas trop d'actualité n'empêche pas qu'elles soient intéressantes .

Cordialement,
Johann