The Computability of the Channel Reliability Function and Related Bounds

The channel reliability function is a crucial tool for characterizing the dependable transmission of messages across communication channels. In many cases, the only upper and lower bounds of this function are known. We investigate the computability of the reliability function and its associated functions, demonstrating that the reliability function is not Turing computable. This also holds true for functions related to the sphere packing bound and the expurgation bound. Additionally, we examine the R∞ function and zero-error feedback capacity, as they are vital in the context of the reliability function. Both the R∞ function and the zero-error feedback capacity are not Banach–Mazur computable.