Computability, complexity, and languages : fundamentals of theoretical computer science /: fundamentals of theoretical computer science. (1994)

• Record Type: Book
• Further Information: Note: Martin D. Davis, Ron Sigal, Elaine J. Weyuker.
• Other Names: Davis, Martin, 1928-; Sigal, Ron; Weyuker, Elaine J
• Contents: Front Cover; Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science; Copyright Page; Dedication; Table of Contents; Preface; Acknowledgments; Dependency Graph; Chapter 1. Preliminaries; 1. Sets and n-tuples; 2. Functions; 3. Alphabets and Strings; 4. Predicates; 5. Quantifiers; 6. Proof by Contradiction; 7. Mathematical Induction; Part 1: Computability; Chapter 2. Programs and Computable Functions; 1. A Programming Language; 2. Some Examples of Programs; 3. Syntax; 4. Computable Functions; 5. More about Macros; Chapter 3. Primitive Recursive Functions. 1. Composition2. Recursion; 3. PRC Classes; 4. Some Primitive Recursive Functions; 5. Primitive Recursive Predicates; 6. Iterated Operations and Bounded Quantifiers; 7. Minimalization; 8. Pairing Functions and Gödel Numbers; Chapter 4. A Universal Program; 1. Coding Programs by Numbers; 2. The Halting Problem; 3. Universality; 4. Recursively Enumerable Sets; 5. The Parameter Theorem; 6. Diagonalization and Reducibility; 7. Rice's Theorem; *8. The Recursion Theorem; *9. A Computable Function That Is Not Primitive Recursive; Chapter 5. Calculations on Strings. 1. Numerical Representation of Strings2. A Programming Language for String Computations; 3. The Languages L and Ln; 4. Post-Turing Programs; 5. Simulation of Ln in F; 6. Simulation of F in L; Chapter 6. Turing Machines; 1. Internal States; 2. A Universal Turing Machine; 3. The Languages Accepted by Turing Machines; 4. The Halting Problem for Turing Machines; 5. Nondeterministic Turing Machines; 6. Variations on the Turing Machine Theme; Chapter 7. Processes and Grammars; 1. Semi-Thue Processes; 2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes. 3. Unsolvable Word Problems4. Post's Correspondence Problem; 5. Grammars; 6. Some Unsolvable Problems Concerning Grammars; *7. Normal Processes; Chapter 8. Classifying Unsolvable Problems; 1. Using Oracles; 2. Relativization of Universality; 3. Reducibility; 4. Sets r.e. Relative to an Oracle; 5. The Arithmetic Hierarchy; 6. Post's Theorem; 7. Classifying Some Unsolvable Problems; 8. Rice's Theorem Revisited; 9. Recursive Permutations; Part 2: Grammars and Automata; Chapter 9. Regular Languages; 1. Finite Automata; 2. Nondeterministic Finite Automata; 3. Additional Examples. 4. Closure Properties5. Kleene's Theorem; 6. The Pumping Lemma and Its Applications; 7. The Myhill-Nerode Theorem; Chapter 10. Context-Free Languages; 1. Context-Free Grammars and Their Derivation Trees; 2. Regular Grammars; 3. Chomsky Normal Form; 4. Bar-Hillel's Pumping Lemma; 5. Closure Properties; *6. Solvable and Unsolvable Problems; 7. Bracket Languages; 8. Pushdown Automata; 9. Compilers and Formal Languages; Chapter 11. Context-Sensitive Languages; 1. The Chomsky Hierarchy; 2. Linear Bounded Automata; 3. Closure Properties; Part 3: Logic; Chapter 12. Propositional Calculus.
• Edition: 2nd ed
• Publisher Details: Boston : Academic Press, Harcourt, Brace
• Publication Date: 1994
• Extent: 1 online resource (xix, 609 pages), illustrations
• Subjects: 511.3; Machine theory; Computational complexity; Formal languages; Computational complexity; Formal languages; Machine theory; MATHEMATICS -- Infinity; MATHEMATICS -- Logic; Computational complexity; Formal languages; Machine theory; Electronic books
• Languages: English
• ISBNs: 9780080502465; 0080502466
• Related ISBNs: 0122063821; 9780122063824
• Notes: Note: Includes bibliographical references (pages 593-594)-and indexes.
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.