A SURVEY OF THE GENERAL THEORY OF EFFECTIVELY COMPUTABLE FUNCTIONS
Abstract
The general theory of effective computability is surveyed to transmit to engineering and scientific personnel the basic concepts. Specifically, the notion of algorithm is introduced and made precise via the theory of Turing computability. After the concept of partial computability follow sections on finite automata - where the theory of Rabin and Scott is developed - and formal axiomatic systems - where the limitive theorems of Church, Godel and Tarski are stated. The survey develops in detail the theory of recursive functions concluding with some of the well-known solvable and unsolvable cases of decision problem theory. A recapitulation of the limitive theorems of formal axiomatics in terms of recursive function theory is made. Several topics of interest in current research which draw upon the prior development of the survey are also presented. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1962
- Accession Number
- AD0273300
Entities
People
- Frank B. Cannonito
- Gerald D. Fogel
Organizations
- Grumman