Skip to Main content Skip to Navigation
Conference papers

Sub-Computabilities

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839381
Contributor : Fabien Givors <>
Submitted on : Thursday, June 27, 2013 - 11:17:51 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 4:46:17 AM

Files

slendersubc.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00839381, version 1

Collections

Citation

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

Share

Metrics

Record views

201

Files downloads

502