+612 9045 4394
 
CHECKOUT
Models of Computation and Formal Languages - R. Gregory Taylor

Models of Computation and Formal Languages

Hardcover Published: 1st November 1997
ISBN: 9780195109832
Number Of Pages: 686

Share This Book:

Hardcover

RRP $274.95
$222.40
19%
OFF
or 4 easy payments of $55.60 with Learn more
This title is not in stock at the Booktopia Warehouse and needs to be ordered from our supplier.
Click here to read more about delivery expectations.

Models of Computation and Formal Languages presents a comprehensive and rigorous treatment of the theory of computability. The text takes a novel approach focusing on computational models and is the first book of its kind to feature companion software. Deus Ex Machina, developed by Nicolae Savoiu, comprises software simulations of the various computational models considered and incorporates numerous examples in a user-friendly format.
Part I of the text introduces several universal models including Turing machines, Markov algorithms, and register machines. Complexity theory is integrated gradually, starting in Chapter 1. The vector machine model of parallel computation is covered thoroughly both in text and software. Part II develops the Chomsky hierarchy of formal languages and provides both a grammar-theoretic and an automata-theoretic characterization of each language family. Applications to programming languages round out an in-depth theoretical discussion, making this an ideal text for students approaching this subject for the first time. Ancillary sections of several chapters relate classical computability theory to the philosophy of mind, cognitive science, and theoretical linguistics.
Ideal for Theory of Computability and Theory of Algorithms courses at the advanced undergraduate or beginning graduate level, Models of Computation and Formal Languages is one of the only texts that... ‹¨« ‹¨« Features accompanying software available on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp/ Adopts an integrated approach to complexity theory
‹¨« Offers a solutions manual containing full solutions to several hundred exercises. Most of these solutions are available to students on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp ‹¨« Features examples relating the theory of computation to the probable programming experience of an undergraduate computer science major

Preface
Mathematical Preliminaries
Sets and Set-Forming Operations
Introduction to Formal Language Theory
Mappings and Functions
Defining Functions Recursively
The Mathematics of Big-O Notation
Mathematical Induction
Graphs
Introduction to Propositional Logic
Two Important Proof Techniques
Defining Sets Recursively
Infinite Sets
Conjunctive Normal Form
Number-Theoretic Predicates
Further Reading
Models of Computation
Turing Machines
What Is Computation?
An Informal Description of Turing Machines
The Formal Definition of Turing Machines
Turing Machines as Language Acceptors and as Language Recognizers
Turing Machines as Computers of Number-Theoretic Functions
Modular Construction of Turing Machines
Introduction to Complexity Theory
Suggestions for Further Reading
Additional Varieties of Turing Machines
Turing Machines with One-Way-Infinite Tape
Turing Machines that Accept by Terminal Stare
Multitape Turing Machines
Encoding of Turing Machines
Universal Turing Machines
Nondeterministic Turing Machines
A Number-Theoretic FUnction That Is Not Turing-Computable
Turing Machines and Artificial Intelligence
Turing Machines and Cognitive Science
Regarding Theoretical Computer Science and Number-Theoretic Functions
Further Reading
An Introduction to Recursion Theory
The Primitive Recursive Functions
Primitive Recursive Predicates
The Partial Recursive Functions
The Class of Partial Recursive Functions Is Identical to the Class of Turing-Computable Functions
Recursive Sets
Recursively Enumerable Sets
Historical Remarks and Suggestions for Further Reading
Markov Algorithms
An Alternative Model of Sequential Computation
Markov Algorithms as Language Acceptors and as Language Recognizers
Markov Algorithms as Computers of Number-Theoretic Functions
Labeled Markov Algorithms
The Class of Markov-Computable Functions Is Identical to the Class of Partial Recursive Functions
Considerations of Efficiency
Computation Theory and the Foundations of Mathematics
Bibliography
Register Machines
Register Machines
The Class of Register-Machine-Computable Functions Is Identical to the Class of Partial Recursive Functions
Register Machines and Formal Languages
A Model-Independent Characterization of Computational Feasibility
Final Remarks and Suggestions for Further Reading
Post Systems (Optional)
Post Systems and Formal Languages
The Class of Post-Computable Functions Is Identical to the Class of Partial Recursive Functions
Closure Properties of the Class of Languages Generated by Post Systems
The Class of Languages Generated by Post Systems Is Identical to the Class of Turing-Acceptable Languages
Language Recognition and Post Systems
What Is a Model of Computation?
The Vector Machine Model of Parallel Computation (Optional)
What Is Parallel Computation?
Vectors and Vector Operations
Vect
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9780195109832
ISBN-10: 019510983X
Audience: Tertiary; University or College
Format: Hardcover
Language: English
Number Of Pages: 686
Published: 1st November 1997
Publisher: Oxford University Press Inc
Country of Publication: US
Dimensions (cm): 25.4 x 20.32  x 3.81
Weight (kg): 1.36