Sign up for Big Think Books

A dedicated space for exploring the books and ideas that shape our world.

Adapted from The Shortest History of AI by Toby Walsh. Published by The Experiment. Copyright © 2025. All rights reserved.

Given the role symbols play in representing concepts in the wider world, a fundamental question for AI is straightforward. How do we manipulate symbols in meaningful ways? This naturally brings us to one of the six ideas central to AI today. It’s an idea for manipulating symbols, and it is ridiculously simple: You can reduce many problems to searching for an answer.

This sounds not just simple but self-­evident, so let me make it a little more complex. You can reduce many problems in AI to the computer searching its internal representation of the world from the symbol representing the starting state to the symbol representing the goal state.

This is not a new idea. It’s called navigation. You search a map for the route from your starting position to your desired end position. We do this all the time. Using a map of the London Underground to get from Bond St. to Kings Cross, you might take the Central Line from Bond St. to Oxford Circus, transfer onto the Victoria Line and go to Warren St, then Euston, before arriving at Kings Cross. The only difference is that rather than search the map for a route ourselves, a computer can do it. In fact, there’s a specialized AI algorithm that intelligently searches a map and efficiently finds such routes. This algorithm is so famous it has a name: A* search. Leaving Bond St., it doesn’t go west to Marble Arch but east to Oxford Circus as this takes you nearer to the final destination, Kings Cross.

A* search was invented in 1968 to navigate a robot called Shakey. Shakey was, as the name suggests, a rather shaky robot built at the Stanford Research Institute in Menlo Park, California. It was the first attempt to build a fully fledged robot like you see in the movies — a robot with a camera to see the world, a microphone to hear commands, wheels and motors to move about, and an onboard computer to make decisions. Shakey was admitted into the Carnegie Mellon University’s Robot Hall of Fame in 2004, alongside some more well-­known but fictional robots such as HAL 9000, R2-­D2, C-­3PO, and Robby the Robot.

Shakey’s computer had a digital map of its world. You could ask Shakey to do a task — Shakey, please go to the library and collect a book — and the robot would explore its digital map with A* search, looking for the route from the symbol representing its current position to the symbol representing the library. Shakey’s motors would then follow this route, using its camera, range-finder sensors, and bump detectors to monitor its progress toward the goal.

Unlike humans, who aren’t always very good at finding their way, A* search is mathematically perfect. What do I mean by that? First, it is complete. If there is a route from A to B, A* search will find it. Second, it is optimal. The route that A* search finds is the shortest possible route from A to B. And third, it is as efficient as possible. That is, in finding this shortest route from A to B, A* search explores as little of the map as it can. You cannot find the route using less search! It won’t consider going to Marble Arch when going from Bond St. to Kings Cross.

Before you dismiss A* search as an interesting little anecdote in the history of AI, you should know that it is likely one of the most common examples of AI in your life today. Every time you get directions on your phone or from your car’s GPS, there’s a little AI program using A* search that finds the shortest route, taking into account the current traffic conditions, road closures, and schedule information. The irony, of course, is that while A* search was originally designed to direct robots, it has now been repurposed to direct humans. I don’t know about you, but that’s been a great improvement to my life. I spend a lot less time being lost and a lot more time getting to my destination nearly on time.

Shakey, the first mobile robot that could make decisions about how to move around its surroundings. (Credit: SRI International / Wikimedia Commons)

This simple idea, of searching for an answer, can be taken up a level — to much, much bigger maps, and to much harder problems than navigation, such as solving a complex puzzle or proving difficult mathematical theorems.

Take the 8-­puzzle, a childhood favorite game of eight sliding tiles in a three-by-three grid. The goal is to get the eight tiles into numerical order. We can turn this into a search problem that A* search can solve. Locations in this search problem are states of the 8-­puzzle. And two states are adjacent to each other if sliding one tile takes us from one to the other. Solving the 8-­puzzle thus requires us to find a path from our starting state to the end state, with the tiles in numerical order.

In the starting state at the top of the illustrated search tree, the blank square is in the middle of the bottom row. In the first move, the number six in the middle square is moved down, creating a blank square in the middle. Similarly, in the second move, the number eight from the top row is moved down, creating a blank square in the middle of the top row. The next two moves rotate this blank square counterclockwise. Finally, the number eight is moved leftward from the middle, taking us to the goal state, in which the numbers occur in sequence around the blank middle square.

A snippet of the search problem solving the 8-puzzle. (Credit: Timothy Colburn / University of Minnesota)

In a robot like Shakey, the map is explicit. Every location is represented with a specific symbol, and there are links in this map connecting locations that are adjacent in the real world. What if we instead represent locations implicitly? We can then search even infinite maps.

Two early AI pioneers, Allen Newell and Herbert Simon, demonstrated these ideas at the 1956 Dartmouth workshop by means of their Logic Theorist program. Newell was at the RAND Corporation at the time, but moved to Carnegie Mellon University (then the Carnegie Institute of Technology) in 1961 to continue his collaboration with Simon, a professor of industrial administration. Simon was a true interdisciplinary genius. He went on to win the Nobel Prize in Economics in 1978. His research interests spanned the fields of cognitive science, computer science, public administration, management, and political science. But the underlying thread in all his research was an attempt to understand human decision-­making scientifically. In 1947, he wrote:

“The human being striving for rationality and restricted within the limits of his knowledge has developed some working procedures that partially overcome these difficulties. These procedures consist in assuming that he can isolate from the rest of the world a closed system containing a limited number of variables and a limited range of consequences.”

Simon and Newell set about describing such “working procedures” in computer programs such as the Logic Theorist.

The Logic Theorist is often called the “first AI program.” Except it wasn’t. There was a checkers program written by Arthur Samuel in 1952, and Turochamp, a chess program written by Alan Turing and his friend David Champernowne in 1948. The Logic Theorist was, however, the first AI program designed to prove mathematical theorems and to demonstrate the power of reasoning with symbols. In fact, the Logic Theorist proved 38 of the first 52 theorems in a famous mathematical text, Alfred Whitehead and Bertrand Russell’s Principia Mathematica.

Principia Mathematica attempts to lay out a formal foundation for all of mathematics. It contains proofs of some fundamental mathematical truths, such as the modus tollens law. This tells us that if P being true implies Q being true, then Q being false implies P also must be false. If winning the lottery implies you are happy, then the fact that you are unhappy means you can’t have won the lottery. This logical argument can be traced back from before the introduction of Powerball to at least Theophrastus, a member of Aristotle’s peripatetic school in the 3rd century BCE.

The Logic Theorist didn’t just prove theorems from Principia Mathematica like modus tollens; it actually found new — and, in a few cases, shorter — proofs for some of these theorems. The Logic Theorist therefore literally rewrote the foundations of mathematics, just as Whitehead and Russell had themselves set out to do in writing Principia Mathematicia. The Logic Theor­ist searched for new mathematical truths by starting from basic axioms and previously derived facts, deriving new mathematical truths from them until it (hopefully) found the target proposition. It thus navigated the infinite map of mathematical truths, searching for new ones.

The Logic Theorist was groundbreaking. It was an artificial mathematician. Who could have imagined in 1956, at the very start of the quest to build artificial intelligence, that a machine could already prove mathematical theorems? Pamela McCorduck, one of the first historians of AI, wrote that the Logic Theorist was “proof positive that a machine could perform tasks heretofore considered intelligent, creative and uniquely human.” Herb Simon made even grander claims for his creation: “[We] invented a computer program capable of thinking non-­numerically, and thereby solved the venerable mind-body problem, explaining how a system composed of matter can have the properties of mind.”

There’s a lot more to “thinking” than proving simple logical propositions, and a lot more to solving the “mind-body problem” than this. Nevertheless, the Logic Theorist was indeed a major milestone in the development of AI, and perhaps even of our understanding of intelligence in general. For the first time, a machine was able to do what only intelligent humans had previously done. A machine could prove difficult mathematical theorems.

Sign up for Big Think Books

A dedicated space for exploring the books and ideas that shape our world.