A sunny summer day in July, 1997.
A walk through the woods outside Kazan,
Along the Volga river.
Ideas for a conference emerge.
Focus only on open problems.
Provide sufficient background for
Fruitful discussions about the problems.
Allow enough free time to
Immerse ourselves in the problems.
Assemble a mix of people with diverse, but con_nected interests.
Provide new ideas and insights.
A consensus emerges.
A list of focus areas is proposed, discussed, modified.
Potential speakers are matched with topics.
A successful proposal to the AMS.
A conference of a different nature sees the light of day.
This volume is a faithful and expanded reflection of most of the talks which
were presented at the Conference on Computability Theory and Applications, as
part of the Joint Summer Research Conferences in the Mathematical Sciences,
Boulder, Colorado, June 13-17, 1999. The meeting focused on open problems in
Computability Theory and some related areas in which the ideas, methods and/ or
results of Computability Theory play a role. Some talks delved in depth into a
narrowly focused group of problems, providing a description of what had been done
and delineating the obstacles to solution. Others covered a wider area, providing
the rationale for interest in the area and the directions pursued, and a broad cross-
section of central open problems. Discussions ensued. Some problems were solved
quickly at the meeting, and others since that time. The result is, we hope, a
snapshot of the status of Computability Theory at the end of the millennium, and
a list of fruitful directions for research early in the next millennium.
All papers in this volume reflect invited talks, are written by the invited speak-
ers, sometimes with a co-author, and are refereed. Alekos Kechris and George
Odifreddi were unable to speak, but submitted papers. Anil Nerode spoke on
Computable Analysis and Topology and Gerald Sacks on Higher Recursion Theory,
but there are no follow-up papers for these talks. Yiannis Moschovakis was, un-
fortunately, not able to attend and talk about Recursion in Computer Science. In
addition, two three-hour blocks of time were allocated for Barry Cooper to describe,
in detail, his work on constructing automorphisms of the degrees.
Of particular note was the intersection of this meeting with one on Topology
which was being held simultaneously. In particular, schedules were arranged so that