Essentials_of_Theoretical_Computer_Science-Lewis.pdf

(1298 KB) Pobierz
Essentials
s
of
Theoretical
heoretic
Computer
ter
Science
nc
F. D. Lewis
University of Kentucky
How to Navigate
This Text
Table of
Contents
CONTENTS
O
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
COMPUTABILITY
C
P
B
Y
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 compare our various models and
discuss their relative power.
The sections are entitled:
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
The
NICE
Programming Language
As computer scientists, we tend to believe that computation takes place inside
computers. Or maybe computations are the results from operating computing
machinery. So, when pressed to describe the limits of computation we might, in
the spirit of Archimedes and his lever, reply that anything can be computed
given a large enough computer! When pressed further as to how this is done we
probably would end up by saying that all we need in order to perform all
possible computations is the ability to execute programs which are written in
some marvelous, nonrestrictive programming language. A
nice
one!
Since we are going to
study
computation rather than engage in it, an actual
computer is not required, just the programs. These shall form our model of
computation. Thus an ideal programming language for computation seems
necessary. Let us call this the
NICE
language and define it without further
delay. Then we can go on to describing what is meant by computation.
We first need the raw materials of computation. Several familiar items come
immediately to mind.
Numbers
(integers as well as real or floating point) and
Boolean constants
(true and
false)
will obviously be needed. Our programs shall
then employ
variables
that take these constants as values. And since it is a
good idea to tell folks exactly what we're up to at all times, we shall declare
these variables before we use them. For example:
var
x, y, z: integer;
p, q: Boolean;
a, b, c: real;
Here several variables have been introduced and defined as to
type.
Since the
world is often nonscalar we always seem to want some data structures.
Arrays
fill that need. They may be multidimensional and are declared as to type and
dimension. Here is an array declaration.
var
d, e: array[ , ] of integer;
s: array[ ] of real;
h: array[ , , , ] of integer;

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin