Sub-Computabilities

Fabien Givors 1, * Grégory Lafitte 1
* Auteur correspondant
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Every recursively enumerable set of integers (r.e. set) is enumerable by a primitive recursive function. But if the enumeration is required to be one-one, only a proper subset of all r.e. sets qualify. Starting from a collection of total recursive functions containing the primitive recursive functions, we thus define a sub-computability as an enumeration of the r.e. sets that are themselves one-one enumerable by total functions of the given collection. Notions similar to the classical computability ones are introduced and variants of the classical theorems are shown. We also introduce sub-reducibilities and study the related completeness notions. One of the striking results is the existence of natural (recursive) sets which play the role of low (non-recursive) solutions to Post's problem for these sub-reducibilities. The similarity between sub-computabilities and (complete) computability is surprising, since there are so many missing r.e. sets in sub-computabilities. They can be seen as toy models of computability.
Type de document :
Communication dans un congrès
Olaf Owe; Martin Steffen; Jan Arne Telle. FCT: Fundamentals of Computation Theory, Aug 2011, Oslo, Norway. Springer, 18th International Symposium on Fundamentals of Computation Theory, LNCS (6914), pp.322-335, 2011, 〈http://fct11.ifi.uio.no/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839381
Contributeur : Fabien Givors <>
Soumis le : jeudi 27 juin 2013 - 23:17:51
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : mercredi 5 avril 2017 - 04:46:17

Fichiers

slendersubc.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00839381, version 1

Collections

Citation

Fabien Givors, Grégory Lafitte. Sub-Computabilities. Olaf Owe; Martin Steffen; Jan Arne Telle. FCT: Fundamentals of Computation Theory, Aug 2011, Oslo, Norway. Springer, 18th International Symposium on Fundamentals of Computation Theory, LNCS (6914), pp.322-335, 2011, 〈http://fct11.ifi.uio.no/〉. 〈lirmm-00839381〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

329