October 2, 2026
11 a.m. CET
Seminar room - 3rd floor
Abstract In the theory of computability, a ‘problem’ is an infinite class of input questions to a computer (modeled as a Turing machine) for which one seeks a single algorithm that (after finite time) gives the correct answer to any of the questions. For example, the ‘is-prime-problem’ consists of the set of integers and the question for each one to compute if it is a prime. Such an algorithm exists and we call that problem decidable.
In mathematics there are also many undecidable problems. A prominent one is Hilbert’s 10th problem. No computer program can take as input any diophantine equation and correctly output if it has an integer solution. Other problems involve tilings of the plane, group theory or winning strategies for games.
In this talk we survey some undecidable problems in mathematics, and in the end discuss one that the speaker has recently added to this list: Whether a polynomial ideal contains a polynomial with at most 3 terms is undecidable.
Based on joint work with Tobias Boege and Anna Hofer.