|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910828235103321 |
|
|
Autore |
Davis Martin <1928-2023, > |
|
|
Titolo |
Computability, complexity, and languages : fundamentals of theoretical computer science / / Martin D. Davis, Elaine J. Weyuker |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
New York, New York ; ; London, [England] : , : Academic Press, , 1983 |
|
©1983 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Descrizione fisica |
|
1 online resource (448 p.) |
|
|
|
|
|
|
Collana |
|
Computer Science and Applied Mathematics |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Machine theory |
Computational complexity |
Formal languages |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Description based upon print version of record. |
|
|
|
|
|
|
Nota di bibliografia |
|
Includes bibliographical references and index. |
|
|
|
|
|
|
Nota di contenuto |
|
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 |
4. Post-Turing ProgramsCHAPTER 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 Problems; 4. Post's Correspondence Problem; 5. Grammars; 6. Some Unsolvable Problems Concerning Grammars; 7. Recursion and Minimalization; 8. Normal Processes |
9. A Non-R.E. SetPART 2: GRAMMARS AND AUTOMATA; CHAPTER 8. Regular Languages; 1. Finite Automata; 2. Nondeterministic Finite Automata; 3. Additional Examples; 4. Closure Properties; 5. Kleene's |
|
|
|
|