A famous result by Alan Turing dating back to 1936 is that a general algorithm solving the halting problem on a Turing machine for all possible inputs and programs cannot exist - the halting problem is undecidable. Formally, an undecidable problem is a decision problem for which one cannot construct a single algorithm that will always provide a correct answer in finite time. In the talk, I show that the problem to determine whether sequentially used identical measurement devices have outcomes that never occur is undecidable. This is already true for Stern-Gerlach-type measurement devices with 9 outcomes. This result shows that even very natural, apparently simple problems in quantum measurement theory can be provably undecidable. In contrast, the corresponding classical problem is decidable, by a reduction to a finite binary semi-group problem.
(Joint work with Jens Eisert, Christian Gogolin, and Martin Kliesch.)