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

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number9127469
Pages (from-to)6184-6199
Number of pages16
JournalIEEE Transactions on Information Theory
Volume66
Issue number10
DOIs
StatePublished - Oct 2020

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • discontinuity
  • feedback
  • Identification capacity
  • super-activation
  • super-additivity

Fingerprint Dive into the research topics of 'Identification Capacity of Channels with Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability'. Together they form a unique fingerprint.

Cite this