Reading group on Topics in Undecidability

The reading group will take place biweekly, alternately between SYMCREA, the UB and the Pompeu Fabra.

Interested? Please write to eva.miranda@upc.edu to register.

Starting day: Thursday October 1st. 

Timing: 12_13:30 Session 1 

               13:30-15:30 lunch 

               15:30-17h second session

Place: Itinerant SYMCREA-UPC, Pompeu Fabra and Facultat de Matemàtiques i Informàtica de la UB.

Organizers:  Carles Casacuberta, Gemma de les Coves and Eva Miranda

Topics in Undecidability

This reading group explores the theoretical foundations and far-reaching consequences of undecidability in mathematics, logic, computer science, and physics. Starting from the classical results of Gödel, Turing, and Church, we will examine the inherent limits of formal systems and algorithmic computation: questions that cannot be answered, problems that cannot be solved, and truths that cannot be proved.

The sessions will cover a selection of foundational texts and research articles, tracing the development of the field from Hilbert’s programme and its collapse to modern undecidability results in algebra, topology, combinatorics, dynamical systems, and theoretical physics. Topics include undecidability in quantum mechanics, the spectral gap problem, fluid trajectories and billiards, and the relationship between physical processes and computation.

We will also explore the categorical perspective on incompleteness and self-reference through Lawvere’s fixed-point theorem, which provides a unifying framework encompassing Gödel’s incompleteness theorem, Cantor’s diagonal argument, and Turing’s halting problem as manifestations of a common categorical phenomenon. Particular attention will be given to the interplay between logic and other areas of mathematics and physics, as well as to the philosophical implications of incompleteness and uncomputability.

The group is open to graduate students and researchers with a background in mathematics, theoretical computer science, or physics. No specific prerequisites beyond mathematical maturity are assumed. Participants will be encouraged to present papers and contribute actively to discussions.

Session 1: October 1, 12pm at room 3.2 adjacent to SYMCREA at the third floor of EPSEB-UPC.

Morning session: The Machine That Cannot Know If It Will Stop
Giovanni Mocellin (UPC)
Thursday 1 October, 12:00, Room 3.2 (third floor of EPSEB-UPC, next to SYMCREA)

We start with Turing's halting problem: no program can decide, for every program and input, whether that program will eventually halt. We'll go through the diagonal proof and see why this is the prototypical example of uncomputability on which many other undecidability results are built.

Afternoon session: One Theorem to Rule Them All: Lawvere's Fixed Point Theorem
Alexander Pappas (UPF)
Thursday 1 October, 15:30, Room 3.2 (third floor of EPSEB-UPC, next to SYMCREA)

Cantor's diagonal argument, Russell's paradox, Gödel's incompleteness theorems and the halting problem all turn out to be instances of a single categorical statement. Lawvere's fixed point theorem provides one short argument behind all of them, tying directly back to the morning session.

No background in logic or category theory is needed. Just bring curiosity.

Session 2: October 15, 12pm at Edifici Tànger of the UPF (Carrer Tànger 122, Barcelona) 

Alexander Pappas (UPF)

CPM(FHilb), the category to model quantum mechanics.  

What does quantum mechanics look like when formulated in the language of category theory? What if, instead of focusing on states, we take processes and their composition as fundamental? We will explore this perspective through the category CPM(FHilb) and see what might be gained.