On the Computability of Finding Capacity-Achieving Codes

Angelos Gkekas, Nikos A. Mitsiou · 2025

Read On the Computability of Finding Capacity-Achieving Codes by Angelos Gkekas, Nikos A. Mitsiou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01414.txt.

Introduction

Angelos Gkekas, Nikos Mitsiou, Ioannis Souldatos, and George Karagiannidis ask a question at the border of information theory and computability. Can a program actually find the best possible error-correcting codes for a noisy channel? Or does theory only promise that such codes exist?

Their answer is that a Turing machine can do it. Given a channel, a target rate below capacity, and an error tolerance, the machine searches through codes of growing block length until one meets the targets. The construction leans on Shannon's channel coding theorem and is written formally as a recursive function. The authors also argue that their assumptions about computable numbers cannot be weakened any further.

Catalog record

CREATORAngelos Gkekas, Nikos A. Mitsiou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01414

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Computability of Finding Capacity-Achieving Codes Thanks: Angelos Gkekas, Nikos A. Mitsiou, and George K. Karagiannidis are with the Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece (e-mails: [email protected], [email protected], [email protected]). Thanks: Ioannis Souldatos is with the Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece (e-mail: [email protected]). Angelos Gkekas, Nikos A. Mitsiou Abstract This work studies the problem of constructing capacity-achieving codes from an algorithmic perspective. Specifically, we prove that there exists a Turing machine which, given a discrete memoryless channel p Y | X p_{Y\mid X} , a target rate R R less than the channel capacity C ⁡ ( p Y | X ) C(p_{Y\mid X}) , and an error tolerance ϵ > 0 \epsilon>0 , outputs a block code 𝒞 \mathcal{C} achieving a rate at least R R and a maximum block error probability below ϵ \epsilon . The machine operates in the general case where all transition probabilities of p Y | X p_{Y\mid X} are computable real numbers, and the parameters R R and ϵ \epsilon are rational. The proof builds on Shannon’s channel coding theorem and relies on an exhaustive search approach that systematically enumerates all codes of increasing block length until a valid code is found. This construction is formalized using the theory of recursive functions, yielding a μ \mu -recursive function FindCode : ℕ 3 ⇀ ℕ \FindCode:\mathbb{N}^{3}\rightharpoonup\mathbb{N} that takes as input appropriate encodings of p Y | X p_{Y\mid X} , R R , and ϵ \epsilon , and, whenever R < C ⁡ ( p Y | X ) R<C(p_{Y\mid X}) , outputs an encoding of a valid code. By Kleene’s normal form theorem, which establishes the computational equivalence between Turing machines and μ \mu -recursive functions, we conclude that the problem is solvable by a Turing machine. This result can also be extended to the case where ϵ \epsilon is a computable real number, while we further discuss an analogous generalization of our analysis when R R is computable as well. We note that the assumptions that the probabilities of p Y | X p_{Y\mid X} , as well as ϵ \epsilon and R R are computable real numbers cannot be further weakened, since computable reals constitute the largest subset of ℝ \mathbb{R} representable by algorithmic means. I Introduction Capacity-achieving codes constitute a cornerstone of modern communication theory. They enable reliable information transmission over noisy environments by ensuring that the probability of decoding error can be made arbitrarily small, while incurring only a bounded increase in codeword length. Specifically, for any discrete memoryless channel (DMC) without feedback, characterized by the conditional distribution p_{Y\mid X} , there exists a fundamental limit C(p_{Y\mid X}) , referred to as the channel capacity. Shannon’s channel coding theorem establishes that for any desired error tolerance \epsilon>0 and any coding rate R\in(0,C) , there exists a coding scheme \mathcal{C} that simultaneously achieves error probability smaller than \epsilon and rate at least R . This seminal result, first established in Shannon’s groundbreaking work [ 1 ] , laid the foundation for the entire field of modern digital communications. However, Shannon’s original proof did not provide a formal approach for designing such codes. Since then, a variety of explicit code constructions that approach or achieve capacity have been developed. Among the most widely studied are low-density parity-check (LDPC) codes [ 2 ] , Reed–Solomon codes [ 3 ] , turbo codes [ 4 ] , and polar codes [ 5 ] . These codes have been extensively analyzed and successfully implemented in practical communication systems and standards, where they have demonstrated exceptional performance, underscoring the lasting importance of Shannon’s original result. Nonetheless, each of these constructions is typically tailored to specific families of channel models. Naturally, this raises the question of whether constructing capacity-achieving codes for arbitrary DMCs is feasible from a computability perspective. Among the most well-known tools for studying computability are Turing machines and \mu -recursive functions. Turing machines, introduced by Turing in his seminal work [ 6 ] , constitute the earliest and most widely used formal model of computation, and are regarded as the foundation of theoretical computer science. The class of \mu -recursive functions provides an alternative model, defined as a collection of partial functions from tuples over \mathbb{N} to \mathbb{N} . A notable subclass is that of the primitive recursive functions, first introduced in Gödel’s proof of the incompleteness theorems [ 7 ] . Their first complete formulation was later developed in Kleene’s studies on recursion theory [ 8 ] . For a comprehensive exposition of \mu -recursive functions, see [ 9 , 10 , 11 , 12 ] . These two models of computation are equivalent, in the sense that any computational task performed in one model can be simulated in the other. This equivalence is established by Kleene’s normal form theorem [ 9 ] , which allows us to freely adopt either model in our analysis. I-A Literature Review There are only a handful of relevant contributions that examine the computability of constructing channel codes for DMCs. First, in [ 13 ] , the computability of the zero-error capacity for DMCs was studied using Turing machines and Kolmogorov oracles and it was proved that the zero-error capacity function is semi-computable in this setting, while [ 14 ] employed a probabilistic channel coding construction to obtain capacity-achieving linear codes for a broad class of channels. However, the most fundamental work on the computability of constructing channel codes is [ 15 ] . In [ 15 ] , the following question was addressed Question 1 . For a given computable family of channels \mathcal{W} and an error tolerance \epsilon\in(0,1)\cap\mathbb{Q} , does there exist a Turing machine M_{\mathcal{W},\epsilon} such that, for every DMC p_{Y\mid X}\in\mathcal{W} and every blocklength n , the machine outputs a block code \mathcal{C}_{n} of length n , whose maximum block error probability \lambda_{n} and rate R_{n} satisfy \lambda_{n}\to 0 and R_{n}\to C(p_{Y\mid X}) as n\to\infty ? A negative answer to this question was provided using tools from the theory of Turing machines, recursive functions and computable real analysis. Moreover, this result also implies that that such an algorithmic construction remains impossible even when the optimality condition is dropped and codes only need to achieve a fraction of the capacity. I-B Motivation and Contribution The negative answer to the problem formulation stated in [ 15 ] motivates the exploration of weaker assumptions for the formulation of the problem of constructing capacity-achieving codes, under which the problem is computable. Ideally, one is interested in finding the least weak assumptions for which this problem remains computable. As a first step in this direction, Question 2 arises Question 2 . Does there exist a Turing machine M such that, when given as input a DMC p_{Y\mid X} , a rate R<C(p_{Y\mid X}) and an error tolerance \epsilon>0 , it outputs a block code \mathcal{C} with rate at least R and with maximum block error probability \lambda_{\max}<\epsilon ? We prove that the answer to this question is positive. Specifically, we show that the above problem is solvable by a Turing machine in the general setting where all parameters of the channel p_{Y\mid X} are arbitrary

Read the complete text