Book anouncement
Computability and Models, Perspectives East and West
edited by
S. Barry Cooper
School of Mathematics, University of Leeds, United Kingdom
Sergei S. Goncharov
Deptartment 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
Book Series: UNIVERSITY SERIES IN MATHEMATICS
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.
ORDER AT:
http://www.wkap.nl/prod/b/0-306-47400-X
From the Preface
Science involves descriptions of the world we live in. It also
depends on nature exhibiting what we can best describe as a high
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
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 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
accordingly.
Contents
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.