Atlas home || Conferences | Abstracts | about Atlas
Host: University of Colorado
Sponsor: American Mathematical Society, National Science Foundation
Homepage: http://www.ams.org/meetings/src-cholak.html
Email: wsd@ams.org
Organizers: Peter Cholak (University of Notre Dame), Steffen Lempp (University of Wisconsin) (co-chair), Manuel Lerman (University of Connecticut) (co-chair), Richard Shore (Cornell University) (co-chair)
Deadline for abstracts: March 03, 1999
Description:
Computability theory (or recursion theory) is an area of mathematical logic dealing with
the theoretical bounds on and structure of computability and with the interplay between
computability and definability in mathematical languages and structures. The field started
in the 1930s with ground-breaking work of Gödel and Turing and has developed into a
rich theory with applications and connections to areas ranging from computer science to
descriptive set theory as well as more traditional branches of mathematics, including
algebra, analysis, and combinatorics. The meeting will focus on classical computability
theory, an area in which many recent advances have been made, and those applications
which currently seem most directly connected to and most likely to benefit from these
advances. In particular, applications in algebra, model theory, and proof theory will be
highlighted. Lectures will stress open problems, their relationship to some of the recent
advances, and further obstacles which need to be overcome to solve the problems.
Problems, primarily from the following areas, will be discussed.
1. Classical computability theory. There have been a number of major advances in the understanding of substructures of the Turing degrees in the past few years, including a phenomenal number of solutions to diverse problems that had been open for decades and had always been considered very hard. In addition, substantial progress has been made towards the solution of other problems. Results have been obtained about automorphisms of these structures, characterizing definable sets and relations, and decidability and undecidability of fragments of elementary theories of the structures. These results will be discussed with an eye towards the limitations of the methods and the obstacles which need to be overcome in order to solve other problems of a similar nature.
2. Computable mathematics. The area of applied computability theory on which we propose to concentrate is computable mathematics. Generally speaking, one wishes to investigate the effective content of mathematical constructions and theorems, that is, to determine which procedures or relations are computable and the relative complexity of those that are not. The problems which we will address deal with determining properties of computable structures which can be decided effectively from their presentations and, if not, on the possible limits on their complexity.
Reverse mathematics is a proof-theoretic and foundational investigation into the axiom systems needed to prove standard theorems of classical mathematics, but many of its arguments and results can also be viewed as belonging to computable mathematics. There is an almost perfect translation between the proof-theoretic systems used and the levels of complexity in computability. Each approach contributes its own techniques, which often produce results with overlapping but supplementary content. An important foundational issue is the existence of classical theorems not equivalent to any of the standard systems. It seems likely that further computability theory analyses using more delicate techniques can shed light on this area.
Speakers: Sergey Goncharov (Novosibirsk), Julia Knight (Notre Dame), Serikzhan Badaev (Almaty), Rod Downey (Wellington), Bakh Khoussainov (Auckland), Mikhail Peretyat'kin (Almaty), Sasha Shlapentokh (E. Carolina), Peter Cholak (Notre Dame), Bob Soare (Chicago), Klaus Ambos-Spies (Heidelberg), Barry Cooper (Leeds), André Nies (Chicago), Richard Shore (Cornell), Gerald Sacks (Harvard & MIT), Harvey Friedman (Ohio State), Carl Jockusch (Urbana), Chi Tat Chong (Singapore), Steve Simpson (Penn State), Jeff Remmel (San Diego), Yiannis Moschovakis (UCLA & Athens), Anil Nerode (Cornell), Ted Slaman (Berkeley), Alekos Kechris (Cal Tech), Marcia Groszek (Dartmouth), Manny Lerman (Connecticut), Marat Arslanov (Kazan)
Mail Address:
Summer Research Conferences Coordinator American Mathematical Society P.O. Box 6887 Providence, RI 02940
Date received: February 17, 1999
© 2008 Atlas Conferences Inc.