Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Goncharov and Peretyat'kin independently gave necessary and sufficient conditions for when a set of types of a complete theory T is the type spectrum of some homogeneous model of T. Their result can be stated as a principle of second order arithmetic, which is called the Homogeneous Model Theorem (HMT), and analyzed from the points of view of computability theory and reverse mathematics. Previous computability theoretic results by Lange suggested a close connection between HMT and the Atomic Model Theorem (AMT), which states that every complete atomic theory has an atomic model. The authors show that HMT and AMT are indeed equivalent in the sense of reverse mathematics, as well as in a strong computability theoretic sense and do the same for an analogous result of Peretyat'kin giving necessary and sufficient conditions for when a set of types is the type spectrum of some model.

Reverse mathematics. --- Computable functions. --- Decidability (Mathematical logic)

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Recursion theory - now a well-established branch of pure mathematics, having grown rapidly over the last 35 years - deals with the general (abstract) theory of those operations which we conceive as being `computable' by idealized machines. The theory grew out of, and is usually still regarded, as a branch of mathematical logic. This book is a collection of advanced research/survey papers by eminent research workers in the field, based on their lectures given at the Leeds Logic Colloquium 1979. As such it provides an up-to-date view of current ideas and developments in the field of recursion theory as a whole. The individual contributions fit together naturally so as to provide an overview of all the main areas of research in the field. It will therefore be an important and invaluable source for advanced researchers and research students in mathematics and computer science (particularly in Europe, USA and USSR).

Recursion theory --- Recursive functions --- Functions, Recursive --- Algorithms --- Arithmetic --- Logic, Symbolic and mathematical --- Number theory --- Decidability (Mathematical logic) --- Foundations

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers.

Computable functions --- Fonctions recurrentes --- Functies [Rekenkundige ] --- Berekenbaarheid. --- Computable functions. --- Fonctions calculables --- Computability theory --- Functions, Computable --- Partial recursive functions --- Recursive functions, Partial --- Constructive mathematics --- Decidability (Mathematical logic)

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation i

Computable functions. --- Constructive mathematics. --- Mathematics, Constructive --- Logic, Symbolic and mathematical --- Computability theory --- Functions, Computable --- Partial recursive functions --- Recursive functions, Partial --- Constructive mathematics --- Decidability (Mathematical logic)

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Driven by the question, "What is the computational content of a (formal) proof ?", this book studies fundamental interactions between proof theory and computability. It provides a unique self-contained text for advanced students and researchers in mathematical logic and computer science. Part I covers basic proof theory, computability and Gödel's theorems. Part II studies and classifies provable recursion in classical systems, from fragments of Peano arithmetic up to Π11-CA0. Ordinal analysis and the (Schwichtenberg-Wainer) subrecursive hierarchies play a central role and are used in proving the 'modified finite Ramsey' and 'extended Kruskal' independence results for PA and Π11-CA0. Part III develops the theoretical underpinnings of the first author's proof assistant MINLOG. Three chapters cover higher-type computability via information systems, a constructive theory TCF of computable functionals, realizability, Dialectica interpretation, computationally significant quantifiers and connectives and polytime complexity in a two-sorted, higher-type arithmetic with linear logic.

Computable functions --- Proof theory --- Computable functions. --- Proof theory. --- Logic, Symbolic and mathematical --- Computability theory --- Functions, Computable --- Partial recursive functions --- Recursive functions, Partial --- Constructive mathematics --- Decidability (Mathematical logic)