On the Algorithmic Solvability of Channel Dependent Classification Problems in Communication Systems

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

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


For communication systems there is a recent trend towards shifting functionalities from the physical layer to higher layers by enabling software-focused solutions. Having obtained a (physical layer-based) description of the communication channel, such approaches exploit this knowledge to enable various services by subsequently processing it on higher layers. For this it is a crucial task to first find out in which state the underlying communication channel is. This paper develops a framework based on Turing machines and studies whether or not it is in principle possible to algorithmically solve such classification tasks, i.e., to decide in which state the communication system is. Turing machines have no limitations on computational complexity, computing capacity and storage, and can simulate any given algorithm and therewith are a simple but very powerful model of computation. They characterize the fundamental performance limits for today's digital computers. It is shown that there exists no Turing machine that takes the physical description of the communication channel as an input and solves a non-trivial classification task. Subsequently, this general result is used to study communication under adversarial attacks and it is shown that it is impossible to algorithmically detect denial-of-service (DoS) attacks on the transmission. Jamming attacks on ACK/NACK feedback cannot be detected as well and, in addition, ACK/NACK feedback is shown to be useless for the detection of DoS on the actual message transmission. Further applications are discussed including DoS attacks on the Post Shannon task of identification, and on physical layer security and resilience by design.

Original languageEnglish (US)
Article number9374798
Pages (from-to)1155-1168
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number3
StatePublished - Jun 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Algorithmic computability
  • Turing machine
  • adversarial attacks
  • communication system
  • decision problem


Dive into the research topics of 'On the Algorithmic Solvability of Channel Dependent Classification Problems in Communication Systems'. Together they form a unique fingerprint.

Cite this