Theory of Computation
Last updated
2003-02-10-22:35 -0800 (pst)
- see also:
- Readings
in Logic
Readings in Mathematics
Readings in Philosophy
-
- [Barendregt1981]
- Barendregt, Hendrik Pieter. The Lambda Calculus: Its Syntax and
Semantics. North-Holland (Amsterdam, 1981). ISBN
0-444-85490-8. Studies in Logic and the Foundations of
Mathematics, vol. 103.
This is one of my fundamental sources on the
lambda calculus. I want to pay particular attention to combinatory
logic (CL) and combinatory algebra (CA). My notes
on this book focus on that.
Content
Preface
Part I. Towards the Theory
1. Introduction
2. Conversion
3. Reduction
4. Theories
5. Models
Part II. Conversion
6. Classical
Lambda Calculus
7. The Theory of
Combinators
8. Classical
Lambda Calculus (continued)
9. The λI-Calculus
10. Böhm
Trees
Part III. Reduction
11. Fundamental
Theorems
12. Strongly
Equivalent Reductions
13. Reduction
Strategies
14. Labelled
Reduction
15. Other Notions
of Reduction
Part IV. Theories
16. Sensible
Theories
17. Other Lambda
Theories
Part V. Models
18. Construction
of Models
19. Local
Structure of Models
20. Global
Structure of Models
21. Combinatory
Groups
Appendices
Appendix A. Typed
Lambda Calculus
Appendix B.
Illative Combinatory Logic
Appendix C.
Variables
References
Index of Names
Index of Definitions
Index of Symbols
- [Chaitin1998]
- Chaitin, Gregory J. The Limits of Mathematics: A Course on
Information Theory and the Limits of Formal Reasoning. Springer-Verglag
Singapore (Singapore: 1998). ISBN 981-3083-59-X.
Contents
Foreword by Cristian Calude
Preface
Randomness in arithmetic and the decline and
fall of reductionism in pure mathematics [1993]
Elegant LISP programs [1996]
An invitation to algorithmic information theory
[1997]
The limits of mathematics [1996]
Appendix: LISP interpreter in Mathematica
- [Chaitin1999]
- Chaitin, Gregory J. The Unknowable. Springer-Verlag
Singapore (Singapore: 1999). ISBN 981-4021-72-5 (hardcover).
HTML version on-line at http://www.umcs.maine.edu/~chaitin/unknowable
and http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable.
"... The essence of this book is words,
explaining mathematical ideas, but readers who feel so inclined can
follow me all the way to LISP programs that pretty much show Gödel's,
Turing's and my proofs working on the computer. And if you want to
play with this software, you can download it from my web site.
"This book is also a 'prequel' to my
Springer book The Limits of Mathematics.
It's an easier introduction to my ideas, and uses the same version of
LISP that I use in The Limits of Mathematics. I hope it'll
be a stepping stone for those for whom The Limits of Mathematics
is too intimidating." From the Preface, pp. v-vi.
Contents
Preface
I. A Hundred Years of Controversy Regarding the
Foundations of Mathematics
II. LISP: A Formalism for Expressing
Mathematical Algorithms
III. Gödel's Proof of His Incompleteness
Theorem
IV. Turing's Proof of the Unsolvability of the
Halting Problem
V. My Proof that You Can't Show that a LISP
Program is Elegant
VI. Information & Randomness: A
Survey of Algorithmic Information Theory
VII. Mathematics in the Third Millennium?
Bibliography
- [Church1936]
- Church, Alonzo. An Unsolvable Problem of Elementary Number
Theory. American Journal of Mathematics 58 (1936),
345-363. Reprinted in pp. 88-107 of [Davis1965]
This is the paper in which Church makes the
assertion since known as Church's Thesis (and lately, the Church-Turing
Thesis). The annotated
citation is now carried in Readings
in Logic. -- dh:2002-10-10
- [Davis1965]
- Davis, Martin (ed.). The Undecidable: Basic Papers on
Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven
Press (New York: 1965). ISBN 0-911216-01-4.
A collection of fundamental papers by Gödel, Church, Post, etc.
The papers that have direct bearing on the Miser Project are cited
individually in one of the appropriate annotated bibliographies.
As I have continued to explore mathematical
logic as a context for computation theory and the Miser Project, I am
now inclined to classify most of these papers as strongly centered in
mathematical logic and as less specific to computation, even the seminal
work of Turing. This book's annotated citation is now carried
under Readings in Logic.
-- dh:2002-07-26
- [Davis1982]
- Davis, Martin. Computability and Unsolvability. Dover (New York: 1958,
1973, 1982). ISBN 0-486-61471-9 pbk.
A précis is available here.
This is a primary reference in the theory of
computation. Although it does not address Church's Thesis and
effective computability, it is widely used for its mapping of the
foundation of computation theory. In my readings
and notes, I want to make sure that my updated formulation, centered
on combinatory logic and combinatory algebra, is appropriately tied to
this foundation and other fundamental works in
this area. -- dh:2000-08-09
Content
Preface to the Dover Edition [1982]
Preface to the First Edition
Glossary of Special Symbols
Introduction
Part 1: The General Theory of Computability
1. Computable
Functions
2. Operations on
Computable Functions
3. Recursive
Functions
4. Turing
Machines Self-Applied
5. Unsolvable
Decision Problems
Part 2: Applications of the General Theory
6. Combinatorial
Problems
7. Diophantine
Equations
8. Mathematical
Logic
Part 3: Further Development of the General
Theory
9. The Kleene
Hierarchy
10. Computable
Functions
11. The
Classification of Unsolvable Decision Problems
Appendix 1: Some Results from the Elementary
Theory of Numbers
Appendix 2. Hilbert's Tenth Problem is
Unsolvable
References
Index
- [Garey1979]
- Garey, Michael R., Johnson, David S. Computers and
Intractability: A Guide to the Theory of NP-Completeness. W.
H. Freeman (New York: 1979). ISBN 0-7167-1045-5 pbk.
Way off-topic: I found this
book on in the local public library on the "any book for 10˘"
cart of donated books. It had me recall that I donated my 3-volume
bound set of Principia Mathematica to the Los Altos public
library in 1999 and I wonder if anyone bought it, maybe for as much as
50˘ per volume. dh: 2001-02-07.
Content
Preface
1. Computers, Complexity, and Intractability
2. The Theory of NP-Completeness
3. Proving NP-Completeness Results
4. Using NP-Completeness to Analyze Problems
5. NP-Hardness
6. Coping with NP-Complete Problems
7. Beyond NP-Completeness
Appendix A: A List of NP-Complete
Problems
A.1 Graph Theory
A.2 Network
Design
A.3 Sets and
Partitions
A.4 Storage and
Retrieval
A.5 Sequencing
and Scheduling
A.6 Mathematical
Programming
A.7 Algebra and
Number Theory
A.8 Games and
Puzzles
A.9 Logic
A.10 Automata and
Language Theory
A.11 Program
Optimization
A.12
Miscellaneous
A.13 Open
Problems
Symbol Index
Reference and Author Index
Subject Index
Update for the Second Printing [April,
1980]
- [Hopcroft2001]
- Hopcroft, John E., Motwani, Rajeev., Ullman, John D. Introduction
to Automata Theory, Languages, and Computation. ed.2.
Addison-Wesley (Boston, MA: 2001). ISBN 0-201-44124-1.
2003-02-10: I was possessed the
day I packed this book home from the University Bookstore. It was
all Sipser and Vaughn Pratt's fault. Beside liking the look and
the approach of this book, I am also tracing how recursively-enumerable
became Turing recognizable and recursive became Turing decidable.
But even more fun is the index entry here: "Algorithm, see
Recursive language." Oh. My. Goodness. Me.
Content
Preface
1. Automata: The Methods and the Madness
2. Finite Automata
3. Regular Expressions and Languages
4. Properties of Regular Languages
5. Context-Free Grammars and Languages
6. Pushdown Automata
7. Properties of Context-Free Languages
8. Introduction to Turing Machines
9. Undecidability
10. Intractable Problems
11. Additional Classes of Problems
Index
- [Johnson1979]
- Garey, Michael R., Johnson, David S. Computers and
Intractability: A Guide to the Theory of NP-Completeness. W.
H. Freeman (New York: 1979). ISBN 0-7167-1045-5 pbk. See [Garey1979]
This considerate style of having a
citation for every author of a work is practiced in this book. The
moment I saw it, I realized I wanted to apply it also. I haven't
gone back over other books yet, although I shall, as I continue working
on my readings and notes. dh: 2001-02-07.
- [Lewis1981]
- Lewis, Harry R., Papadimitriou, Christos H. Elements of the Theory of
Computation. Prentice-Hall (Englewood Cliffs, NJ: 1981). ISBN 0-13-273417-6.
This is an undergraduate introductory text on the theory of computation.
2000-07-18: I
am looking for notations and references and these chapters are fruitful for
the Miser Project: 1. Sets, Relations, and Languages. 3. Context-Free
Languages (but minimally - just for presenting a context-free grammar as a
demonstration that a language is recursive and solvable). 5. Church's
Thesis, again, not deeply but enough to appeal to the connection between
recursive functions, Turing-computability, etc. 6. Uncomputability, for
making sure I keep the language straight, 7. The Propositional Calculus
(maybe), and 8. The Predicate Calculus for connection to inference systems
and such.
The material on logic is for later, I think. I want to use simpler
presentations for this, but I want to be consistent with this kind of
more-abstracted treatment.
2000-09-12: All right, this is the second time
I have checked this book out of the local public library, renewed it
once, and kept it overdue without looking at it. Today I looked
through it more and I will do what I have done with [Davis1982]:
Order my own copy. The table of contents says it all:
1. Sets, Relations and Languages
1.1 "If-Then" and its
Relatives [big breakthrough for computational logic! -- dh:]
1.2 Sets
1.3 Relations and Functions
1.4 Special Types of Binary
Relations
1.5 Closures
1.6 Finite and Infinite Sets
1.7 Three Fundamental Proof
Techniques
1.8 Alphabets and Languages
1.9 Finite Representation of
Languages
2. Finite Automata
3. Context-Free Languages
4. Turing Machines
5. Church's Thesis
5.1 Church's Thesis
5.2 Grammars
5.3 The Primitive Recursive
Functions
5.4 Gödelization
5.5 The µ-Recursive Functions
5.6 Turing-Computability of the
µ-Recursive Functions
5.7 Universal Turing Machines
6. Uncomputability
7. Computational Complexity
8. The Propositional Calculus
9. The Predicate Calculus
2000-09-13: Well, a good plan that is
impossible to execute: This book is now in its second edition, and the
second edition is consistently panned by readers, especially in
comparison to the first edition which is held in higher repute by people
willing to confront the mathematics.
So I may just have to keep checking this one out of the library when I
want to verify what it offers against the other sources I have for
these topics. I do like the outline of the original, so I will
stay with it. (orcmid)
-
- [Lifschitz1991]
- Lifschitz, Vladimir (ed.) Artificial Intelligence and Mathematical
Theory of Computation: Papers in Honor of John McCarthy. Academic Press (San
Diego: 1991). ISBN 0-12-450010-2.
John McCarthy was 64 in 1991 and these
papers are in his honor. I picked it up in the Stanford Bookstore in 1993
and have held onto it all this time. It survived the cut of my last two
moves.
2000-07-18: There are a number of interesting
items here. One that I hadn't
expected is a paper by Carolyn Talcott on binding structures. There are also
John C. Mitchell's "On the Equivalence of Data Representations"
to dig into as well as a number of papers on inference systems, and dealing
with recursive forms of functions by Knuth and also Solomon Feferman.
Robert
Cartright's "Lambda: the Ultimate Combinator" will be interesting
because with the Miser Engine, lambda is a defined operation on objects
representing formulae, rather than being part of the meta-notation. I don't
get all of Cartright's idea, but I want to.
There is a very revealing paper by Herbert
Stoyan, "The Influence of
the Designer on the Design -- J. McCarthy and LISP." I was always
baffled by the bugs in the original short definition of the LISP evaluator,
and here is some useful background on that. I kept thinking I was simply
thick and not getting it, when I first saw the original LISP papers. The FUNARG problem
is one that we simply will not have and will not tolerate in Miser.
I also learned here that the Russian computer scientist Andrei Ershov had died
by 1991. That's very disappointing. I had a very
brief correspondence with Ershov in the early 80's about some things I
learned from his genuine extensions to BNF, and now I cannot renew that
discussion.
Content
Preface
Contributor List
A Short Sketch of the Life and Career of John
McCarthy, D.J. Israel
Functional Instantiations in First-Order Logic,
R.S. Boyer, D.M. Goldschlag, M. Kaufmann, and J.S.
Moore
Lambda: The Ultimate Combinator, R.
Cartwright
Proofs of Termination and the "91"
Function, S. Feferman
Robots with Common Sense? J.A. Feldman
Ascribing Artificial Intelligence to (Simpler)
Machines, or When AI Meets the Real World, R.E. Filman
The Design of Parallel
Programming Languages, R.P. Gabriel
Metaprogamming at Work in Automated
Manufacturing, C. Goad
LISP + Calculus = Identities, R.W. Gosper
Model Checking vs. Theorem Proving: A
Manifesto, J.Y. Halpern and M.Y. Vardi
Algebraic Computation: The Quiet Revolution, A.C.
Hearn
LISP and Parallelism, T. Ito
Textbook Examples of Recursion, D.E. Knuth
A Metalogic Programming Approach to Multi-Agent
Knowledge and Belief, R. Kowalski and J.S. Kim
Belief and Introspection, H.J. Levesque
Monotonicity Properties in Automated Deduction,
Z. Manna, M. Stickel, and R. Waldinger
Circumscription and Disjunctive Logic
Programming, J. Minker, J. Lobo and A. Rajasekar
On the Equivalence of Data Representations, J.C.
Mitchell
Caution! Robot Vehicle! H.P. Moravec
Circumscription and Authority, P.K. Rathmann
and G. Wiederhold
The Frame Problem in the Situation Calculus: A
Simple Solution (Sometimes) and a Completeness Result for Goal
Regression, R. Reiter
An Abstraction Mechanism for Symbolic
Expressions, M. Sato
Varieties of Context, Y. Shoham
The Influence of the Designer on the Design --
J. McCarthy and LISP, H. Stoyan
Binding Structures, C. Talcott
Logicism, AI, and Common Sense: John McCarthy's
Program in Philosophical Perspective, R.H. Thomason
The Incorrectness of the Bisection Algorithm, R.
Weyhrauch
Index
- [Motwani2001]
- Hopcroft, John E., Motwani, Rajeev., Ullman, John D. Introduction
to Automata Theory, Languages, and Computation. ed.2.
Addison-Wesley (Boston, MA: 2001). ISBN 0-201-44124-1. See [Hopcroft2001]
- [Papadimitriou1981]
- Lewis, Harry R., Papadimitriou, Christos H. Elements of the Theory of
Computation. Prentice-Hall (Englewood Cliffs, NJ: 1981). ISBN 0-13-273417-6.
See [Lewis1981]
-
- [Revesz1988]
- Révész, György E. Lambda-Calculus,
Combinators and Functional Programming. Cambridge University Press
(Cambridge, 1988). ISBN 0-521-34589-8.
2000-07-18: I have book-marked some material
in here on the idea of extensionally-equal (Definition 1.1, which comes
up in the theory for CL) and the nice explanation of the set-theoretic
model of functions and the procedural view of functions, considered the
older model.
Chapter 3 is about combinators and constant symbols and
ways people have dealt with placeholders.
There are also representations
of arithmetic and logic (Boolean values) in CL, and the treatment of
recursion is something I need to understand better, especially around
finding fixed-points. There are additional things here, that can be used
in building implementations and applying Miser engines. For example, list processing, handling
infinite-lists, stuff like that. (I don't propose to go down that road
very far, but I have my eye out for useful definitions for
list-processing primitives, string manipulation, and other things.) The
Church-Rosser theorem is treated in here, also. And a treatment of FP,
the John Backus approach to functional programming.
I want to be very careful about how true and false is represented in the
Miser Engine. In one respect, true and false can be represented any way that
we want. But the primitive operation for equality has to produce some sort
of result and it, along with an idiom for conditional evaluation, will
create a truth representation. So I want to come up with a comparison result
that fits into this and is both useful and revealing.
Content
Preface
1. Introduction
2. Type-Free Lambda Calculus
3. Combinators and Constant Symbols
4. List Manipulation in Lambda-Calculus
5. Rule-Based Semantics of λ-expressions
6. Outlines of a Reduction Machine
7. Towards a Parallel Graph-Reduction
Appendix A. A Proof of the Church-Rosser
Theorem
Appendix B. Introduction to Typed λ-Calculus
Bibliographical notes
References
- [Sipser1997]
- Sipser, Michael.
Introduction to the Theory of Computation.
PWS Publishing (Boston, MA: 1997). ISBN 0-534-94728-X.
"You are about to embark on the study of a
fascinating and important subject: the theory of computation. It
comprises the fundamental mathematical properties of computer hardware,
software, and certain applications thereof. In studying this
subject we seek to determine what can and cannot be computed, how
quickly, with how much memory, and on which type of computational
model. The subject has obvious connections with engineering
practice, and, as in many sciences, it also has purely philosophical
aspects." From the Preface, p.xi.
2001-08-06: This book has been singled
out for use in a self-study/on-line-reading group project of the Learn-CS-Theory
on-line discussion group. The syllabus
follows the sections of the Contents. Participation on this
group is my peculiar way of having added yet one more unmastered tome on
computation theory to my collection. I shall use the structure
provided by the group, such as it may be, to forward my own adoption of
current CS concepts and terminology for application to The Miser
Project.
Content
Preface
0. Introduction
0.1 Automata,
Computability, and Complexity
0.2 Mathematical
Notions and Terminology
0.3 Definitions,
Theorems, and Proofs
0.4 Types of
Proof
Exercises and
Problems
Part One: Automata and Languages
1. Regular Languages
1.1 Finite
Automata
1.2
Nondeterminism
1.3 Regular
Expressions
1.4 Nonregular
Languages
Exercises and
Problems
2. Context-Free Languages
2.1 Context-Free
Grammars
2.2 Pushdown
Automata
2.3
Non-context-free Languages
Exercises and
Problems
Part Two: Computability Theory
3. The Church-Turing Thesis
3.1 Turing
Machines
3.2 Variants of
Turing Machines
3.3 The
Definition of Algorithm
Exercises and
Problems
4. Decidability
4.1 Decidable
Languages
4.2 The Halting
Problem
Exercises and
Problems
5. Reducibility
5.1 Undecidable
Problems from Language Theory
5.2 A Simple
Undecidable Problem
5.3 Mapping
Reducibility
Exercises and
Problems
6. Advanced Topics in Computability Theory
6.1 The Recursion
Theorem
6.2 Decidability
of Logical Theories
6.3 Turing
Reducibility
6.4 A Definition
of Information
Exercises and
Problems
Part Three: Complexity Theory
7. Time Complexity
7.1 Measuring
Complexity
7.2 The Class P
7.3 The Class NP
7.4
NP-Completeness
7.5 Additional
NP-Complete Problems
Exercises and
Problems
8. Space Complexity
8.1 Savitch's
Theorem
8.2 The Class
PSPACE
8.3 PSPACE-Completeness
8.4 The Classes L
and NL
8.5
NL-Completeness
8.6 NL Equals
coNL
Exercises and
Problems
9. Intractability
9.1 Hierarchy
Theorems
9.2
Relativization
9.3 Circuit
Complexity
Exercises and
Problems
10. Advanced Topics in Complexity Theory
10.1
Approximation Algorithms
10.2
Probabilistic Algorithms
10.3 Alternation
10.4 Interactive
Proof Systems
10.5 Parallel
Computation
10.6 Cryptography
Exercises and
Problems
Selected Bibliography
Index
- [Ullman2001]
- Hopcroft, John E., Motwani, Rajeev., Ullman, John D. Introduction
to Automata Theory, Languages, and Computation. ed.2.
Addison-Wesley (Boston, MA: 2001). ISBN 0-201-44124-1. See [Hopcroft2001]
created 2000-07-18-17:03 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 03-02-10 23:02 $
$$Revision: 22 $
Home