Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
108 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Récursivité et complexité

Envoyé par TigerFou 
Récursivité et complexité
il y a onze années
avatar
Bonjour,

Je me pose les questions suivantes :

Comme la complexité (de Kolmogorov) d'un objet est la taille du plus petit programme réduit qui génère cet objet (par une machine de Turing universelle), et puisqu'on peut d'une certaine manière assimiler un système formel à une machine de Turing;
Peut-on dire que la complexité d'un système formel (pour une logique prédéfinie) soit la taille de son axiomatique "minimale" ?

En gros, peut-on "classer" la complexité des théories selon la taille de leur axiomatique ?
Genre : fini < récursif < récursivement énumérable < approximable < compressible

Cordialement,
johann
Re: Récursivité et complexité
il y a onze années
avatar
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
Re: Récursivité et complexité
il y a onze années
C'est un sujet un peu désuet, mais qui abcp été étudié entre 1950 et 2000. Soit dit en passant, on ne connait, je crois, de théories naturelles (ens des axiomes récursif) dont l'ensemble des théorèmes ne soit ni récursif, ni récursivment énumérable universel
Re: Récursivité et complexité
il y a onze années
avatar
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
Re: Récursivité et complexité
il y a onze années
Un truc qui pourrait 't'intéresser dans la même veine: tu quotientes $\R$ par (E) $x-y\in \Q$ et tu regardes l'ensemble des classes L. Tu supposes (pas Axiome du choix) que tous les ensembles de réels sont Lebesgues mesurables.

Alors il y a un ultrafiltre sigma additif sur L: autrement dit, "une classe fantome" qui se comporte comme si elle était un élément de L, vue de l'extérieur.

Cela tient au fait que tout ensemble stable par E est de mesure nulle ou de comesure nulle. Si tu aimes la complexité élevée, cette classe fantome est l'archétype même: rien ne la dépasse!!! C'est la complexité maximum (mais pas en profondeur logique, je ne sais plus quel est le nom de cette complexité)
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 708, Messages: 1 376 285, Utilisateurs: 25 644.
Notre dernier utilisateur inscrit EPFL.


Ce forum
Discussions: 2 211, Messages: 43 966.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page