Concise Guide to Computation Theory

• Main Author: Maruoka, Akira (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: London : Springer London : Imprint: Springer, 2011.
• Subjects: Computer science.; Computers.; Computer mathematics.; Computer Science.; Theory of Computation.; Computational Science and Engineering.

Computation lies at the heart of modern digital technology and our increasingly advanced information society. The theory of computation describes what tasks can and cannot be computed, and how efficiently the computable tasks can be computed. This focused and accessible guide/textbook presents a tho...

Table of Contents:

• Part I: The Theory of Computation
• Everything Begins With Computation
• Preliminaries to the Theory of Computation
• Part II: Automata and Languages
• Finite Automata
• Context-Free Languages
• Pushdown Automaton
• Part III: Computability
• Turing Machine
• Universality of Turing Machine and its Limitation
• Part IV: Complexity of Computation
• Computational Complexity Based on Turing Machines
• Computational Complexity Based on Boolean Circuits
• NP-Completeness
• Solutions
• Concluding Remarks.