Mathematical Foundations of Programming

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0011.djvu
Foreword......Page __sk_0005.djvu
Preface......Page __sk_0007.djvu
1. The Effective......Page __sk_0017.djvu
1.1 Definition of Effectiveness......Page __sk_0018.djvu
1.2 The Modern Age of Pythagoras......Page __sk_0021.djvu
1.3 Algorithms......Page __sk_0025.djvu
1.4 Berry's Paradox......Page __sk_0027.djvu
Exercises......Page __sk_0030.djvu
Appendix: Effectiveness in the Roots of Mathematics......Page __sk_0033.djvu
1.5 Foundations of Mathematics and Troubles with the Infinite......Page __sk_0034.djvu
1.6 Constructive Mathematics......Page __sk_0038.djvu
1.7 Effective Processes in Physics......Page __sk_0042.djvu
1.8 The Arithmetization of Physics......Page __sk_0045.djvu
References......Page __sk_0047.djvu
2. Foundations of Mathematics I......Page __sk_0049.djvu
2.2 The Meaning and Extensions of Function......Page __sk_0050.djvu
2.3 A Function Considered as a Mapping from One Set into Another......Page __sk_0052.djvu
2.4 On Some Ways of Defining Functional Relationships......Page __sk_0054.djvu
2.5 Functions Defined on Objects Other than the Natural Numbers......Page __sk_0056.djvu
2.6 Functions of Functions......Page __sk_0057.djvu
2.7 Relations......Page __sk_0058.djvu
2.8 The Designation of Functions and the Lambda Notation......Page __sk_0059.djvu
2.9 Genetic Methods in Defining Sets......Page __sk_0062.djvu
2.10 Formal Systems......Page __sk_0063.djvu
2.11 Arithmetization......Page __sk_0067.djvu
2.12 Boolean Algebra......Page __sk_0069.djvu
2.13 An Axiomatic Formulation of the Propositional Calculus......Page __sk_0076.djvu
2.14 The Method of "Reductio Ad Absurdum"......Page __sk_0077.djvu
2.15 Forming a Boolean Expression Whose Truth Table Is Given......Page __sk_0078.djvu
2.16 On "Polish Notation"......Page __sk_0079.djvu
Exercises......Page __sk_0080.djvu
References......Page __sk_0083.djvu
3. Foundations of Mathematics II (Applications)......Page __sk_0085.djvu
3.1 Realizations of Boolean Algebra......Page __sk_0086.djvu
3.2 The Happy Marriage of Binary Arithmetic and Boolean Algebra......Page __sk_0090.djvu
3.3 The Boolean Algebra of Sets......Page __sk_0095.djvu
3.4 Miscellaneous Special Notation and Its Uses......Page __sk_0099.djvu
3.5 The Product of Sets......Page __sk_0101.djvu
3.6 The Role of Set Theory in Mathematics and in Computing......Page __sk_0102.djvu
3.7 The Theory of Transfinite Numbers......Page __sk_0105.djvu
3.8 Implications of the Theory of Transfinite Numbers to Computing......Page __sk_0110.djvu
Exercises......Page __sk_0111.djvu
Appendix: The Rudiments of Graph Theory......Page __sk_0114.djvu
3.9 Some Fundamental Notions of Graph Theory......Page __sk_0115.djvu
3.10 Miscellaneous Examples of Graphical Structures in Computing......Page __sk_0120.djvu
3.11 The Encoding of Graphs in the Computer......Page __sk_0123.djvu
3.12 Example of an Algorithmic Solution to a Graph-related Problem - The Minimal Path Problem......Page __sk_0126.djvu
Appendix Exercises......Page __sk_0128.djvu
References......Page __sk_0129.djvu
4. Recursive Functions......Page __sk_0131.djvu
4.2 "Recursive" Definitions......Page __sk_0132.djvu
4.3 The Basic Recursive Functions......Page __sk_0134.djvu
4.4 Possible Programming Language Features to Enable the Use of Function-generating Operations......Page __sk_0137.djvu
4.5 The Class of Primitive Recursive Functions......Page __sk_0138.djvu
4.6 Ackermann's Function......Page __sk_0140.djvu
4.7 The Class of Partial Recursive Functions......Page __sk_0144.djvu
4.9 A Programming Language PRECL Based upon the Generation of the Partial Recursive Functions......Page __sk_0147.djvu
4.10 Remarks on Vocabulary - "Recursive," "Iterative"......Page __sk_0149.djvu
4.11 Primitive Recursion and Mathematical Induction......Page __sk_0152.djvu
4.12 The Use of Iteration as an Alternative to Minimalization......Page __sk_0153.djvu
4.13 On Sets: Primitive Recursive, Recursive, Recursively Enumerable......Page __sk_0155.djvu
4.14 On Structured Programming......Page __sk_0159.djvu
Exercises......Page __sk_0163.djvu
References......Page __sk_0166.djvu
5. Turing Machines and Computability......Page __sk_0167.djvu
5.1 Motivations Underlying Turing Machines......Page __sk_0168.djvu
5.2 Organization of a Turing Machine......Page __sk_0171.djvu
5.3 The Use of Turing Machines to Compute Functions......Page __sk_0173.djvu
5.4 The Instantaneous Description of a Turing Machine......Page __sk_0174.djvu
5.5 Representation of Input and Output Data......Page __sk_0175.djvu
5.6 Additional Conventions......Page __sk_0177.djvu
5.7 Some Elementary Data-handling Operations......Page __sk_0181.djvu
5.8 Some More Complex Machine Operations......Page __sk_0183.djvu
5.9 The Arithmetization of Turing Machines......Page __sk_0186.djvu
5.10 "Proof" That if a Function Is Turing Machine Computable Then It Is Partial Recursive......Page __sk_0188.djvu
5.11 Some Implications to the "Real" World of Computing......Page __sk_0191.djvu
Exercises......Page __sk_0194.djvu
References......Page __sk_0196.djvu
6. The Universal Turing Machine, Some Implications of the Theory of Computability, Variants of Turing Machines......Page __sk_0197.djvu
6.1 The Universal Turing Machine......Page __sk_0199.djvu
6.2 The Halting Problem......Page __sk_0200.djvu
6.4 Variations of the Halting Problem......Page __sk_0203.djvu
6.5 A Noncomputable Function......Page __sk_0206.djvu
6.6 A Recursively Enumerable Set That Is Not Recursive......Page __sk_0207.djvu
6.8 The Busy-Beaver Problem......Page __sk_0209.djvu
6.10 Nondeterministic Turing Machines......Page __sk_0211.djvu
6.11 Wang Machines......Page __sk_0214.djvu
6.12 Register Machines of Shepherdson-Sturgis......Page __sk_0216.djvu
6.13 Cellular Automata......Page __sk_0218.djvu
6.14 A Turing Machine as a Symbol Manipulation System......Page __sk_0220.djvu
6.15 The Use of "Normal" Rewriting Rules and Some Special Symbol Manipulation Systems......Page __sk_0222.djvu
6.16 The Problem of "Tag"......Page __sk_0224.djvu
6.17 Computable Numbers......Page __sk_0226.djvu
6.18 Intimations of Gödel's Results......Page __sk_0228.djvu
6.19 Discussion of the Incompleteness Results and Some Possible Implications to the Question of Whether or Not Man Is a Machine......Page __sk_0230.djvu
Exercises......Page __sk_0231.djvu
References......Page __sk_0233.djvu
7. General Remarks about Automata......Page __sk_0235.djvu
7.1 What Is an Automaton?......Page __sk_0236.djvu
7.2 The Notions of "State" and of a "Mechanism"......Page __sk_0238.djvu
7.3 A Classification of Automata......Page __sk_0240.djvu
7.4 Functions Performed by Automata......Page __sk_0243.djvu
7.5 The Range of Automata......Page __sk_0244.djvu
7.6 Machines With Pushdown Stores and Machines with Stacks......Page __sk_0245.djvu
7.7 Nondeterminism and Monte Carlo Methods in Computing......Page __sk_0247.djvu
7.8 The Building Blocks of Automata......Page __sk_0251.djvu
7.9 Universal Logical Elements......Page __sk_0255.djvu
7.10 Feedback and Memory......Page __sk_0259.djvu
7.11 Oracles......Page __sk_0262.djvu
7.12 Automata and Thinking - The Turing Test......Page __sk_0264.djvu
Exercises......Page __sk_0267.djvu
References......Page __sk_0269.djvu
8. Finite Automata......Page __sk_0271.djvu
8.2 How They Are Described......Page __sk_0272.djvu
8.3 Sequential Machines......Page __sk_0274.djvu
8.4 Finite Automata as Recognition Devices......Page __sk_0277.djvu
8.5 What Functions Can a Transducer Compute?......Page __sk_0280.djvu
8.6 Nondeterministic Finite Automata......Page __sk_0283.djvu
8.7 Some Miscellaneous Notation Useful in Discussing Finite Automata......Page __sk_0284.djvu
8.8 Constructing a Deterministic Finite Automaton That Is Equivalent to a Given NDFA......Page __sk_0286.djvu
8.10 Regular Expressions, a Notation for the Regular Sets......Page __sk_0289.djvu
8.11 The Minimization of Finite Automata......Page __sk_0291.djvu
8.12 Finite Automata That Can Read Their Tapes Backwards......Page __sk_0292.djvu
8.13 Tree Automata......Page __sk_0295.djvu
Exercises......Page __sk_0297.djvu
References......Page __sk_0301.djvu
9. Formal Languages - Introduction......Page __sk_0303.djvu
9.1 Natural Languages and Formal Languages......Page __sk_0304.djvu
9.2 Symbolic Manipulation Systems - Rewriting Rules......Page __sk_0307.djvu
9.3 Formalization of These Systems......Page __sk_0310.djvu
9.4 A Classification of Languages......Page __sk_0314.djvu
9.5 Examples of the Definitions of Languages by Their Grammars......Page __sk_0316.djvu
9.6 Syntax, Semantics, and Ambiguity......Page __sk_0322.djvu
9.7 Parsing......Page __sk_0326.djvu
9.8 Some Uses of Finite Automata in Recognizing and Parsing Sentences of Context-Free Languages......Page __sk_0331.djvu
9.9 The Recognition of Prefixes in Parsing......Page __sk_0334.djvu
9.10 A Necessary Condition for a Language with Sufficiently Long Sentences To Be Context Free......Page __sk_0337.djvu
Exercises......Page __sk_0340.djvu
References......Page __sk_0342.djvu
10. Formal Languages - Further Relationships with Automata and Programming Languages......Page __sk_0345.djvu
10.1 The Definition of the Languages in the Chomsky Hierarchy in Terms of Classes of Automata......Page __sk_0347.djvu
10.2 Some Restricted Context-Free Grammars That Are of Special Importance in Parsing the Sentences, or Programs, of Programming Languages......Page __sk_0349.djvu
10.3 ALGOL Is Not Context Free......Page __sk_0353.djvu
10.4 Post's Correspondence Problem......Page __sk_0354.djvu
10.5 The Transitive Closure of a Relation......Page __sk_0360.djvu
10.6 An Application of the Transitive Closure of a Relation to a Problem of Formal Languages......Page __sk_0362.djvu
10.7 On Proving the Correctness of Programs......Page __sk_0364.djvu
10.8 The Definition of Semantics......Page __sk_0368.djvu
10.9 The Vienna Definition Language......Page __sk_0369.djvu
10.10 LINCOS, a Language for Cosmic Intercourse......Page __sk_0372.djvu
Exercises......Page __sk_0379.djvu
References......Page __sk_0382.djvu
11. Studies of Computational Complexity......Page __sk_0385.djvu
11.1 Complexity and Simplicity......Page __sk_0386.djvu
11.2 Remarks on the Mathematical Description of Rates of Growth......Page __sk_0388.djvu
11.3 The Mathematical Measure of Information......Page __sk_0390.djvu
11.4 The Information Content of a Finite Sequence......Page __sk_0392.djvu
11.5 Complexity of Machines......Page __sk_0393.djvu
11.6 Some Varied Problems of Complexity Theory......Page __sk_0394.djvu
11.7 An Axiomatic, Machine Independent Approach to the Definition of the Complexity of the Partially Computable Functions......Page __sk_0400.djvu
11.8 The Speed-up Theorem......Page __sk_0402.djvu
11.9 Functions Computable by Finite Automata......Page __sk_0403.djvu
11.10 Predictable Complexity - The Ritchie Hierarchy of the Elementary Arithmetic Functions......Page __sk_0405.djvu
11.11 The Use of "Fan-in" Components in a Circuit and Winograd's Minimal Bounds for Addition and Multiplication......Page __sk_0407.djvu
11.12 Time and Space Tradeoffs......Page __sk_0412.djvu
11.13 Probabilistic Algorithms......Page __sk_0414.djvu
11 14 "Real-time" Computations......Page __sk_0416.djvu
11.15 On the Randomness of Finite Sequences......Page __sk_0419.djvu
11.16 An Unsolved Problem, is P = NP?......Page __sk_0420.djvu
Exercises......Page __sk_0421.djvu
References......Page __sk_0423.djvu
12. Restatement and Summary of the Influence of Mathematical Ideas on Computing - Perspective, Comments......Page __sk_0425.djvu
12.1 Fundamental Notions and a Quick Survey of Some Selected Historical Developments......Page __sk_0426.djvu
12.2 Peano's Axioms......Page __sk_0427.djvu
12.3 Computability......Page __sk_0428.djvu
12.4 The Nature of Modern Mathematics - Abstraction and Axiomatization......Page __sk_0429.djvu
12.5 The Influence of Computing on Mathematics......Page __sk_0432.djvu
12.6 The Four-Color Theorem......Page __sk_0433.djvu
12.7 A Checklist of Some Key Relevant Mathematical Ideas......Page __sk_0438.djvu
12.8 General Remarks, the Chronology of Events......Page __sk_0439.djvu
Appendix: The Influence of Modern Algebra......Page __sk_0440.djvu
12.9 Computer Science and Algebra......Page __sk_0441.djvu
12.10 Categories of Machines......Page __sk_0444.djvu
References......Page __sk_0446.djvu
About the Author......Page __sk_0449.djvu
Index......Page __sk_0451.djvu