  This note is intended to foster a discussion about the extent to which
typical problems arising in quantum information theory are algorithmically
decidable (in principle rather than in practice). Various problems in the
context of entanglement theory and quantum channels turn out to be decidable
via quantifier elimination as long as they admit a compact formulation without
quantification over integers. For many asymptotically defined properties which
have to hold for all or for one integer N, however, effective procedures seem
to be difficult if not impossible to find. We review some of the main tools for
(dis)proving decidability and apply them to problems in quantum information
theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a
two-qubit singlet state?" easily become undecidable. A closer look at such
questions might rule out some of the "single-letter" formulas sought in quantum
information theory.
