Kolmogorov complexity for possibly infinite computations

DOI10.1007/s10849-005-2255-6zbMath1075.68034OpenAlexW2151438660WikidataQ61927037 ScholiaQ61927037MaRDI QIDQ1777368

Santiago Figueira, Verónica Becher

Publication date: 13 May 2005

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: http://sedici.unlp.edu.ar/handle/10915/22767

zbMATH Keywords

Turing machinesKolmogorov complexityinfinite computationsprogram-size complexitymonotone machinesnon-effective computations

Mathematics Subject Classification ID

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

Related Items (1)

Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets
• Several results in program size complexity
• Information-theoretic characterizations of recursive infinite strings
• Algorithmic entropy of sets
• On degrees of unsolvability
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity

This page was built for publication: Kolmogorov complexity for possibly infinite computations