From Formal Logic to Computation: The Mathematical Road to AI

The Long Human Road to AI, article 3 of 8

Before a machine could follow a rule, humans had to make rule-following into something you could write down, check, and hand to someone else. That transformation — from reasoning that lived in minds and speech to reasoning on paper, then in circuits — is the thread of this article.

It is not a straight line, and it does not end with an inevitable artificial intelligence. It is a set of bridges. Symbolic notation made reasoning inspectable. Computability made procedure precise. Switching circuits made logic physical. Information theory made signals measurable. Feedback and control gave researchers a language for purposeful machine behavior. Each bridge made later ideas easier to think about; none of them, alone, built the computers or AI systems we know today.

The problem: reasoning is hard to share

Reasoning is fragile when it stays in memory or conversation. A good argument can be forgotten, misquoted, or bent by the teller. One remedy is to write it down as a set of public steps, like a recipe.

Point C1 Algebraic and symbolic treatments of logic helped make reasoning inspectable and manipulable as formal symbol systems.

A recipe turns a cook’s private sequence into steps anyone can follow. Formal notation does something similar for parts of reasoning: it exposes the moves so they can be checked, copied, and taught. In An Investigation of the Laws of Thought (1854), George Boole showed that some logical relations could be treated algebraically. Decades later, Gottlob Frege’s 1879 Begriffsschrift pushed symbolic logic toward modern quantificational logic, though the story of modern logic also includes work by Boole, De Morgan, Schröder, Peirce, Venn, and others.

Where the recipe analogy breaks: A recipe tolerates judgment and variation; a formal system has strict syntax and inference rules, and not every human judgment can be reduced to a formal recipe.

Logic becomes algebra and notation

Boole did not invent the computer, and Frege did not invent AI. Their narrower and more defensible contribution was to make parts of reasoning more formal, inspectable, and manipulable. Alfred North Whitehead and Bertrand Russell’s Principia Mathematica (1910) then became a landmark of the logicist ambition: the idea that mathematics could be built from explicit logical foundations.

This was not the only tradition, and it was not free of limits. But it created a shared language in which rules, propositions, and inferences could be written as symbol manipulations. That language would later help engineers and computer scientists describe what a machine should do.

The dream of a complete formal method

By the early twentieth century, mathematicians such as David Hilbert wanted to put mathematics on firm formal foundations. Hilbert’s 1900 address on mathematical problems, and the later Entscheidungsproblem, asked whether there could be a general decision method for logical validity.

Point C3 The formalist ambition around mathematical foundations and decision procedures created the problem setting in which computability could be made precise.

The dream mattered even when it failed. It focused attention on what a “method” actually is. Once you ask that question precisely, you can also ask which problems have methods and which do not. Hilbert’s 1900 problems are not identical to the later Entscheidungsproblem; the gap between them is part of the real history, not a single compressed slogan.

Limits become discoverable

In 1931, Kurt Gödel published incompleteness results showing that any consistent, effectively axiomatized formal system strong enough for elementary arithmetic has statements it cannot prove or disprove. That is a boundary, not a failure of logic.

Point C4 Gödel’s incompleteness theorems showed that consistent formal systems strong enough for arithmetic have intrinsic limits, complicating the dream of complete formal foundations.

A rulebook can make a game playable and fair, but it may not answer every meaningful question about the game from inside itself. Gödel’s theorems are precise mathematical results about formal systems containing arithmetic, not a vague claim that “logic cannot know everything” or that machines are impossible.

Where the rulebook analogy breaks: Gödel’s theorems are precise mathematical results, not a general claim that every set of rules is incomplete.

A method a machine could imitate

Once “method” became a precise question, several mathematicians answered it at nearly the same time. In 1936 and 1937, Alonzo Church, Alan Turing, and Emil Post gave different but converging formalizations of effective procedure or symbolic process.

Turing imagined an idealized machine that reads and writes symbols on a tape according to fixed rules. Church approached the same territory through functions and substitution in the lambda calculus. Post offered an independent formulation of symbol manipulation. The word “computer” still referred, in part, to human beings carrying out calculations; these models abstracted what it means to follow a rule with symbols, memory, and finite steps.

Point C5 Church, Turing, and Post offered different formalizations of effective procedure, helping turn computation into a mathematical subject before modern computers were common.

Point C6 The Church-Turing thesis concerns effective methods and is often misunderstood when treated as a claim about all physical machines or minds.

The convergence became known as the Church-Turing thesis: anything that can be computed by an effective method can be computed by a Turing machine. The thesis is about effective methods, not about every physical process or every mental capacity.

Where the dance-card analogy breaks: A dance card specifies steps independent of a dancer, but real computers have time, memory, faults, power use, and engineering constraints that computability models set aside.

Switches implement logic

Formal logic stayed on paper until someone showed how to build it. In 1938, Claude Shannon published “A Symbolic Analysis of Relay and Switching Circuits,” applying Boolean algebra to the design of relay and switching circuits. The bridge was direct: an on/off switch could represent a yes/no value, and networks of switches could express more complicated logical conditions.

Point C7 Shannon’s switching-circuit work connected Boolean algebra to relay and switching circuit design, helping make logic part of digital engineering.

This did not mean circuits “thought.” It meant that parts of logical structure could be implemented with physical switching systems. A light switch is a physical yes/no; a network of switches is a physical network of yes/no conditions. Logic gates implement operations; they do not understand propositions.

Where the switch-network analogy breaks: Switches do not have beliefs or reasons; they are engineered electrical behavior that can implement formal operations.

Messages, noise, and feedback

Computation is not only symbol manipulation; it is also transmission, storage, compression, and recovery. In 1948, Shannon published “A Mathematical Theory of Communication,” giving a mathematical treatment of messages, channels, noise, and information. The same year, Norbert Wiener published Cybernetics: Or Control and Communication in the Animal and the Machine, offering a vocabulary of feedback, control, and communication.

Point C8 Shannon’s communication theory provided a mathematical treatment of messages, channels, noise, and information, but it is not a theory of semantic meaning.

Point C9 Cybernetics supplied a language of feedback, control, and communication for thinking about machines and organisms, but feedback alone is not intelligence.

A message sent across a noisy room needs redundancy or correction; so does a signal sent through a channel. A thermostat compares sensed temperature to a target and acts to reduce the difference. Shannon information measures uncertainty and communication capacity, not whether a sentence is wise, true, or meaningful. Feedback control is a pattern of regulation, not intelligence by itself.

Where the noisy-room analogy breaks: Shannon information measures uncertainty and capacity, not whether a sentence is meaningful, true, or important to a person.

Where the thermostat analogy breaks: Feedback control is not intelligence by itself; it is one pattern of regulation that can appear inside larger intelligent or automated systems.

What this made possible, not inevitable

By the middle of the twentieth century, several ideas that once seemed separate had become linkable: formal symbols, effective procedures, switching circuits, information measures, and feedback loops. That linkage made computing and AI more legible. It did not make them inevitable.

The stored-program architecture described in John von Neumann’s 1945 “First Draft of a Report on the EDVAC” shows how formal instructions could be treated as reusable machine data, but the idea has contested attribution and is only a small part of this story.

What still mattered: hardware engineering, programming practice, institutions, funding, labor, data, and culture. The bridges in this article made AI thinkable; the human road to AI also ran through workshops, laboratories, governments, universities, markets, and countless ordinary decisions. The next article, “The Birth of AI,” picks up that road at the 1956 Dartmouth workshop and the first wave of symbolic AI optimism. The previous article, “Before Machines,” looks at the longer prehistory of calculation, automata, and mechanical reasoning.

Technical companion

Same word, different meaning

• Computation once meant human calculation; now it can mean anything from a Turing-machine model to a spreadsheet formula to a neural-network update.
• Information in Shannon’s sense measures uncertainty reduction, not understanding or truth.
• Mechanical can mean “made of gears,” “following fixed rules,” or “without understanding,” depending on the context.
• Intelligence in AI is a contested, moving target; this article does not assume a single definition.