s
Esentials
of
heoretic
T
al
ter
Compu
nc
Scie
e
F. D. Lewis
University of Kentucky
How to Navigate
This Text
Table of
Contents
O
CNTENTS
Title Page
Copyright Notice
Preface
COMPUTABILITY
Introduction
The NICE Programming Language
Turing Machines
A Smaller Programming Language
Equivalence of the Models
Machine Enhancement
The Theses of Church and Turing
Historical Notes and References
Problems
UNSOLVABILITY
Introduction
Arithmetization
Properties of the Enumeration
Universal Machines and Simulation
Solvability and the Halting Problem
Reducibility and Unsolvability
Enumerable and Recursive Sets
Historical Notes and References
Problems
COMPLEXITY
Introduction
Measures and Resource Bounds
Complexity Classes
Reducibilities and Completeness
The Classes P and NP
Intractable Problems
Historical Notes and References
Problems
AUTOMATA
Introduction
Finite Automata
Closure Properties
Nondeterministic Operation
Regular Sets and Expressions
Decision Problems for Finite Automata
Pushdown Automata
Unsolvable Problems for Pushdown Automata
Linear Bounded Automata
Historical Notes and References
Problems
LANGUAGES
Introduction
Grammars
Language Properties
Regular Languages
Context Free Languages
Context Free Language Properties
Parsing and Deterministic Languages
Summary
Historical Notes and References
Problems
C
P
B
Y
OMUTAILIT
Before examining the intrinsic nature of computation we must have a precise
idea of what computation means. In other words, we need to know what we’re
talking about! To do this, we shall begin with intuitive notions of terms such as
calculation, computing procedure, and algorithm. Then we shall be able to
develop a precise, formal characterization of computation which captures all of
the modern aspects and concepts of this important activity.
Part of this definitional process shall involve developing models of
computation. They will be presented with emphasis upon their finite nature
and their computational techiques, that is, their methods of transforming
inputs into outputs. In closing, we shall