Book contents
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Computing in Algebraic Systems
Published online by Cambridge University Press: 09 February 2010
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Summary
INTRODUCTION
Given a relational structure A, imagine an A-register machine which can hold in its registers a fixed, finite number of elements of A, perform the basic operations and decide the basic relations on these elements, and manage some simple manipulations and decisions such as to replace the contents of one register by those of another and to tell when two registers carry the same element. Next, picture an A-register machine with counting by adding a finite number of counting registers to an A-register machine; these carry natural numbers and the device is able to put zero into a counting register, add or subtract one from the contents of any counting register, tell if two registers contain the same number, and so on. Thirdly, there is the A-register machine with stacking which augments an A-register machine with a single stack register into which the entire contents of the ordinary algebraic registers of the basic machine can be temporarily placed at various points in the course of a calculation. Thus, the combinatorial operations of the A-register machine are extended in the first instance by permitting subcomputations on the natural numbers ω and in the second by prolonging the number and complexity of entirely algebraic subcomputations. On arranging both we have an A-register machine with counting and stacking.
To use one of these machines to compute a partial function on A is to write down the familiar finite program of instructions referring to whatever activities of the machine are available and containing information to stop in certain circumstances.
- Type
- Chapter
- Information
- Recursion Theory, its Generalisations and Applications , pp. 215 - 235Publisher: Cambridge University PressPrint publication year: 1980
- 12
- Cited by