Accession Number:

AD0744206

Title:

Further Results on Hierarchies of Canonic Systems

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1972-05-01

Pagination or Media Count:

86.0

Abstract:

The thesis outlines a new way of presenting the theory of canonic systems, including a distinction for methodic reasons between simple canonic systems and general canonic systems, and proves a series of results on hierarchies of canonic systems. After a brief summary of Doyles results on a partial hierarchy of canonic systems, a new hierarchy is developed which relates the general canonic systems not only to all 4 types of formal grammars defined by Chomsky but also to any class of formal grammars definable in terms of productions. It is also shown that all attempts to define a mathematical system which exactly corresponds to the recursive sets are necessarily fruitless.

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE