[FOM] book announcement

S B Cooper pmt6sbc at maths.leeds.ac.uk
Thu Feb 6 09:26:47 EST 2003


Computability and Models
Perspectives East and West

edited by
S. Barry Cooper
School of Mathematics, University of Leeds, UK
Sergei S. Goncharov
Dept. of Mechanics and Mathematics, Novosibirsk State University, Russia

Kluwer Academic/Plenum Publishers
Hardbound, ISBN 0-306-47400-X
January 2003,  388 pp.
EUR 142.00 /  USD 135.00 /  GBP 90.50


There are few notions as fundamental to contemporary science as those of
computability and modelling.  'Computability and Models' attempts to make
some of the exciting and important new research developments in this area
accessible to a wider readership. Written by international leaders drawn
from major research centres both East and West, this book is an essential
addition to scientific libraries serving both specialist and the
interested non-special reader.

>From the Preface:

"Science involves {\it descriptions} of the world we live in.  It also
depends on nature exhibiting what we can best describe as a high {\it
algorithmic content}. The theme running through this collection of papers
is that of the interaction between descriptions, in the form of formal
theories, and the algorithmic content of what is described, namely of the
{\it models} of those theories. This appears most explicitly here in a
number of valuable, and substantial, contributions to what has until
recently been known as `recursive model theory' -- an area in which
researchers from the former Soviet Union (in particular Novosibirsk) have
been pre-eminent. There are also articles concerned with the computability
of aspects of familiar mathematical structures, and --- a return to the
sort of basic underlying questions considered by Alan Turing in the early
days of the subject --- an article giving a new perspective on
computability in the real world. And, of course, there are also articles
concerned with the classical theory of computability, including the first
widely available survey of work on quasi-reducibility.

The contributors, all internationally recognised experts in their fields,
have been associated with the three-year INTAS-RFBR Research Project
'Computability and Models' (Project No. 972-139), and most have
participated in one or more of the various international workshops (in
Novosibirsk, Heidelberg and Almaty)  and other research activities of the
network. Although based on just eight research centres -- Almaty,
Heidelberg, Ivanovo, Kazan, Leeds, Novosibirsk, Siena and Turin -- the
project has acted as a focus for researchers from all over Europe and
beyond. This has been an exciting and rewarding experience for everybody
involved, and has helped transform the fragmented European scene of ten or
more years ago (so vividly described by George Odifreddi in his
entertaining introduction to this volume) into the lively community of
researchers we now see developing.

The articles which follow approach this important and growing area of
research from many different angles.  The authors were encouraged to
provide {\it readable} introductions to their research. All have responded
either with timely surveys of work inadequately covered elsewhere, or with
interesting and important new results, with clear pointers to the wider
context. All articles have been rigorously refereed, and revised


Introduction - P. Odifreddi. Truth-Table Complete Computably Enumerable
Sets - M.M. Arslanov. Completeness and Universality of Arithmetical
Numbering - S. Badaev, S. Goncharov, A. Sorbi. Algebraic Properties of
Rogers Semilattices of Arithmetical Numberings - S. Badaev, S. Goncharov,
S. Podzorov, A.  Sorbi.  Isomorphism Types and Theories of Rogers
Semilattices of Arithmetical Numberings - S. Badaev, S. Goncharov, A.
Sorbi.  Computability over Topological Structures - V. Brattka.
Incomputability In Nature - S.B. Cooper, P.  Odifreddi. Gems in the Field
of Bounded Queries - W. Gasarch. Finite End Intervals in Definable
Quotients of E - E. Herrmann. A Tour of Robust Learning - S. Jain, F.
Stephan. On Primitive Recursive Permutations - I.  Kalimullin. On
Self-Embeddings of Computable Linear Orders - S. Lempp, A.S. Morozov,
C.F.D. McCoy, D.R. Solomon. Definable Relations on the Computably
Enumerable Degrees - A. Li.  Quasi-Degrees of Recursively Enumerable Sets
- R.Sh. Omanadze. Positive Structures - V. Selivanov. Local Properties of
the Non-Total Enumeration Degrees - B. Solon.


More information about the FOM mailing list