A computability challenge: asymptotic bounds for error-correcting codes

DOI10.1007/978-3-642-27654-5_13MaRDI QIDQ2891310zbMATH OpenOpenAlexFDO

Authors Yuri I. Manin

Publication date 15 June 2012

Published in Computation, Physics and Beyond (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.4246, http://edoc.mpg.de/634929

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Linear codes (general theory) (94B05) Bounds on codes (94B65) Constructive and recursive analysis (03F60)

Abstract: Consider the set of all error--correcting block codes over a fixed alphabet with $q$ letters. It determines a recursively enumerable set of points in the unit square with coordinates $(R,delta)$:= {it (relative transmission rate, relative minimal distance).} Limit points of this set form a closed subset, defined by $Rlealph{a}_q(delta)$, where $alph{a}_q(delta)$ is a continuous decreasing function called {it asymptotic bound.} Its existence was proved by the author in 1981, but all attempts to find an explicit formula for it so far failed. In this note I consider the question whether this function is computable in the sense of constructive mathematics, and discuss some arguments suggesting that the answer might be negative.

Recommendations

• Kolmogorov complexity and the asymptotic bound for error-correcting codes
• Asymptotic bounds for spherical codes
• Algebraic-geometric codes and asymptotic problems
• Notes on the asymptotic behavior of the information rate of block codes (Corresp.)
• On improved asymptotic bounds for codes from global function fields

Cites work

• scientific article; zbMATH DE number 3836211 (Why is no real title available?)
• scientific article; zbMATH DE number 3110188 (Why is no real title available?)
• Algebraic geometric codes. Basic notions
• Computability of Julia sets
• Computability on subsets of Euclidean space. I: Closed and compact subsets
• Computability on subsets of metric spaces.
• Computing over the reals: foundations for scientific computing.
• Error-correcting codes and phase transitions
• Holomorphic supergeometry and Yang-Mills superfields
• Plottable Real Number Functions and the Computable Graph Theorem
• Random codes: minimum distances and error exponents
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Renormalisation and computation. II: Time cut-off and the halting problem
• Renormalization and computation. I: Motivation and background

Cited in

(7)

• Error-correcting codes and neural networks
• The complexity of error-correcting codes
• Syntactic structures and code parameters
• Codes as fractals and noncommutative spaces
• Differential subordination and convexity criteria of integral operators
• Asymptotic bounds for spherical codes
• Kolmogorov complexity and the asymptotic bound for error-correcting codes

This page was built for publication: A computability challenge: asymptotic bounds for error-correcting codes

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