On the information carried by programs about the objects they compute

Mathieu Hoyrup, Cristóbal Rojas

Resultado de la investigación: Conference contribution

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 originalEnglish
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
EstadoPublished - 1 feb 2015
Evento32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Germany
Duración: 4 mar 20157 mar 2015

Other

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

Huella dactilar

Tapes

ASJC Scopus subject areas

  • Software

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
Hoyrup, Mathieu ; Rojas, Cristóbal. / On the information carried by programs about the objects they compute. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. Vol. 30 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. pp. 447-459
@inproceedings{391317e350d54e6ca29f69e450aa4fbf,
title = "On the information carried by programs about the objects they compute",
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.",
keywords = "Ershov topology, Kolmogorov complexity, Markov-computable, Representation",
author = "Mathieu Hoyrup and Crist{\'o}bal Rojas",
year = "2015",
month = "2",
day = "1",
doi = "10.4230/LIPIcs.STACS.2015.447",
language = "English",
volume = "30",
pages = "447--459",
booktitle = "32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

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, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 447-459, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, Garching, Germany, 4/03/15. https://doi.org/10.4230/LIPIcs.STACS.2015.447

On the information carried by programs about the objects they compute. / Hoyrup, Mathieu; Rojas, Cristóbal.

32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. Vol. 30 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 447-459.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - On the information carried by programs about the objects they compute

AU - Hoyrup, Mathieu

AU - Rojas, Cristóbal

PY - 2015/2/1

Y1 - 2015/2/1

N2 - 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.

AB - 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.

KW - Ershov topology

KW - Kolmogorov complexity

KW - Markov-computable

KW - Representation

UR - http://www.scopus.com/inward/record.url?scp=84923918084&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2015.447

DO - 10.4230/LIPIcs.STACS.2015.447

M3 - Conference contribution

AN - SCOPUS:84923918084

VL - 30

SP - 447

EP - 459

BT - 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

Hoyrup M, Rojas C. 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. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2015. p. 447-459 https://doi.org/10.4230/LIPIcs.STACS.2015.447