A coding theorem for enumerable output machines

DOI10.1016/J.IPL.2004.05.002zbMATH Open1178.68247OpenAlexW2035692138MaRDI QIDQ2390302FDOQ2390302

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

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 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)

Cites Work

• Title not available (Why is that?)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• On the relation between descriptional complexity and algorithmic probability
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT

Cited In (1)

• 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)