## Thinking as Computation

by Levesque

### Instructor Requests

This book guides students through an exploration of the idea that thinking might be understood as a form of computation. Students make the connection between thinking and computing by learning to write computer programs for a variety of tasks that require thought, including solving puzzles, understanding natural language, recognizing objects in visual scenes, planning courses of action, and playing strategic games. The material is presented with minimal technicalities and is accessible to undergraduate students with no specialized knowledge or technical background beyond high school mathematics. Students use Prolog (without having to learn algorithms: “Prolog without tears!”), learning to express what they need as a Prolog program and letting Prolog search for answers.

After an introduction to the basic concepts, Thinking as Computation offers three chapters on Prolog, covering back-chaining, programs and queries, and how to write the sorts of Prolog programs used in the book. The book follows this with case studies of tasks that appear to require thought, then looks beyond Prolog to consider learning, explaining, and propositional reasoning. Most of the chapters conclude with short bibliographic notes and exercises. The book is based on a popular course at the University of Toronto and can be used in a variety of classroom contexts, by students ranging from first-year liberal arts undergraduates to more technically advanced computer science students.

Expand/Collapse All
Contents (pg. vii)
Preface (pg. xiii)
Background (pg. xiii)
Overview of the book (pg. xvi)
Guide for the course instructor (pg. xvii)
Guide for the student (pg. xix)
Acknowledgments (pg. xxi)
Chapter 1. Thinking and Computation (pg. 1)
1.1 Thinking (pg. 2)
1.2 Computation (pg. 4)
1.3 Thinking as computation (pg. 11)
Want to read more? (pg. 20)
Exercise (pg. 21)
Chapter 2. A Procedure for Thinking (pg. 23)
2.1 Atomic and conditional sentences (pg. 23)
2.2 Logical entailment (pg. 24)
2.3 Back-chaining (pg. 27)
2.4 Variables in queries (pg. 31)
2.5 Why is back-chaining good? (pg. 36)
Want to read more? (pg. 38)
Exercises (pg. 39)
Chapter 3. The Prolog Language (pg. 41)
3.1 Prolog programs (pg. 42)
3.2 Prolog queries (pg. 45)
3.3 Prolog back-chaining (pg. 55)
Want to read more? (pg. 61)
Exercises (pg. 61)
Chapter 4. Writing Prolog Programs (pg. 63)
4.1 The truth in Prolog (pg. 63)
4.2 A blocks world (pg. 66)
4.3 Recursion in Prolog (pg. 68)
∗ 4.4 Mathematical induction (pg. 69)
4.5 Nonterminating programs (pg. 72)
4.6 A more complex predicate (pg. 75)
4.7 Efficiency in Prolog (pg. 78)
Want to read more? (pg. 81)
Exercises (pg. 82)
Chapter 5. Case Study: Satisfying Constraints (pg. 85)
5.1 Constraint satisfaction problems (pg. 86)
5.2 A first example: Sudoku (pg. 91)
5.3 A second example: Cryptarithmetic (pg. 96)
∗ 5.4 A third example: The eight queens (pg. 103)
5.5 A fourth example: Logic problems (pg. 107)
∗ 5.6 A fifth example: Scheduling (pg. 112)
Want to read more? (pg. 114)
Exercises (pg. 115)
Chapter ∗ 6. Case Study: Interpreting Visual Scenes (pg. 119)
6.1 The thinking part of vision (pg. 119)
6.2 Aerial sketch maps (pg. 121)
6.3 Polyhedral objects (pg. 124)
6.4 Object recognition (pg. 130)
Want to read more? (pg. 135)
Chapter 7. Lists in Prolog (pg. 137)
7.1 Lists (pg. 137)
7.2 Writing programs that use lists (pg. 140)
7.3 Using the member and append predicates (pg. 145)
Want to read more? (pg. 150)
Exercises (pg. 150)
Chapter 8. Case Study: Understanding Natural Language (pg. 153)
8.1 Analyzing the syntax of a language (pg. 154)
8.2 Interpreting noun phrases (pg. Cover)
8.3 Interpreting sentences (pg. 170)
8.4 Nonreferential noun phrases (pg. 174)
Want to read more? (pg. 175)
Exercises (pg. 176)
Chapter 9. Case Study: Planning Courses of Action (pg. 179)
9.1 Planning problems (pg. 180)
9.2 Generating plans (pg. 183)
9.3 Scaling up: The search problem (pg. 191)
9.4 Scaling up: The representation problem (pg. 197)
Want to read more? (pg. 204)
Exercises (pg. 205)
Chapter 10. Case Study: Playing Strategic Games (pg. 209)
10.1 Games as problems (pg. 210)
10.2 Finding the best move (pg. 212)
10.3 Playing bigger games (pg. 226)
Want to read more? (pg. 233)
Exercises (pg. 234)
Chapter ∗ 11 Case Study: Other Ways of Thinking (pg. 239)
11.1 Back-chaining as subject matter (pg. 241)
11.2 Explanation (pg. 249)
11.3 Learning (pg. 253)
11.4 Propositional reasoning (pg. 258)
Want to read more? (pg. 265)
Chapter 12. Can Computers Really Think? (pg. 267)
12.1 What computers can do (pg. 268)
12.2 The Turing Test (pg. 270)
12.4 The Summation Room (pg. 272)
12.5 A final word (pg. 273)
Want to read more? (pg. 274)
12.3 The Chinese Room (pg. 271)
Appendix A. Some Computer Basics (pg. 275)
A.1 Working with computer files (pg. 275)
A.2 Files available online (pg. 276)
Appendix B. Getting Started with SWI-Prolog (pg. 279)
B.1 Installing SWI-Prolog (pg. 279)
B.2 How to load SWI-Prolog programs (pg. 280)
Appendix C. Getting Your Prolog Programs to Work (pg. 283)
C.1 Getting program files to load (pg. 283)
C.2 Getting the right answers from queries (pg. 285)
C.3 Saving a record of program execution (pg. 287)
Appendix D. Other Prolog Systems (pg. 289)
References (pg. 291)
Index of Technical Terms (pg. 297)

#### Hector J. Levesque

Hector J. Levesque is Professor Emeritus in the Department of Computer Science at the University of Toronto. He is the author of The Logic of Knowledge Bases and Thinking as Computation: A First Course (both published by the MIT Press).

 eTextbook Go paperless today! Available online anytime, nothing to download or install. 4 months / \$27.50 12 months / \$38.50