Universal codes of the natural numbers
From MaRDI portal
Publication:2846579
DOI10.2168/LMCS-9(3:7)2013zbMATH Open1284.03233arXiv1308.1600OpenAlexW3102830890MaRDI QIDQ2846579
Publication date: 6 September 2013
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Abstract: A code of the natural numbers is a uniquely-decodable binary code of the natural numbers with non-decreasing codeword lengths, which satisfies Kraft's inequality tightly. We define a natural partial order on the set of codes, and show how to construct effectively a code better than a given sequence of codes, in a certain precise sense. As an application, we prove that the existence of a scale of codes (a well-ordered set of codes which contains a code better than any given code) is independent of ZFC.
Full work available at URL: https://arxiv.org/abs/1308.1600
Other types of codes (94B60) Consistency and independence results (03E35) Applications of set theory (03E75) Arithmetic codes (94B40)
Related Items (3)
Meta-Fibonacci Codes:Efficient Universal Coding of Natural Numbers ⋮ Unnamed Item ⋮ A new recursive universal code of the positive integers
Uses Software
This page was built for publication: Universal codes of the natural numbers
