Course contentsShow
← Computer Science
Lesson 1860 of 2,87242. Turing Machines and ComputabilityFree lesson

The Quest for a Formal Definition of Algorithm

Understanding why mathematicians sought a precise definition of 'effective computability' in the 1930s.

The Quest for a Formal Definition of Algorithm

What You'll Learn

You'll understand why mathematicians in the 1930s needed to precisely define what it means for a problem to be "solvable by algorithm."

The Problem That Started It All

By the early 20th century, mathematicians used the word "algorithm" informally—they meant a "step-by-step procedure" or "mechanical process" that could solve a problem. But here's the catch: no one had defined exactly what "mechanical" or "effective" meant.

This vagueness created serious problems. Mathematicians were asking fundamental questions like:

  • Can every mathematical statement be proven or disproven?
  • Is there an algorithm to solve any mathematical problem?
  • How do we prove that no algorithm exists for certain problems?

You can't answer "Does an algorithm exist for X?" if you don't know precisely what "algorithm" means!

Why Vagueness Was Unacceptable

Think of it like debating whether a recipe is "easy to follow" without defining "easy." Everyone has different intuitions. In mathematics, intuition isn't enough—you need rigorous definitions.

David Hilbert's famous Entscheidungsproblem (decision problem) asked: "Is there an algorithm to determine whether any mathematical statement is true?" To answer this, mathematicians first needed to formalize what an algorithm is.

This quest led to multiple independent approaches in the 1930s:

  • Turing's Turing machines (which you've just learned!)
  • Church's lambda calculus
  • Gödel's recursive functions

Remarkably, all three turned out to define the same class of computable problems—strong evidence they captured the "true" notion of effective computability.

Key Takeaway: The 1930s quest for a formal definition of "algorithm" wasn't philosophical nit-picking—it was essential for proving what computers can and cannot do, leading directly to the Turing machine model you're now studying.