Identification Capacity of Channels with Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability

Abstract

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. This is the first time that super-activation is observed for discrete memoryless channels. On the other hand, for the randomized IDF capacity, super-activation is not possible. Finally, the developed theory is studied from an algorithmic point of view by using the framework of Turing computability. The problem of computing the IDF capacity on a Turing machine is connected to problems in pure mathematics and it is shown that if the IDF capacity would be Turing computable, it would provide solutions to other problems in mathematics including Goldbach's conjecture and the Riemann Hypothesis. However, it is shown that the deterministic and randomized IDF capacities are not Banach-Mazur computable. This is the weakest form of computability implying that the IDF capacity is not computable even for universal Turing machines. On the other hand, the identification capacity without feedback is Turing computable revealing the impact of the feedback: It transforms the identification capacity from being computable to non-computable.