Theory of Computation - Hardcover

Brainerd, Walter S.; Landweber, Lawrence H.

Hardcover

ISBN 10: 0471095850 ISBN 13: 9780471095859

Publisher: John Wiley & Sons Canada, Limited, 1974

Synopsis

A partial list of subjects covered in each chapter includes: 1) INTRODUCTION: algorithms; sets, relations, and functions; representation of data; induction; some special functions; operations on functions; and cardinality. 2) ALGORITHMIC LANGUAGE: the language of PL & PL-computable functions and Church's Thesis. 3) RECURSIVE FUNCTIONS: primitive and partial recursive functions; closure properties; minimization; relations between functions and different alphabets; the pairing functions; and recursive sets. 4) MACHINE LANGUAGE: the unlimited-register machine; a compiler for PL programs and single-register machines; the Turing machine; and sets accepted by machines. 5) LABELED MARKOV ALGORITHMS (LMA): LMA simulation of Turing machine programs; SNOBOL; partial recursiveness of functions computed by LMA's; universal functions and programs; and an index of recursion theorems. 6) RECURSIVELY ENUMERABLE SETS: programs that enumerate sets; properties of recursively enumerable sets (RE); index of RE sets; effective enumerability of sets of functions; and finite sets. 7) FORMAL LANGUAGES: post production systems; recursive enumerability of each language; grammar for each RE set; normal systems; production rates w/multiple antecedents; and context-free, context-sensitive, and linear grammars. 8) REDUCIBILITY: programs and oracles; degrees; and strong reductibility. 9) COMPLEXITY OF COMPUTATIONS: properties of and axioms for dynamic complexity measures; complexity classes of recursive functions; and the Speedup Theorem. 10) SUBRECURSIVE HIERARCHIES: hierarchy of primitive recursive functions; loop programs; and Grzegorczyk Hierarchy. 11) INTRO. TO COMBINATORY LOGIC: the calculi; adequacy for and equivalence with partial recursiveness and its functions; and consistency. All chapters also include a specific history, and severed include undecidable problems, as well.

About this edition

• Publisher: John Wiley & Sons Canada, Limited
• Publication date: 1974
• ISBN 10: 0471095850
• ISBN 13: 9780471095859
• Binding: Hardcover
• Edition number: 1
• Number of pages: 358