Higher Recursion Theory

Author: Gerald E. Sacks

Publisher: Cambridge University Press

ISBN: 1316739465

Category: Mathematics

Page: N.A

View: 1785

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the second publication in the Perspectives in Logic series, is an almost self-contained introduction to higher recursion theory, in which the reader is only assumed to know the basics of classical recursion theory. The book is divided into four parts: hyperarithmetic sets, metarecursion, α-recursion, and E-recursion. This text is essential reading for all researchers in the field.

Bounded Queries in Recursion Theory

Author: William S. Levine,Georgia Martin

Publisher: Springer Science & Business Media

ISBN: 1461206359

Category: Computers

Page: 353

View: 1975

One of the major concerns of theoretical computer science is the classifi cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.

Recursion Theory

Computational Aspects of Definability

Author: Chi Tat Chong,Liang Yu

Publisher: Walter de Gruyter GmbH & Co KG

ISBN: 3110275643

Category: Mathematics

Page: 320

View: 6128

This monograph presents recursion theory from a generalized and largely global point of view. A major theme is the study of the structures of degrees arising from two key notions of reducibility, the Turing degrees and the hyperdegrees, using ideas and techniques beyond those of classical recursion theory. These include structure theory, hyperarithmetic determinacy and rigidity, basis theorems, independence results on Turing degrees, as well as applications to higher randomness.

The Role of True Finiteness in the Admissible Recursively Enumerable Degrees

Author: Noam Greenberg

Publisher: American Mathematical Soc.

ISBN: 0821838857

Category: Mathematics

Page: 99

View: 7078

When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of $\alpha$-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees.We show that if an admissible ordinal $\alpha$ is effectively close to $\omega$ (where this closeness can be measured by size or by confinality) then such constructions may be performed in the $\alpha$-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of $\alpha$-r.e. degrees for various classes of admissible ordinals $\alpha$. Together with coding work which shows that for some $\alpha$, the theory of the $\alpha$-r.e. degrees is complicated, we get that for every admissible ordinal $\alpha$, the $\alpha$-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.

Fundamentals of Mathematical Logic

Author: Peter G. Hinman

Publisher: A K Peters/CRC Press

ISBN: 9781568812625

Category: Mathematics

Page: 896

View: 6957

This introductory graduate text covers modern mathematical logic from propositional, first-order and infinitary logic and Gödel's Incompleteness Theorems to extensive introductions to set theory, model theory and recursion (computability) theory. Based on the author's more than 35 years of teaching experience, the book develops students' intuition by presenting complex ideas in the simplest context for which they make sense. The book is appropriate for use as a classroom text, for self-study, and as a reference on the state of modern logic.

Logic Colloquium 76

Proceedings of a Conference held in Oxford in July 1976

Author: R. O. Gandy,J. M. E. Hyland

Publisher: N.A

ISBN: 9780720422009

Category: Logic, Symbolic and mathematical

Page: 612

View: 6649

The higher infinite

large cardinals in set theory from their beginnings

Author: Akihiro Kanamori

Publisher: Springer

ISBN: 9783540570714

Category: Mathematics

Page: 536

View: 3156

After describing the beginnings of the subject - the theory of large cardinals - a comprehensive account is given of the work in the 1960s on partition properties, forcing and sets of reals, and aspects of measurability (including saturated ideals and inner models of measurability). Then discussed are the strong hypotheses like supercompactness up to Kunen's inconsistency. The last sections describe the investigation of determinacy from its beginnings up to a survey of the recent consistency results of Woodin. The material is presented in the context of its historical development and leads to the frontiers of contemporary research. It will serve as a reference and guide to graduate students and researchers in set theory and set-theoretic topology.


Author: Vanderbilt University

Publisher: N.A

ISBN: 9780897918916

Category: Machine learning

Page: 338

View: 9532

Constructivity and Computability in Historical and Philosophical Perspective

Author: Jacques Dubucs,Michel Bourdeau

Publisher: Springer

ISBN: 9401792178

Category: Philosophy

Page: 214

View: 4053

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic.

Recursively Enumerable Sets and Degrees

A Study of Computable Functions and Computably Generated Sets

Author: Robert I. Soare

Publisher: Springer Science & Business Media

ISBN: 9783540152996

Category: Mathematics

Page: 437

View: 8742

..."The book, written by one of the main researchers on the field, gives a complete account of the theory of r.e. degrees. .... The definitions, results and proofs are always clearly motivated and explained before the formal presentation; the proofs are described with remarkable clarity and conciseness. The book is highly recommended to everyone interested in logic. It also provides a useful background to computer scientists, in particular to theoretical computer scientists." Acta Scientiarum Mathematicarum, Ungarn 1988 ..."The main purpose of this book is to introduce the reader to the main results and to the intricacies of the current theory for the recurseively enumerable sets and degrees. The author has managed to give a coherent exposition of a rather complex and messy area of logic, and with this book degree-theory is far more accessible to students and logicians in other fields than it used to be." Zentralblatt für Mathematik, 623.1988

Computability and Models

Perspectives East and West

Author: Barry S. Cooper,Sergei S. Goncharov

Publisher: Springer Science & Business Media

ISBN: 1461507553

Category: Mathematics

Page: 375

View: 9452

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 "Com putability 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 otherresearch activities of the network.

Proofs and Computations

Author: Helmut Schwichtenberg,Stanley S. Wainer

Publisher: Cambridge University Press

ISBN: 1139504169

Category: Mathematics

Page: N.A

View: 3971

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.

Perspectives in Computation

Author: Robert Geroch

Publisher: University of Chicago Press

ISBN: 0226288552

Category: Computers

Page: 200

View: 5959

Perspectives in Computation covers three broad topics: the computation process & its limitations; the search for computational efficiency; & the role of quantum mechanics in computation.

The Future of Post-Human Mathematical Logic

Author: Peter Baofu

Publisher: Cambridge Scholars Publishing

ISBN: 1443806218

Category: Medical

Page: 278

View: 1459

Why should mathematical logic be grounded on the basis of some formal requirements in the way that it has been developed since its classical emergence as a hybrid field of mathematics and logic in the 19th century or earlier? Contrary to conventional wisdom, the foundation of mathematic logic has been grounded on some false (or dogmatic) assumptions which have much impoverished the pursuit of knowledge. This is not to say that mathematical logic has been useless. Quite on the contrary, it has been quite influential in shaping the way that reality is to be understood in numerous fields of knowledge—by learning from the mathematical study of logic and its reverse, the logical study of mathematics. In the final analysis, the future of mathematical logic will depend on how its foundational crisis is to be resolved, and "the contrastive theory of rationality" (in this book) is to precisely show how and why it can be done by taking a contrastive turn, subject to the constraints imposed upon by "existential dialectic principles" at the ontological level (to avoid any reductionistic fallacy) and other ones (like the perspectives of culture, society, nature, and the mind). The contrastive theory of rationality thus shows a better way to ground mathematical logic (beyond both classical and non-classical logics) for the future advancement of knowledge and, if true, will alter the way of how mathematical logic is to be understood, with its enormous implications for the future of knowledge and its "post-human" fate.