Prefix-like complexities and computability in the limit

Alexey Chernov, Juergen Schmidhuber

    Research output: Chapter in Book/Report/Conference proceedingConference contribution with ISSN or ISBN

    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.
    LanguageEnglish
    Title of host publicationSecond Conference on Computability in Europe, CiE 2006
    Place of PublicationBerlin
    Pages85-93
    Number of pages9
    Volume3988
    DOIs
    StatePublished - 31 Dec 2006
    EventSecond Conference on Computability in Europe, CiE 2006 - Swansea, UK, June 30-July 5, 2006
    Duration: 31 Dec 2006 → …

    Conference

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

    Fingerprint

    Computability
    Prefix
    Halting Problem
    Kolmogorov Complexity
    Turing Machine
    Model

    Bibliographical note

    The final publication is available at Springer via http://dx.doi.org/10.1007/11780342_9

    Keywords

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

    Cite this

    Chernov, A., & Schmidhuber, J. (2006). Prefix-like complexities and computability in the limit. In Second Conference on Computability in Europe, CiE 2006 (Vol. 3988, pp. 85-93). Berlin. DOI: 10.1007/11780342_9
    Chernov, Alexey ; Schmidhuber, Juergen. / Prefix-like complexities and computability in the limit. Second Conference on Computability in Europe, CiE 2006. Vol. 3988 Berlin, 2006. pp. 85-93
    @inproceedings{cb063dfeac2e431ba5fc4871e0933358,
    title = "Prefix-like complexities and computability in the limit",
    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.",
    keywords = "Kolmogorov complexity, limit computability, generalized Turing machine, non-halting computation",
    author = "Alexey Chernov and Juergen Schmidhuber",
    note = "The final publication is available at Springer via http://dx.doi.org/10.1007/11780342_9",
    year = "2006",
    month = "12",
    day = "31",
    doi = "10.1007/11780342_9",
    language = "English",
    volume = "3988",
    pages = "85--93",
    booktitle = "Second Conference on Computability in Europe, CiE 2006",

    }

    Chernov, A & Schmidhuber, J 2006, Prefix-like complexities and computability in the limit. in Second Conference on Computability in Europe, CiE 2006. vol. 3988, Berlin, pp. 85-93, Second Conference on Computability in Europe, CiE 2006, 31/12/06. DOI: 10.1007/11780342_9

    Prefix-like complexities and computability in the limit. / Chernov, Alexey; Schmidhuber, Juergen.

    Second Conference on Computability in Europe, CiE 2006. Vol. 3988 Berlin, 2006. p. 85-93.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution with ISSN or ISBN

    TY - GEN

    T1 - Prefix-like complexities and computability in the limit

    AU - Chernov,Alexey

    AU - Schmidhuber,Juergen

    N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/11780342_9

    PY - 2006/12/31

    Y1 - 2006/12/31

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

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

    KW - Kolmogorov complexity

    KW - limit computability

    KW - generalized Turing machine

    KW - non-halting computation

    U2 - 10.1007/11780342_9

    DO - 10.1007/11780342_9

    M3 - Conference contribution with ISSN or ISBN

    VL - 3988

    SP - 85

    EP - 93

    BT - Second Conference on Computability in Europe, CiE 2006

    CY - Berlin

    ER -

    Chernov A, Schmidhuber J. Prefix-like complexities and computability in the limit. In Second Conference on Computability in Europe, CiE 2006. Vol. 3988. Berlin. 2006. p. 85-93. Available from, DOI: 10.1007/11780342_9