On November 24, 2022 at 14:00 EET, Eugenio Omodeo (DMG, Università degli studi di Trieste) will give an online talk in the Logic Seminar.
Title: Julia Robinson, existential definability, and Hilbert’s 10th problem
Abstract: Julia Bowman Robinson put forward in 1952 her notions of existential definability and exponential growth, both regarding relations on natural numbers. She foresaw that one of the new century problems posed by David Hilbert in the year 1900 would be settled by singling out an exponential-growth, existentially definable relation. The problem in question called for an algorithm that would establish, for any given polynomial P with integer coefficients, whether the equation P = 0 has integer solutions or not.
Julia Robinson’s outlook had a decisive influence in the research that led, almost twenty years later, to a proof of the algorithmic unsolvability of Hilbert’s 10th problem. She had designed from the outset a scheme for getting a specification of exponentiation in polynomial terms, out of any alike specification of an exponential-growth relation. In a 1969 paper, she would propose an improved version of her reduction scheme, of which a possible further refinement shines through a 1975 paper that she wrote in collaboration with Yuri V. Matiyasevich.
By retracing the stages of Julia Robinson’s contribution to the existential definition of exponentiation, this seminar does not simply intend to pay homage to an outstanding scientist. From an in-depth revisitation of her studies on Hilbert’s 10th, along with the contributions of Martin Davis and Yuri Matiyasevich, a novel characterization of a key concept in computability might emerge: that of a listable set.
The talk will be online; people are welcome to join us physically at FMI Hall 214 “Google”.
Google Meet link: https://meet.google.com/xwm-syvx-bbr