Computability and complexity : from a programming perspective

MIT Press

1997

xvi, 466 pages

Foundations of computing

9780262100649

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 abstra- near 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

Английский