Skip to Main content Skip to Navigation
Conference papers


Fabien Givors 1, * Grégory Lafitte 1 
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien Givors Connect in order to contact the contributor
Submitted on : Thursday, June 27, 2013 - 11:17:51 PM
Last modification on : Friday, August 5, 2022 - 3:02:59 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 4:46:17 AM


Publisher files allowed on an open archive


  • HAL Id : lirmm-00839381, version 1



Fabien Givors, Grégory Lafitte. Sub-Computabilities. FCT: Fundamentals of Computation Theory, Aug 2011, Oslo, Norway. pp.322-335. ⟨lirmm-00839381⟩



Record views


Files downloads