Computability and computable models. (English) Zbl 1143.03017

Gabbay, Dov M. (ed.) et al., Mathematical problems from applied logic. II. Logics for the XXIst century. New York, NY: Springer (ISBN 978-0-387-69244-9/hbk). International Mathematical Series (New York) 5, 99-216 (2007).
In this 118 pages long survey paper the author first notes that, in view of the wide range of applications, there are the following two important directions in computability theory: (1) Investigation of the bounds for the applicability of a given computable model and an algorithm to an object existing in reality and the processes flowing there; (2) Creation of computability theory over abstract structures which could provide a unique approach to both computational processes in continuous models in reality and their discrete analogs.
The paper is devoted to an investigation of the first direction. The author reviews recent important results and formulates more than 30 current problems and open questions dictated by applications of the theory of computable models. The first section, entitled “Preliminaries”, contains basic facts from model theory, theory of numerations and computability theory that are necessary for the subsequent sections. The list of the remaining sections is the following: (2) Bounds for computable models; (3) Structural complexity of computable models; (4) Isomorphism problem; (5) Classes of computable models and index sets.
For the entire collection see [Zbl 1109.03003].


03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures