On the information carried by programs about the objects they compute

Mathieu Hoyrup 1 Cristobal Rojas 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov computability and Type-2 computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov semidecidable sets.
Type de document :
Communication dans un congrès
STACS15, Mar 2015, Munich, Germany. 〈http://www14.in.tum.de/konferenzen/STACS2015/〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01067618
Contributeur : Mathieu Hoyrup <>
Soumis le : mardi 23 septembre 2014 - 16:51:54
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : mercredi 24 décembre 2014 - 20:58:12

Fichier

withproofs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01067618, version 1

Collections

Citation

Mathieu Hoyrup, Cristobal Rojas. On the information carried by programs about the objects they compute. STACS15, Mar 2015, Munich, Germany. 〈http://www14.in.tum.de/konferenzen/STACS2015/〉. 〈hal-01067618〉

Partager

Métriques

Consultations de la notice

389

Téléchargements de fichiers

85