A coding theorem for enumerable output machines

DOI10.1016/J.IPL.2004.05.002MaRDI QIDQ2390302zbMATH OpenOpenAlexFDO

Authors Jan Poland

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.05.002

zbMATH Keywords

theory of computationKolmogorov complexityalgorithmic information theorycoding theoremenumerable output machine

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• On the complexity of decision problems for counter machines with applications to coding theory
• Coding in the partial order of enumerable sets
• A note on a result in the theory of code construction
• Coding Theory Applied to a Problem of Ulam
• Coding on Countably Infinite Alphabets
• An application of coding theory to a problem in graphical enumeration
• Codes and automata in minimal sets
• Encodings of Turing machines in linear logic
• scientific article; zbMATH DE number 4066872
• scientific article; zbMATH DE number 5521858

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• On the relation between descriptional complexity and algorithmic probability
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(2)

• Coding with minimal programs
• Increasing the gap between descriptional complexity and algorithmic probability

This page was built for publication: A coding theorem for enumerable output machines

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