Penn Arts & Sciences Logo

Logic and Computation Seminar

Sunday, October 8, 2023 - 9:15am

V. Harizanov, J. Park, S. Shlapentokh, H. Towsner



University of Pennsylvania


This is the DDC (Definability, Decidability, Computability) Day at Penn. The speakers are: Valentina Harizanov (GWU), Jennifer Park (OSU), Alexandra Shlapentokh (ECU), Henry Towsner (UPenn).

9:15am   Henry Towsner
Title: From Saturated Embeddings to Explicit Algorithms

Abstract: The earliest quantifier elimination theorems were explicit algorithms: given an arbitrary formula in Presburger arithmetic, or the theory of algebraically closed fields, or dense linear orders, for instance, we know how to transform it into an equivalent quantifier-free formula.
Many modern quantifier elimination theorems, however, are proven through saturated embedding tests, which use the existence of certain kinds of embeddings between uncountable models to prove, indirectly, that each formula is equivalent to a quantifier-free formula. We discuss how the method of proof mining can be used to transform these proofs into explicit algorithms. Since proof mining typically deals with countable objects, we have to reinterpret the saturated embedding test itself in a more computational way before we can hope to extract an algorithm.

10:15am  Alexandra Shlapentokh:
HP10 over Number Fields and beyond

Abstract: I will give a brief survey on what is known about H10 (Hilbert's 10th Problem) over the ring of integers of number fields and describe in more detail the case of quadratic field extensions which hold a key to the solution of H10 in general.

11:00am Valentina Harizanov:
Orders on computable structures and their Turing degrees

Abstract: Orders on algebraic structures are ubiquitous in mathematics and have been studied since Dedekind. For an algebraic structure with a binary operation we consider total orderings of the elements of the domain, which are left-invariant (right-invariant, or both) with respect to the operation. Important examples of such structures include orderable groups. For an orderable structure there is a topology on the set of all orders. One of our goals is to connect algebraic, topological, and computability-theoretic properties of orders on computable structures. In some cases, spaces of orders on countable structures are homeomorphic to the Cantor set or contain a copy of the Cantor set, and these structures may or may not have orders in all Turing degrees. The question whether the space of bi-orders of a free group of finite rank greater than one is homeomorphic to the Cantor set still remains open.

12:00 (noon) Jennifer Park:
Intermediate Hilbert's Tenth Problems

Abstract: It is well-known that Hilbert's tenth problem is undecidable, by the works of Matiyasevich and Davis--Putnam--Robinson. On the other hand, a variant of Hilbert's tenth problem, where one searches for rational solutions to a polynomial instead of integer solutions, is still open (that is, we don't know whether this problem is undecidable). In this short talk, I will describe some attempts towards Hilbert's tenth problem over Q; in particular, by considering the intermediate problems that could potentially link this problem to the original Hilbert's tenth problem.