Program Synthesis & Neurosymbolic Reasoning: A Foundation for General Intelligence

Preface

Part I: Foundations of Symbolic AI and Program Synthesis

Chapter 1: Introduction to Symbolic Reasoning

1. Propositional and Predicate Logic
2. Automated Theorem Proving and Logic Programming
3. Knowledge Representation and Reasoning
4. Search, Planning, and Constraint Satisfaction
5. Shared Utilities
6. Running the Examples

Chapter 2: The Program Synthesis Problem

1. Enumerative Search: Bottom-Up
2. Version Space Algebras
3. Stochastic and Evolutionary Search
4. Formal Problem Statement
5. Running the Examples

Part II: Core Methods in Program Synthesis

Chapter 3: Inductive Synthesis & Programming by Example (PBE)

1. String Transformations with Whole-String Primitives
2. Version Spaces
3. Stochastic and Evolutionary Search
4. Flash Fill in a Toy DSL
5. The Flash Fill Algorithm: A Version Space Algebra
6. Running the Examples
7. Wrap Up

Chapter 4: Deductive Synthesis & Constraint-Based Methods

1. Programs from Proofs: Deductive Synthesis
2. Constraint Solving: SAT and SMT
3. Counter-Example Guided Inductive Synthesis
4. Syntax-Guided Synthesis and Sketches
5. Running the Examples
6. Interpreting the Results
7. Wrap Up
8. Optional Practice Problems

Part III: Neurosymbolic Program Synthesis

Chapter 5: The Neurosymbolic Paradigm

1. Why Deep Learning Alone is Insufficient
2. The Synergy of Neural Networks and Symbolic Search
3. Differentiable Reasoning and Logic
4. Case Study: Compositional Reasoning
5. Synthesis with Learned Proposers
6. Running the Examples
7. Wrap Up

Chapter 6: Neurosymbolic Architectures & Algorithms

1. Logic Tensor Networks (LTN)
2. Logical Neural Networks (LNN)
3. NeurASP: Integrating Answer Set Programming with Neural Networks
4. Differentiable Inductive Logic Programming (∂ILP)
5. Running the Examples
6. Wrap Up

Part IV: Advanced Topics & Applications

Chapter 7: Generalization & Autonomous Skill Acquisition

1. Generalizing Beyond the Training Distribution
2. Compositional Abstractions and Reusable Modules
3. Test-Time Adaptation and Reasoning
4. Program Synthesis for Autonomous Skill Acquisition
5. Running the Examples
6. Wrap Up

Chapter 8: Program Synthesis for Scientific Discovery

1. Automated Hypothesis Generation and Testing
2. Data-Efficient Learning for Scientific Domains
3. Causal and Temporal Reasoning in Synthesis
4. Case Study: Equation Discovery — Kepler’s Third Law
5. From Kepler to FunSearch: Synthesis at Research Scale
6. Running the Examples
7. Wrap Up

Part V: The Road Ahead

Chapter 9: Benchmarks, Evaluation, and the Path to AGI

1. Evaluating General Intelligence: Per-Task Metrics
2. A Key Benchmark: ARC in Miniature
3. ARC in Practice: Versions, the ARC Prize, and Real Scores
4. Compositional Generalization: A SCAN-Style Gap
5. Generalization-Gap Leaderboard
6. Running the Examples
7. Wrap Up

Appendix: Essential Tools & Resources

1. SMT and SAT Solvers
2. Synthesis Systems and Languages
3. Neurosymbolic Frameworks
4. Program Synthesis from Examples
5. Scientific Discovery
6. Benchmarks and Evaluation
7. Key Surveys and Books
8. A Suggested Path