LSV Seminar

Date

06.10.2020, 11:00

Place

online

Speaker

Vasco Brattka (Universitaet der Bundeswehr Muenchen)

We discuss the question whether there is a weakest unsolvable mathematical problem. In recent years the Weihrauch lattice has been established as a suitable computability theoretic framework to analyze the uniform computational content of problems from many different fields of mathematics. Here we answer a question by Schröder, whether there is a weakest discontinuous problem with respect to the continuous version of Weihrauch reducibility. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schröder's question sensitively depends on the axiomatic framework that is chosen and it is a positive answer if we work in Zermelo-Fraenkel set theory with dependent choice and the axiom of determinacy. On the other hand, using the axiom of choice, one can construct problems which are discontinuous, but not effectively so. Hence, the exact structure of the ``bottom'' of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose. We prove our result using Wadge games for mathematical problems and while the existence of a winning strategy for player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for player I characterizes effective discontinuity of the problem. We also provide further insights into the algebraic nature of the discontinuity problem. For one we show that the parallelization of the discontinuity problem is exactly the non-computability problem that was studied before. One the other hand, we introduce a new algebraic operation in the Weihrauch lattice that we call summation and which is the dual operation to parallelization. While parallelization can be seen as an analogue of the bang operator in linear logic, summation can be seen as an analogue of the question mark operator. It turns out that the discontinuity problem can be obtained as summation of a number of well-known problems in the Weihrauch lattice, such as the (lesser) limited problem of omniscience and variants thereof. More generally, we study the action of the monoid formed by parallelization and summation on the Weihrauch lattice, and we prove that this action can lead to at most five different Weihrauch degrees, which (in the maximal case) are always organized in a pentagon. We show that the discontinuity problem appears as the bottom of several natural such pentagons. This leads to further interesting characterizations of the discontinuity problem.