Comparative Schematology.
Abstract
While we may have the intuitive idea of one programming language having greater power than another, or of some subset of a language being an adequate 'core' for that language, we find when we try to formalize this notion that there is a serious theoretical difficulty. This lies in the fact that even quite rudimentary languages are nevertheless 'universal' in the following sense. If the language allows us to program with simple arithemtic or list-processing functions than any effective control structure can be simulated, traditionally, by encoding a Turing machine computation in some way. In particular, a simple language with some basic arithmetic can express programs for any partial recursive function. Such an encoding is usually quite unnatural and impossibly inefficient. Thus in order to carry on a practical study of the comparative power of different languages we are led to banish explicit functions and deal instead with abstract, uninterpreted programs, or schemas. What follows is a brief report on some preliminary exploration in this area. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1978
- Accession Number
- ADA062699
Entities
People
- Carl E. Hewitt
- Michael S. Paterson
Organizations
- Massachusetts Institute of Technology