Details

Subject(s)

• Computer programming [Browse]
• Computational complexity [Browse]

Series

Foundations of computing. [More in this series]

Bibliographic references

Includes bibliographical references (p. [447]-455] and index.

Action note

Committed to retain in perpetuity — ReCAP Shared Collection (HUL)

Contents

• Introduction
• The WHILE language
• Programs as data objects
• Self-interpretation: universal programs for WHILE and I
• Elements of computability theory
• Metaprogramming, self-application, and compiler generation
• Other sequential models of computation
• Robustness of computability
• Computability by functional languages (partly by T.Æ. Mogensen)
• Some natural unsolvable problems
• Hilbert's tenth problem (by M.H. Sorensen)
• Inference systems and Gödel's incompleteness theorem
• Computability theory based on numbers
• More abstract approaches to computability
• Overview of complexity theory
• Measuring time usage
• Time usage of tree-manipulating programs
• Robustness of time-bounded computation
• Linear and other time hierarchies for WHILE programs
• The existence of optimal algorithms (by A.M. Ben-Amram)
• Space-bounded computations
• Nondeterministic computations
• A structure for classifying the complexity of various problems
• Characterizations of LOGSPACE and PTIME by GOTO programs
• Completeness and reduction of one problem to another
• Complete problems for PTIME
• Complete problems for NPTIME
• Complete problems for PSPACE
• A mathematical terminology and concepts.

Show 26 more Contents items

ISBN

0262100649 (alk. paper)

LCCN

^^^96044043^

OCLC

35723572

RCP

H - S

Statement on language in description

Princeton University Library aims to describe library materials in a manner that is respectful to the individuals and communities who create, use, and are represented in the collections we manage. Read more...