Yuval Filmus - Universal codes of the natural numbers

lmcs:975 - Logical Methods in Computer Science, August 29, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:7)2013
Universal codes of the natural numbersArticle

Authors: Yuval Filmus

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.

Comment: 11 pages

https://doi.org/10.2168/LMCS-9(3:7)2013
Source: arXiv.org:1308.1600
Volume: Volume 9, Issue 3
Published on: August 29, 2013
Imported on: October 16, 2012
Keywords: Computer Science - Logic in Computer Science, Computer Science - Information Theory
Licence: arXiv.org - Non-exclusive license to distribute

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 3104 times.
This article's PDF has been downloaded 1270 times.