Abstract
Computability in the limit represents the non-plus-ultra of constructive describability. It is well known that the limit computable functions on naturals are exactly those computable with the oracle for the halting problem. However, prefix (Kolmogorov) complexities defined with respect to these two models may differ. We introduce and compare several natural variations of prefix complexity definitions based on generalized Turing machines embodying the idea of limit computability, as well as complexities based on oracle machines, for both finite and infinite sequences.
Original language | English |
---|---|
Title of host publication | Second Conference on Computability in Europe, CiE 2006 |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 85-93 |
Number of pages | 9 |
Volume | 3988 |
DOIs | |
Publication status | Published - 31 Dec 2006 |
Event | Second Conference on Computability in Europe, CiE 2006 - Swansea, UK, June 30-July 5, 2006 Duration: 31 Dec 2006 → … |
Conference
Conference | Second Conference on Computability in Europe, CiE 2006 |
---|---|
Period | 31/12/06 → … |
Bibliographical note
The final publication is available at Springer via http://dx.doi.org/10.1007/11780342_9Keywords
- Kolmogorov complexity
- limit computability
- generalized Turing machine
- non-halting computation