A connotational theory of program structure
This book attacks some questions of foundational character regarding the programming languages, by settling a new language independent theory of program structure. This theory uses in an extensive way the well established apparatus of recursive function theory, which leads to some significant results, that could probably have not been obtained by other approaches like the denotational semantics or the theory of program schemes. The basic frame is that of effective numberings which represent what is in essence the class of all theoretically possible programming languages. It allows a very general definition of the notion of control structure, which covers all the usual representatives of this notion (if...then...else, while...do, etc.). Hence, a main objective of this book is a detailed study of this numberings. It is shown that a semilattice structure, called the Rogers semilattice, can be embedded in the family of effective numberings, which has similar algebraical properties with the much better known semilattice of m-degrees of r.e sets. The acceptable numberings which are those effective numberings into which every other effective numbering has an effective translation play a prominent part in the book. An important problem is that of characterizing the acceptable numberings. There are some well-known such characterizations like the one of Rogers (a numbering having the s-l-l function is acceptable) or the one due to Machtey, Winklmann, and Young who showed that an effective numbering admitting an implementation of the composition operator is acceptable. Such results are largely extended in this book in an attempt to understand which control structures characterize acceptability. Several new control structures are found which taken in pair characterize acceptability. Some of these matters are also discussed from a computational complexity point of view. For example it is shown that in an effective numbering which has s-l-l as a primitive, all the other control structures can be built within a relatively low complexity bound. Another topic extensively discussed is that of the relative dependence of some usual control structures. A quite general technique is developed for control structure independence arguments by the help of which, to cite one result out of many, it is shown that conditional, for-loop, primitive recursion form an independent set in the sense that none of the three control structures can be built from the other two. An extension of this technique is used to obtain complexity independence results: for example, there are acceptable numberings in which conditional and while are efficiently represented, but in which repeat has only representations beyond an arbitrary, preassigned complexity bound. In conclusion, this monograph offers some relevant results to matters which seem to have been less focused by computer scientists in the last time. Whether the impact of the book will produce a change in this attitude is at this time an open problem. Contents: Chapter 1. Motivations, Background, and Basic Definitions, Chapter 2. Effective numberings, Completions, and Control Structures, Chapter 3. Some Special Effective Numberings, Chapter 4. Characterizations of Acceptability, Chapter 5. Independence of Control Structures, Chapter 6. General Programming Properties of Effective Numberings of Subrecursive Classes, Bibliography, Notation Index, Definition Index.
- Maximal machine learnable classes
- Composition is almost (but not quite) as good as \(s-1-1\)
- Program size restrictions in computational learning
- Learning-theoretic perspectives of acceptable numberings
- The synthesis of language learners.
- Effectivity questions for Kleene's recursion theorem
- Some independence results for control structures in complete numberings
- Characteristics of minimal effective programming systems
- Effectivity questions for Kleene's recursion theorem
- Program self-reference in constructive Scott subdomains
- Spatial/kinematic domain and lattice computers
- scientific article; zbMATH DE number 605140 (Why is no real title available?)
- Acceptable Numerations of Morphisms and Myhill‐Shepherdson Property
- Learnability: admissible, co-finite, and hypersimple languages
- Parsimony hierarchies for inductive inference
- Hypothesis spaces for learning
- Computable one-to-one enumerations of effective domains
- Costs of general purpose learning
- Control structures in hypothesis spaces: The influence on learning
- Machine induction without revolutionary paradigm shifts
- A learning-theoretic characterization of classes of recursive functions
- Program self-reference in constructive Scott subdomains
- Constructivity conditions on immune sets
- Control structures in computable numberings and the completion operator
- Computably enumerable sets of reals in constructive mathematical analysis
- Characterizing programming systems allowing program self-reference
This page was built for publication: A connotational theory of program structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579920)
