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_\infty$ function and the zero-error feedback capacity, both of them play an important role for the reliability function. Both the $R_\infty$ function and the zero-error feedback capacity are not Banach Mazur computable. We show that the $R_\infty$ function is additive. The zero-error feedback capacity is super-additive and we characterize it's behavior.
翻译：频道的可靠性功能是一个重要的工具,它代表了在通信频道上可靠传输信息的特点。对于许多频道来说,只有该功能的上下界才为人所知。在本文中,我们分析了可靠性功能及其相关功能的可计算性。我们显示,可靠性功能不是图灵可计算性功能。同样也适用于域包装和排污约束的功能。此外,我们认为$R ⁇ infty$函数和零error反馈能力,两者对于可靠性功能都起着重要作用。$R ⁇ infty$函数和零error反馈能力都不是Banach Mazur可计算性功能。我们显示,$R ⁇ infty$函数是添加性的。0eror反馈能力是超级添加的,我们描述它的行为。
相关内容
微信扫码咨询专知VIP会员