Collaboration in Computability

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

This award will support activities of a research network of mathematicians working in computability theory. This project will facilitate collaborative work of faculty and graduate students from the U.S., Russia, Kazakhstan and Bulgaria. The research is in quickly developing areas of computability, and this project has two broad goals: the first goal is more rapid scientific progress resulting from a network of collaborators, from all four countries, enabling them to pool their ideas to solve fundamental problems. The second goal is to provide opportunities for students and young researchers to participate actively in the world community of scientists. Computability as a research area has blossomed in recent years, with many exciting new results that involve combining techniques from pure computability with sophisticated algebra, model theory, set theory, and/or probability. There are also stronger ties with computer science. The proposal named 20 senior participants, and students and postdocs will also participate in the activities supported by the grant. The proposed work includes a variety of problems. There are problems on the difficulty in building a copy of a structure (degree spectra), and on the relative computing power of structures (Muchnik reducibility). There are problems on the internal complexity of structures (Scott rank) and on the difficulty of describing a structure, measured by the complexity of a ``Scott sentence''. In particular, there are problems on Scott sentences for groups. Some problems concern uncountable structures such as the ordered field of reals. There are problems on ``jumps'' of structures and a strong notion of ``jump inversion''. There are problems on complexity of isomorphisms, and on automorphisms, in particular, for vector spaces. There are problems on degree structures (enumeration degrees, and ``continuous'' degrees). There are problems on ``numberings''. At least two problems, one on the ``Hanf number'' for Scott sentences of computable structures, and one on the relative computing power of the ordered field of reals and an expansion by an arbitrary continuous function, have been solved since the proposal was submitted.