Miser Project Readings Theory of Computation

miser>readings> theory.htm> 0.01 2017-08-29 16:40

see also: 

Readings in Logic [Orcmid's Lair]
Readings in Mathematics  [Orcmid's Lair]
Readings in Philosophy  [Orcmid's Lair]
Readings in Functional Programming

 

[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]
   

You are navigating the Miser Project.

created 2000-07-18-17:03 -0700 (pdt) by orcmid $$Date: 17-08-29 16:40 $ $$Revision: 31 $