Description: Preface0.: Mathematical Preliminaries.1: Sets and Set-Forming Operations.2: Introduction to Formal Language Theory.3: Mappings and Functions.4: Defining Functions Recursively.5: The Mathematics of Big-O Notation.6: Mathematical Induction.7: Graphs.8: Introduction to Propositional Logic.9: Two Important Proof Techniques.10: Defining Sets Recursively.11: Infinite Sets.12: Conjunctive Normal Form.13: Number-Theoretic Predicates.14: Further ReadingPart I MODELS OF COMPUTATION1 .: Turing Machines1.1: What Is Computation?1.2: An Informal Description of Turing Machines1.3: The Formal Definition of Turing Machines1.4: Turing Machines as Language Acceptors and as Language Recognizers1.5: Turing Machines as Computers of Number-Theoretic Functions1.6: Modular Construction of Turing Machines1.7: Introduction to Complexity Theory1.8: Suggestions for Further Reading2: Additional Varieties of Turing Machines2.1: Turing Machines with One-Way-Infinite Tape2.2: Turing Machines that Accept by Terminal Stare2.3: Multitape Turing Machines2.4: Encoding of Turing Machines2.5: Universal Turing Machines2.6: Nondeterministic Turing Machines2.7: A Number-Theoretic FUnction That Is Not Turing-Computable2.8: Turing Machines and Artificial Intelligence2.9: Turing Machines and Cognitive Science2.10: Regarding Theoretical Computer Science and Number-Theoretic Functions2.11: Further Reading3: An Introduction to Recursion Theory3.1: The Primitive Recursive Functions3.2: Primitive Recursive Predicates3.3: The Partial Recursive Functions3.4: The Class of Partial Recursive Functions Is Identical to the Class of Turing-Computable Functions3.5: Recursive Sets3.6: Recursively Enumerable Sets3.7: Historical Remarks and Suggestions for Further Reading4: Markov Algorithms4.1: An Alternative Model of Sequential Computation4.2: Markov Algorithms as Language Acceptors and as Language Recognizers4.3: Markov Algorithms as Computers of Number-Theoretic Functions4.4: Labeled Markov Algorithms4.5: The Class of Markov-Computable Functions Is Identical to the Class of Partial Recursive Functions4.6: Considerations of Efficiency4.7: Computation Theory and the Foundations of Mathematics4.8: Bibliography5: Register Machines5.1: Register Machines5.2: The Class of Register-Machine-Computable Functions Is Identical to the Class of Partial Recursive Functions5.3: Register Machines and Formal Languages5.4: A Model-Independent Characterization of Computational Feasibility5.5: Final Remarks and Suggestions for Further Reading6: Post Systems (Optional)6.1: Post Systems and Formal Languages6.2: The Class of Post-Computable Functions Is Identical to the Class of Partial Recursive Functions6.3: Closure Properties of the Class of Languages Generated by Post Systems6.4: The Class of Languages Generated by Post Systems Is Identical to the Class of Turing-Acceptable Languages6.5: Language Recognition and Post Systems6.6: What Is a Model of Computation?7.: The Vector Machine Model of Parallel Computation (Optional)7.1: What Is Parallel Computation?7.2: Vectors and Vector Operations7.3: Vector Machines7.4: Vector Machines and Function Computation7.5: Vector Machines and Formal Languages7.6: Parallel Computation and Cognitive Science7.7: Further Remarks8.: The Bounds of Computability8.1: The Church-Turing Thesis8.2: The Bounds of Computability-in-Principle: The Self-Halting Problem for Turing Machines8.3: The Bounds of Computability-in-Principle: The Halting Problem for Turing Machines8.4: The Bounds of Computability-in-Principle: Rice''s Theorem8.5: The Bounds of Feasible Computation: The Concept of NP-Completeness8.6: An NP-Complete Problem (Cook-Levin Theorem)8.7: Other NP-Complete Problems8.8: The Bounds of Parallel Computation: The Concept of P-Completeness (Advanced)8.9: A P-Complete Problem (Ladner''s Theorem) (Advanced)8.10: The Nearest-Neighbor Traveling Salesman Problem is P-Complete (Advanced)8.11: Beyond Symbol Processing: The Connectionist Model of Cognition8.12: Summary, Historical Remarks, and Suggestions for Further ReadingPart II FORMAL LANGUAGES AND AUTOMATA9.: Regular Languages and Finite-State Automata9.1: Regular Expressions and Regular Languages9.2: Deterministic Finite-State Automata9.3: Nondeterministic Finite-State Automata9.4: A Pumping Lemma for FSA-Acceptable Languages9.5: Closure Properties of the Family of FSA-Acceptable Languages9.6: The Family of Regular Languages Is Identical to the Family of FSA-Acceptable Languages9.7: Finite-State Automata with Epsilon-Moves9.8: Generative Grammars9.9: Right-Linear Grammars and Regular Languages9.10: Summary, Historical Remarks and Suggestions for Further Reading10.: Context-Free Languages and Pushdown-Stack Automata10.1: Context-Free Grammars and Natural Languages10.2: Normal Forms for Context-Free Grammars10.3: Pushdown-Stack Automata10.4: An Equivalent Notion of Word Acceptance for Pushdown-Stack Automata10.5: The Class of Context-Free Languages Is Identical to the Class of PSA-Acceptable Languages10.6: Closure Properties of the Family of Context-Free Languages10.7: A Pumping Lemma for Context-Free Languages10.8: Deterministic Context-Free Languages10.9: Decidability Results for Context-Free Languages10.10: Bibliography and Suggestions for Further Reading11.: Context-Sensitive Languages and Linear-Bounded Automata11.1: Context-Sensitive Grammars11.2: A Normal Form for Context-Sensitive Grammars11.3: Linear-Bounded Automata11.4: Context-Sensitive Languages and Linear-Bounded Automata11.5: Closure Properties of the Family of Context-Sensitive Languages11.6: The General Word Problem for Context-Sensitive Languages Is Solvable11.7: There Exist Turing-Recognizable Languages That Are Not Context-Sensitive11.8: Final Remarks12.: Generative Grammars and the Chomsky Hierarchy12.1: Turing Machines and Phrase-Structure Languages12.2: Closure Properties of the Family of Phrase-Structure Languages12.3: Turing Machiens as Language Enumerators12.4: A Recursion-Theoretic Characterization of the Family of Phrase-Structure Languages12.5: The General Word Problem for Phrase-Structure Languages Is Unsolvable12.6: The Post Correspondence Problem12.7: The Chomsky HierachyEpilogueBibliographyIndex

Please Wait