Abstract:

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.)