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 ISBNResearchpeer-review

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 languageEnglish
Title of host publicationSecond Conference on Computability in Europe, CiE 2006
Place of PublicationBerlin
Pages85-93
Number of pages9
Volume3988
DOIs
Publication statusPublished - 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. https://doi.org/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. https://doi.org/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/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNResearchpeer-review

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 https://doi.org/10.1007/11780342_9