La calculabilité est centrée autour de la notion de fonction calculable telle que définie par Church, Kleene, Rosser et Turing au siècle dernier. D'abord focalisée sur les nombres entiers, la calculabilité a été généralisée aux ensembles, notamment par le biais de la théorie axiomatique des ensembles de Kripke-Platek. Dans cette thèse, nous définissons une notion générale de calculabilité, les sous-calculabilités, dont les axiomes sont satisfaits à la fois par de nombreux fragments récursifs de la calculabilité classique, mais également par des calculabilités d'ordre supérieur sur les ensembles admissibles. Nous montrons, sur cette structure composée d'une énumération de fonctions totales et d'une énumération de fonctions partielles, que les théorèmes classiques de calculabilité (isomorphisme de Myhill, Rogers, théorème s-m-n,point fixe de Kleene, théorème de Rice, créativité, etc.) sont présents sous différentes formes alors même que les sous-calculabilités ne comprennent qu'un fragment des objets de la calculabilité classique. Les structures de degrés associées aux notions de récursivité que nous définissons reflètent également des propriétés de la calculabilité (degrés intermédiaires, high, low, etc.), mais nos réductions étant plus fortes, une structure fine apparaît à l'intérieur même des degrés récursifs. Finalement, nous montrons que les calculabilités sur les admissibles sont interprétables dans le formalisme des sous-calculabilités. En particulier, les énumérations des ensembles alpha-finis et alpha-énumérables présents dans ce contexte nous permettent de transférer certains résultats d'un modèle à l'autre. / Computability is centered on computable functions, as defined by Church, Kleene,Rosser and Turing in the twentieth century. Initially focused on integers,computability has been generalised to sets, in particular thanks toKripke-Platek's Axiomatic Set Theory.In this thesis, we define a general notion of computability,sub-computabilities, whose axioms are satisfied by numerous recursive fragmentsof classical computability, and also by higher-order computabilities overadmissible sets. We show how in sub-computabilities, containing an enumeration oftotal functions and an enumeration of partial functions, classical theoremssuch as Myhill and Rogers isomorphisms, s-m-n theorem, Kleene's fixed-point orRice's theorem hold in a slightly different way, even if a large part ofthe objects of computability are missing. Along with each of thesesub-computabilities and their different notions of recursivity comes a structureof degrees (with intermediate, high and low degrees, etc.), refining theclassical one, our notions of recursivity being stronger.Moreover, we show how admissible computability can be interpreted through theformalism of sub-computabilities. In particular, the enumerations ofalpha-finite and alpha-enumerable sets present in this setting allowsome interesting results to be carried from one model to the other.
| Identifer | oai:union.ndltd.org:theses.fr/2013MON20160 |
| Date | 06 December 2013 |
| Creators | Givors, Fabien |
| Contributors | Montpellier 2, Durand, Bruno, Lafitte, Grégory |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0021 seconds