Sub-Computabilities - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011



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.


Other [cs.OH]
Fichier principal
Vignette du fichier
slendersubc.pdf (439.47 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

lirmm-00839381 , version 1 (27-06-2013)



Fabien Givors, Grégory Lafitte. Sub-Computabilities. FCT 2011 - 18th International Symposium on Fundamentals of Computation Theory, Aug 2011, Oslo, Norway. pp.322-335, ⟨10.1007/978-3-642-22953-4_28⟩. ⟨lirmm-00839381⟩
108 View
223 Download



Gmail Facebook Twitter LinkedIn More