nach oben

Theory of Computing Systems

Erschienen in:

08.05.2017

Short lists with short programs from programs of functions and strings

verfasst von: Nikolay Vereshchagin

Erschienen in: Theory of Computing Systems | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Let {φ _p} be an optimal Gödel numbering of the family of computable functions (in Schnorr’s sense), where p ranges over binary strings. Assume that a list of strings L(p) is computable from p and for all p contains a φ-program for φ _p whose length is at most ε bits larger than the length of the shortest φ-programs for φ _p. We show that for infinitely many p the list L(p) must have 2^{|p|−ε−O(1)} strings. Here ε is an arbitrary function of p.

Vorheriger Artikel On the Complexity of Automatic Complexity

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The term “optimal Gödel numbering” was introduced by Schnorr [4]. Teutsch and Zimand [2] call optimal Gödel numberings Kolmogorov numberings. However Kolmogorov has neither introduced nor studied them.

Bauwens, B., Makhlin, A., Vereshchagin, N., Zimand, M.: Short lists with short programs in short time. In: Proceedings 28th IEEE Conference on Computational Complexity (CCC). ECCC report TR13-007, pp. 98–108. Stanford, CA (2013)

Teutsch, J., Zimand, M.: On approximate decidability of minimal programs. Available from arXiv:1409.0496 and http://people.cs.uchicago.edu/~teutsch/papers/teutschpubs.html (2014)

Rogers, H. Jr.: The Theory of Recursive Functions and Effective Computability. MIT Press (1987)

Schnorr, C. P.: Optimal enumerations and optimal Gödel numberings. Mathematical Systems Theory 8(2), 182–191 (1975)CrossRefMATH

Shen, A.: A talk on some open problems in Kolmogorov complexity. The talk was delivered on a meeting during the IMS program “Algorithmic Randomness” (IMS, University of Singapore, 2–30 June 2014) around June 20, 2014

Titel: Short lists with short programs from programs of functions and strings
verfasst von: Nikolay Vereshchagin
Publikationsdatum: 08.05.2017
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9773-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2017

New Pairwise Spanners

Exact Constructive and Computable Dimensions

Optimal Decremental Connectivity in Planar Graphs

Towards an Isomorphism Dichotomy for Hereditary Graph Classes

A Generalized Characterization of Algorithmic Probability

Semiautomatic Structures

Premium Partner