Prefix-like complexities and computability in the limit

Alexey Chernov, Juergen Schmidhuber

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNpeer-review


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 languageEnglish
Title of host publicationSecond Conference on Computability in Europe, CiE 2006
Place of PublicationBerlin
Number of pages9
Publication statusPublished - 31 Dec 2006
EventSecond Conference on Computability in Europe, CiE 2006 - Swansea, UK, June 30-July 5, 2006
Duration: 31 Dec 2006 → …


ConferenceSecond Conference on Computability in Europe, CiE 2006
Period31/12/06 → …

Bibliographical note

The final publication is available at Springer via


  • Kolmogorov complexity
  • limit computability
  • generalized Turing machine
  • non-halting computation


Dive into the research topics of 'Prefix-like complexities and computability in the limit'. Together they form a unique fingerprint.

Cite this