Modeling time-bounded prefix Kolmogorov complexity

DOI10.1007/S002249910008MaRDI QIDQ1974444zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz, David W. Juedes

Publication date 7 May 2000

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002249910008

zbMATH Keywords

prefix Kolmogorov complexityself-delimiting Turing machines

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1304330
• scientific article; zbMATH DE number 107775
• Logical Approaches to Computational Barriers
• Time-bounded Kolmogorov complexity and Solovay functions

Cited in

(3)

• scientific article; zbMATH DE number 1304330 (Why is no real title available?)
• A model of \(\widehat{R}^2_3\) inside a subexponential time resource
• Not every domain of a plain decompressor contains the domain of a prefix-free one

This page was built for publication: Modeling time-bounded prefix Kolmogorov complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974444)