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}$, a target rate $R$ less than the channel capacity $C(p_{Y|X})$, and an error tolerance $\epsilon > 0$, outputs a block code $\mathcal{C}$ achieving a rate at least $R$ and a maximum block error probability below $\epsilon$. The machine operates in the general case where all transition probabilities of $p_{Y|X}$ are computable real numbers, and the parameters $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 $\mathrm{FindCode} : \mathbb{N}^3 \rightharpoonup \mathbb{N}$ that takes as input appropriate encodings of $p_{Y|X}$, $R$, and $\epsilon$, and, whenever $R < C(p_{Y|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$ is computable as well. We note that the assumptions that the probabilities of $p_{Y|X}$, as well as $\epsilon$ and $R$, are computable real numbers cannot be further weakened, since computable reals constitute the largest subset of $\mathbb{R}$ representable by algorithmic means.

翻译：本文从算法视角研究构造容量可达码的问题。具体而言，我们证明存在一个图灵机，给定离散无记忆信道 $p_{Y|X}$、小于信道容量 $C(p_{Y|X})$ 的目标速率 $R$ 以及误差容限 $\epsilon > 0$，该图灵机能够输出一个分组码 $\mathcal{C}$，其速率至少为 $R$ 且最大分组错误概率低于 $\epsilon$。该机器在 $p_{Y|X}$ 的所有转移概率均为可计算实数、且参数 $R$ 与 $\epsilon$ 为有理数的一般情形下运行。证明基于香农信道编码定理，并依赖于一种穷举搜索方法：系统性地枚举所有递增分组长度的码，直至找到有效码。该构造通过递归函数理论形式化，得到一个 $\mu$-递归函数 $\mathrm{FindCode} : \mathbb{N}^3 \rightharpoonup \mathbb{N}$，该函数以 $p_{Y|X}$、$R$ 和 $\epsilon$ 的适当编码作为输入，并在 $R < C(p_{Y|X})$ 时输出有效码的编码。根据克林范式定理（该定理确立了图灵机与 $\mu$-递归函数之间的计算等价性），我们得出结论：该问题可由图灵机求解。此结果可推广至 $\epsilon$ 为可计算实数的情形，同时我们进一步讨论了当 $R$ 也为可计算实数时分析的类似推广。我们指出，$p_{Y|X}$ 的概率以及 $\epsilon$ 和 $R$ 为可计算实数的假设无法进一步弱化，因为可计算实数是 $\mathbb{R}$ 中可通过算法表示的最大子集。