On the information carried by programs about the objects they compute

Mathieu Hoyrup, Cristóbal Rojas

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferencia

2 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojada32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
EditorialSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Páginas447-459
Número de páginas13
Volumen30
ISBN (versión digital)9783939897781
DOI
EstadoPublicada - 1 feb 2015
Evento32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Alemania
Duración: 4 mar 20157 mar 2015

Otros

Otros32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
PaísAlemania
CiudadGarching
Período4/03/157/03/15

Áreas temáticas de ASJC Scopus

  • Software

Huella Profundice en los temas de investigación de 'On the information carried by programs about the objects they compute'. En conjunto forman una huella única.

  • Citar esto

    Hoyrup, M., & Rojas, C. (2015). On the information carried by programs about the objects they compute. En 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 (Vol. 30, pp. 447-459). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2015.447