Computability of the Channel Reliability Function and Related Bounds
share
The channel reliability function is an important tool that characterizes the reliable transmission of messages over communications channels. For many channels only the upper and lower bounds of the function are known. In this paper we analyze the computability of the reliability function and its related functions. We show that the reliability function is not a Turing computable performance function. The same also applies to the functions of the sphere packing bound and the expurgation bound. Furthermore, we consider the R_∞ function and the zero-error feedback capacity, both of them play an important role for the reliability function. Both the R_∞ function and the zero-error feedback capacity are not Banach Mazur computable. We show that the R_∞ function is additive. The zero-error feedback capacity is super-additive and we characterize it's behavior.
READ FULL TEXT