Computability in Combinatory Spaces

One service mathematics bas rendered the 'Bt moi, .... si j'avait su comment en revenir, je human race. It bas put common sense back n'y semis point aU6.' where it belongs, on the topmost shelf next to Jules Verne the dusty canister labelled 'discarded nonsense'. BrieT.Bell The series is divergent; therefore we may be able to do something with it. O. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and nonlineari ties abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sci ences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One ser vice topology has rendered mathematical physics .. .'; 'One service logic has rendered computer science .. .'; 'One service category theory has rendered mathematics .. .'. All arguably true. And all statements obtainable this way form part of the raison d' 8tre of this series.

Texte du rabat

This volume provides an account of the current state of the theory of combinatory spaces and discusses various applications. Here the term `combinatory space' can be regarded as a system for functional programming, and bears no close connection with combinatory logic. br/ The main text is divided into three chapters. Chapter 1 deals with computational structures and computability; Chapter 2 considers combinatory spaces; and Chapter 3 embraces computability in iterative combinatory spaces. A number of appendices treat a survey of examples of combinatory spaces. All sections of the various chapters contain exercices togethers with hints for solution where appropriate. br/ For the reading of some parts of the book a knowledge of mathematical logic and recursive function theory would be desirable. br/ For researchers and specialists in mathematical logic and its applications and theoretical computer scientists. br/

Contenu
I. Computational Structures and Computability on them.- 1. Computational structures.- 2. Computability of partial functions with respect to a given computational structure.- 3. On a procedure for generating the unary partial recursive functions.- 4. On the interconnection between programmability in a FP - system and ?- computability.- 5. Computability of multiple-valued functions with respect to a given computational structure.- 6. The recursively enumerable binary relations considered as multiple-valued functions.- 7. On the notions of prime and search computability.- 8. Computability in the case of unproductive termination taken into account.- II. Combinatory Spaces.- 1. The notion of combinatory space.- 2. The companion operative space of a combinatory space.- 3. Iteration in combinatory spaces.- 4. On least fixed points in partially ordered sets.- 5. The companion operative space of an iterative combinatory space.- 6. Left-homogeneous mappings and least fixed points connected with them.- 7. Some formal systems for the theory of iterative combinatory spaces.- III. Computability in Iterative Combinatory Spaces.- 1. Explicit and fixed-point definability in partially ordered algebras.- 2. Computable elements and mappings in iterative combinatory spaces.- 3. Representation of the partial recursive functions in iterative combinatory spaces.- 4. The First Recursion Theorem for iterative combinatory spaces.- 5. Application of the First Recursion Theorem to some concrete iterative combinatory space.- 6. Normal Form Theorems for computable elements and mappings in iterative combinatory spaces.- 7. Universal computable elements in iterative combinatory spaces.- 8. A notion of search computability in iterative combinatory spaces.- 9. On the formalization of the proof of theFirst Recursion Theorem.- References.- Additional Bibliography.- Index of Names.- Index of Definitions.