Prefix-like complexities and computability in the limit

Alexey Chernov, Jürgen Schmidhuber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. © Springer-Verleg Berlin Heidelberg 2006.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages85-93
Number of pages9
ISBN (Print)3540354662
DOIs
StatePublished - Jan 1 2006
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2022-09-14

Fingerprint

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

Cite this