Module 3 · Lesson 1

Computation: Algorithms and the limits of computation, from Euclid's algorithm to Turing

You'll run a 2,300-year-old algorithm that's still in use and see how the idea of a step-by-step procedure was made precise in the 1930s. You'll follow Turing's argument that some questions can't be answered by any computer program, however powerful.

What you will be able to do

Describe what an algorithm is and explain why the halting problem can't be solved by any algorithm.

0% of this lesson · 9 items · 1h 3m total · 48m without the optional activity

Contents of this lesson9 items

ReadingA 2,300-Year-Old Algorithm You Can Run by Hand3 min
ReadingFrom Euclid and al-Khwarizmi to Lovelace and Turing4 min
ReadingWhat Makes Something an Algorithm: Precise, Finite Steps4 min
ReadingTuring Machines: A Precise Definition of Computation4 min
ReadingThe Halting Problem: A Question No Program Can Answer4 min
Guided ReadingWorked Example: The Program That Contradicts Its Own Prediction7 min
Guided ConversationWrite an Algorithm for an Everyday Task12 min
Hands-on Activity · optionalRun Euclid's Algorithm and a Sorting Procedure by Hand15 min
Knowledge CheckAlgorithms and the limits of computation, from Euclid's algorithm to Turing10 min

Report an issue on this page

Reading 3 min Done

A 2,300-Year-Old Algorithm You Can Run by Hand

Here's a task you can try with a pencil. Find the largest whole number that divides both 1071 and 462 with nothing left over. You could list every divisor of each number and compare the lists, but that's slow. There's a faster way, and it has been written down for roughly 2,300 years.

The method appears in Book VII of Euclid's Elements. Euclid taught at Alexandria and lived from about 325 to about 265 BCE, though little else is known about his life (O'Connor and Robertson 1999b). He states the method with subtraction: take the smaller number away from the larger, again and again, then do the same with what's left (Euclid, Elements VII.1). The next proposition uses that procedure to find the greatest common measure of two numbers (Elements VII.2). Subtracting the same number over and over is what division does, so today the method is usually written with division and remainders.

Here is the method in words:

Divide the larger number by the smaller, and keep the remainder.
Replace the larger number with the smaller one, and the smaller one with the remainder.
Repeat until the remainder is 0. The last remainder that wasn't 0 is the answer.

Try it on 1071 and 462 before you look at the working below.

The first division gives $1071 = 2 \times 462 + 147$ . In words, 462 goes into 1071 twice, with 147 left over. The second division gives $462 = 3 \times 147 + 21$ . The third gives $147 = 7 \times 21 + 0$ . The remainder is now 0, so the answer is 21. It took three divisions.

You can check the result. Since $1071 = 21 \times 51$ and $462 = 21 \times 22$ , 21 divides both numbers. And 51 and 22 share no factor larger than 1, so no larger number divides both.

Look at what made the method work. Each step is exact, so there's no judgment call about what to do next. The remainder gets smaller at every step, so the process has to stop. And the same steps work for any two whole numbers, not just these two. A procedure with those features is what mathematicians call an algorithm.

The branch of mathematics that studies computation takes procedures like this as its subject. It asks how to state a procedure precisely and how many steps one takes as the numbers grow. It also asks a stranger question: are there problems that no procedure at all can solve? In 1936, Alan Turing and Alonzo Church each showed that the answer is yes (De Mol 2025, sec. 2.4). Some of those problems are short enough to state in a sentence.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy
Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book VII (Joyce)
O'Connor, J. J., and E. F. Robertson. 1999b. "Euclid of Alexandria." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 1999.
- Free: MacTutor: Euclid

Reading 4 min Done

From Euclid and al-Khwarizmi to Lovelace and Turing

Introduction

People followed step-by-step methods for calculating long before anyone asked exactly what such a method is. When the question was finally made precise, in the 1930s, the answer came with a surprise attached. This reading traces the idea of an algorithm from ancient Greece, through Baghdad and Victorian England, to the work of Alan Turing and Alonzo Church.

Ancient Procedures

An algorithm is a finite list of exact instructions that turns any valid input into an output in a finite number of steps. One of the best-known early examples is in Book VII of Euclid's Elements. It finds the largest number that divides two given numbers, by repeatedly taking the smaller from the larger (Euclid, Elements VII.1–2). Euclid taught at Alexandria and lived from about 325 to about 265 BCE (O'Connor and Robertson 1999b).

Euclid didn't call his method an algorithm. He gave a procedure, a sequence of steps for carrying out a task, and then proved that it does what it claims. The proof matters: it shows the method works for every pair of numbers, not only for the ones someone happened to try. For more than two thousand years, mathematicians wrote down procedures like this without needing a general definition. If you could follow the steps and they worked, that was enough.

A Name From Baghdad

The word "algorithm" comes from a person's name. Muhammad ibn Musa al-Khwarizmi was a scholar at the House of Wisdom in Baghdad in the ninth century. Among his works was a book on the Hindu place-value system of numerals. The Arabic original is lost. It survives in a Latin translation that begins Algoritmi de numero Indorum, roughly "Al-Khwarizmi on the Hindu art of reckoning," and the word "algorithm" grew from that Latin form of his name (O'Connor and Robertson 1999a).

The Latin version differs considerably from the original, and even the Arabic title is unknown (O'Connor and Robertson 1999a). So the word comes to us through a translation of a book whose original is lost, and whose author's name was turned into Latin along the way.

Instructions for a Machine

In the 19th century, Charles Babbage designed the Analytical Engine, a calculating machine meant to be controlled by punched cards, like the cards that controlled the patterns on a Jacquard loom. Ada Lovelace translated a French article about the engine and added her own Notes, about three times as long as the article. The translation and Notes were published in 1843 (O'Connor and Robertson 2002).

In the Notes, Lovelace described how the engine could be programmed and gave what many consider "the first ever computer program" (O'Connor and Robertson 2002). She also suggested that the engine "might act upon other things besides number," such as music, if the relations between pitched sounds could be expressed in its terms. With the Notes, the idea of writing instructions for a general-purpose machine was on paper.

Hilbert's Question and the 1930s Answer

In 1928, the mathematicians Hilbert and Ackermann stated the decision problem, often known by its German name, the Entscheidungsproblem. It asks whether there is a procedure that can decide, for every statement written in the standard formal language of logic, whether that statement can be proved (De Mol 2025, sec. 1.1).

To show that no such procedure exists, you need a precise definition of "procedure." Otherwise there's no way to rule out every possible one. In 1936, Turing gave such a definition with his imagined machines, and he used it to show that the decision problem has no general solution (Turing 1936–37). Church reached the same conclusion independently, with a different definition (De Mol 2025, sec. 2.4). The result went against what Hilbert had hoped to achieve.

Conclusion

Exact procedures are ancient, and the word for them comes from a ninth-century scholar's name. A precise definition of computation arrived only in 1936, and it came with a proof that some well-posed questions have no algorithmic answer. Every later study of what computers can and can't do starts from that definition.

Key Terms

Algorithm: A finite list of exact instructions that turns any valid input into an output in a finite number of steps.
Procedure: A sequence of steps for carrying out a task, which may or may not be exact enough to count as an algorithm.
Analytical Engine: A calculating machine designed by Charles Babbage, meant to be controlled by punched cards, for which Ada Lovelace described how to write programs.
Decision problem: Hilbert and Ackermann's 1928 question of whether one procedure can decide, for every statement in the formal language of logic, whether it can be proved.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy
Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book VII (Joyce)
O'Connor, J. J., and E. F. Robertson. 1999a. "Abu Ja'far Muhammad ibn Musa Al-Khwarizmi." MacTutor History of Mathematics Archive, University of St Andrews. Last updated July 1999.
- Free: MacTutor: Al-Khwarizmi
O'Connor, J. J., and E. F. Robertson. 1999b. "Euclid of Alexandria." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 1999.
- Free: MacTutor: Euclid
O'Connor, J. J., and E. F. Robertson. 2002. "Augusta Ada King, Countess of Lovelace." MacTutor History of Mathematics Archive, University of St Andrews. Last updated August 2002.
- Free: MacTutor: Lovelace
Turing, A. M. 1936–37. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, ser. 2, 42: 230–265.
- Free: None confirmed
- Free companion: De Mol 2025

Reading 4 min Done

What Makes Something an Algorithm: Precise, Finite Steps

Introduction

Cookbooks, assembly instructions, and tax forms all give you steps to follow. Most of them wouldn't meet a mathematician's definition of an algorithm. This reading sets out the four requirements an algorithm has to meet, compares an algorithm with a recipe, and shows how counting steps measures an algorithm's speed.

Four Requirements

An algorithm is a finite list of exact instructions that turns any valid input into an output in a finite number of steps. The input is the data an algorithm starts from, such as two numbers or a stack of cards. The output is the result it produces, such as a single number or the same cards in order. The definition packs in four requirements:

Exact. Each instruction says exactly what to do, so two people following it make the same moves.
Finite. The list of instructions has an end. You can write it down in full.
General. The same instructions work for every valid input, not just one example.
Guaranteed to stop. For every valid input, the process finishes after some number of steps.

When Alan Turing made the idea precise in 1936, he modeled it on a person calculating with paper and pencil and following fixed rules. The account was meant to formalize "human computation," not machine computation (De Mol 2025, sec. 3.1). That's why the requirements leave no room for insight or judgment. A rule-follower with no understanding of the task should still get the right answer.

A Recipe Versus an Algorithm

A recipe looks like an algorithm, but it usually fails the test in a few places. The table compares a typical recipe with Euclid's method for finding the largest number that divides two whole numbers.

Requirement	Typical recipe	Euclid's method
Exact	"Season to taste" and "bake until golden" call for judgment	"Divide and keep the remainder" has one meaning
Finite	Yes, a list of steps	Yes, three short instructions
General	Works for one dish, with some cooks and some ovens	Works for every pair of whole numbers
Guaranteed to stop	Usually, but nothing in the recipe proves it	Yes: the remainder shrinks at every step

The last row matters most to mathematicians. Euclid's method stops because each remainder is smaller than the number before it, and whole numbers can't shrink forever.

Counting Steps

Take a concrete task: sorting, which means putting a collection of items in order. Here's one way to sort five playing cards from lowest to highest. Compare cards in pairs to find the smallest card, and set it aside. Then find the smallest of the remaining cards, and repeat until none are left.

Count the comparisons. Finding the smallest of 5 cards takes 4 comparisons, since each comparison rules out one card. Finding the smallest of the remaining 4 takes 3, then 2, then 1. The total is $4 + 3 + 2 + 1 = 10$ comparisons, whatever order the cards started in.

The same method on 100 cards takes $99 + 98 + \dots + 1$ comparisons. That sum equals 4,950. In general, for $n$ cards, where $n$ stands for the number of cards, the count is

\frac{n(n-1)}{2}.

Check it for 5 cards: $5 \times 4 \div 2 = 10$ .

Step Count as a Measure of Speed

The step count is the number of basic operations an algorithm carries out on a given input, used to measure its speed. For this sorting method, the basic operation is one comparison between two cards. Counting steps instead of timing a computer has an advantage: the count doesn't depend on how fast any particular machine is. Two methods for the same task can be compared on paper.

The count also shows how the work grows. Going from 100 cards to 200 doubles the input, but the comparisons rise from 4,950 to 19,900, about four times as many. When the step count grows roughly like the square of the input size, doubling the input roughly quadruples the work. Knowing how a step count grows tells you whether a method that's fine for 100 items will still be usable for a million.

Conclusion

An algorithm is exact, finite, general, and guaranteed to stop, and a recipe usually isn't. Counting an algorithm's basic steps, and seeing how that count grows with the input, is the standard way to judge how fast it is.

Key Terms

Algorithm: A finite list of exact instructions that turns any valid input into an output in a finite number of steps.
Input: The data an algorithm starts from.
Output: The result an algorithm produces from its input.
Sorting: Putting a collection of items in order.
Step count: The number of basic operations an algorithm carries out on a given input, used to measure its speed.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy

Reading 4 min Done

Turing Machines: A Precise Definition of Computation

Introduction

Every computer you've used, from a phone to a data center, can in principle be described by a device with three parts and no electronics at all. Alan Turing described that device in 1936. This reading explains what a Turing machine is, what Turing's universal machine adds, and why the claim that it captures all computation is called a thesis rather than a theorem. Section numbers in citations refer to the encyclopedia entry listed in the References.

Three Parts

A Turing machine is an imagined device, made of a tape, a read-write head, and a finite table of rules, that carries out a computation one small step at a time. Each part is simple:

The tape. A strip divided into squares, each holding one symbol, such as 0, 1, or a blank. The tape never runs out. That corresponds to an unlimited memory (De Mol 2025, sec. 1.1).
The head. It looks at one square at a time. It can read the symbol there, write a new one, and move one square left or right.
The rule table. The machine is always in one of a finite number of states. Each rule says: if you're in this state and you see this symbol, write this symbol, move this way, and switch to this state.

That's the whole machine. Turing built it from an analysis of a person doing a calculation with pencil and paper, who looks at a few symbols at a time and follows fixed rules (Turing 1936–37; De Mol 2025, sec. 3.1). Turing machines aren't physical devices. They're a mathematical model, used to reason about what can be computed.

One Machine for Every Task

Each Turing machine has its own rule table, so each does one job. Turing's most far-reaching idea was a universal machine: a single Turing machine that, given a written description of any other Turing machine and its input, does whatever that machine would do (De Mol 2025, sec. 2.3). The program and the data sit on the same tape.

This is the idea behind the computers you use. One device runs a word processor, a game, or a spreadsheet, depending on which program it's given. The entry on Turing machines in the Stanford Encyclopedia of Philosophy reports that the universal machine is "by many still considered as the main theoretical model of the modern computer," while warning against crediting the modern computer to Turing alone (De Mol 2025, sec. 5.2). One difference remains: a real computer has finite memory, while the model's tape is endless.

A Thesis, Not a Theorem

A problem or function is computable if some Turing machine can compute it, always stopping with the correct answer. Is that the same as being computable by any step-by-step method at all? The Church–Turing thesis says yes: anything that can be computed by an effective procedure, meaning an exact method a person could follow by rule, can be computed by a Turing machine. Alonzo Church stated an equivalent claim using a different formal system (De Mol 2025, sec. 3.2).

It's called a thesis because it can't be proved. It links an informal idea, an exact method a person could follow, to a precise mathematical definition. A proof needs precise ideas on both sides (De Mol 2025, sec. 3.2). The thesis could in principle be refuted, by an intuitively acceptable method that no Turing machine can carry out. So far, none has been found (De Mol 2025, sec. 3.2). And each of the other definitions of computation proposed in the 1930s, including Church's, was proved to capture exactly the same functions (De Mol 2025, sec. 4).

Why It Matters

The thesis turns questions about "any possible method" into questions about Turing machines, which can be studied with proofs. If you can show that no Turing machine solves a problem, the thesis says no algorithm does. And since a phone or laptop is, apart from its finite memory, a universal machine, such a result applies to every program those devices could ever run.

Conclusion

A Turing machine is a tape, a head, and a finite rule table, and a universal Turing machine can imitate any other. The Church–Turing thesis identifies this model with the informal idea of computation. It remains a thesis, unproved by its nature and unchallenged in practice.

Key Terms

Turing machine: An imagined device, made of a tape, a read-write head, and a finite table of rules, that carries out a computation one small step at a time.
Universal machine: A single Turing machine that, given a description of any other Turing machine and its input, does whatever that machine would do.
Computable: Able to be computed by some Turing machine that always stops with the correct answer.
Church–Turing thesis: The claim that anything computable by an effective procedure can be computed by a Turing machine. It's a thesis, not a theorem, because it links an informal idea to a precise one.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy
Turing, A. M. 1936–37. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, ser. 2, 42: 230–265.
- Free: None confirmed
- Free companion: De Mol 2025

Reading 4 min Done

The Halting Problem: A Question No Program Can Answer

Introduction

You've probably watched a program freeze and wondered whether to wait or give up. It would help to have a tool that could look at any program and say whether it will ever finish. This reading explains why no such tool can exist: the question it asks, the argument that rules it out, and what that limit means in practice.

The Question

The halting problem asks: given any program and any input, will that program eventually stop, or will it run forever? Some cases are easy. A program that counts from 1 to 10 and then stops will halt. A program told to repeat "add 1" with no exit will never halt. The question is whether one method can answer correctly for every program and every input.

Running the program and waiting doesn't settle it. If the program stops, you have your answer. But if it's still running after an hour, or a year, you can't tell whether it's about to stop or never will. A halt-checker would have to predict the outcome without waiting for it.

A problem is undecidable if no algorithm can answer it correctly for every possible input. Alan Turing's 1936 paper proved results of this kind for questions closely related to halting. The halting version is the one usually taught today (De Mol 2025, sec. 2.4).

The Argument in Outline

The proof is a proof by contradiction: you assume the opposite of what you want to prove, then show that the assumption leads to something impossible. Here, you assume a perfect halt-checker exists and see what goes wrong.

Suppose someone has written a program that takes any program and input and always answers correctly, "halts" or "runs forever." Now use it to build a new program that takes a program as its input and does three things:

It asks the checker what that program will do when given its own text as input.
If the checker says "halts," the new program loops forever.
If the checker says "runs forever," the new program stops.

The key move is self-reference: making a program act on a description of itself. Feed the new program its own text. If the checker says it halts, it runs forever. If the checker says it runs forever, it halts. Either way the checker is wrong, which contradicts the assumption that it's always right (De Mol 2025, sec. 2.4). So no perfect halt-checker can exist.

Why It's a Landmark

This isn't a claim that nobody has found a halt-checker yet. It's a proof that none can be written, for any machine that computes the way a Turing machine does, which includes every ordinary computer. More speed or memory doesn't help, because the contradiction doesn't depend on how long the checker runs.

The result doesn't say you can never tell whether a particular program halts. People settle individual cases all the time. What fails is a single method that works for every case.

Results like this also answered a larger question. Turing used his undecidable problems to show that there's no general procedure for deciding which statements of formal logic can be proved. If such a procedure existed, it could be used to answer questions about machines that he had already shown no machine can answer (De Mol 2025, sec. 2.4).

Consequences

The same style of argument extends to other questions about what programs do. Turing himself showed that no machine can decide, for every machine, whether it will ever print a given symbol (De Mol 2025, sec. 2.4). Questions like "will this program ever crash?" or "will this program ever do something harmful?" share the problem. So a perfect bug-finder, or a perfect virus detector that never errs on any program, can't exist. Practical tools are still useful. They accept occasional mistakes, give up on some cases, or check narrower properties.

Conclusion

No algorithm can decide, for every program and input, whether the program halts. The proof assumes a perfect checker and builds a program that defeats it. The result marks a permanent limit on computation, and practical tools for finding bugs and threats are built with that limit in mind.

Key Terms

Halting problem: The question of whether a given program, run on a given input, will eventually stop or run forever.
Undecidable: Describes a problem that no algorithm can answer correctly for every possible input.
Proof by contradiction: A proof that assumes the opposite of what it aims to show and derives something impossible from that assumption.
Self-reference: Making a program, statement, or process act on a description of itself.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy

Guided Reading 7 min Done

Worked Example: The Program That Contradicts Its Own Prediction

Introduction

Some limits on computers come from cost: a task takes too long or needs too much memory. The halting problem is a different kind of limit. It asks whether a given program, run on a given input, will eventually stop or run forever. No program can answer that question correctly for every program and input, and the reason is a short argument you can follow in full. This worked example takes a claimed halt-checker seriously, builds a program from it, and shows step by step why the claim has to be false.

The argument is a proof by contradiction. You assume the thing you want to rule out, follow the assumption carefully, and arrive at something impossible. When that happens, the assumption must be false.

The Problem

Suppose someone announces that they've written a program called HALTS. It takes two inputs: the text of any program, which we'll call P, and an input for it, which we'll call X. HALTS always finishes, and it always answers correctly with one of two words:

"halts," if P, given X, eventually stops
"loops," if P, given X, runs forever

The claim is about every program and every input, not just the ones anyone has tested. Your task is to decide whether such a program could exist.

One fact about programs makes the argument possible. A program is itself a piece of text, so it can be given as input to another program, or even to itself. Programmers do this routinely. A spell-checker can check its own source code, and a compiler, the program that turns code into something a machine runs, can process its own code.

Working It Through

Step 1: Build a new program, CONTRARY, that uses HALTS

If HALTS exists, anyone can use it as a part inside a larger program. Build a new program called CONTRARY. It takes one input, the text of some program P. The first thing CONTRARY does is ask HALTS a question: what will P do when P is given its own text as input? In other words, CONTRARY runs HALTS with P as the program and P again as the input.

Nothing about this step is unusual. Programs call other programs all the time, and P's text is a legal input because it's just text. If HALTS works as claimed, this question always gets an answer in a finite time.

Step 2: Make CONTRARY do the opposite of the prediction

Now give CONTRARY its instructions for each possible answer:

If HALTS answers "halts," CONTRARY goes into an endless loop, for example by repeating "add 1" with no way out.
If HALTS answers "loops," CONTRARY stops at once.

So CONTRARY is built to do the reverse of whatever HALTS predicts about a program run on itself. Every piece of it is ordinary: a call to HALTS, a check of the answer, and either a loop or a stop. If HALTS exists, CONTRARY can be written.

Step 3: Run CONTRARY on itself

Here is the move that makes the argument work. CONTRARY is a program, so it has a text. Give CONTRARY its own text as input.

Follow what happens. CONTRARY receives its own text as P. It asks HALTS what CONTRARY does when given CONTRARY's text as input. That's the very run now under way. HALTS has to predict the very run that's asking it the question. This is self-reference: making a program act on a description of itself.

Step 4: Trace both cases

HALTS always finishes and gives one of two answers, so there are only two cases to check.

Case 1: HALTS answers "halts." Then, by its instructions in Step 2, CONTRARY goes into an endless loop. So CONTRARY, run on itself, never stops. HALTS said it would halt. HALTS was wrong.

Case 2: HALTS answers "loops." Then, by its instructions, CONTRARY stops at once. So CONTRARY, run on itself, does halt. HALTS said it would loop forever. HALTS was wrong again.

There's no third option. HALTS was assumed to give one of the two answers and always be right, yet each answer is wrong in this one case. The run of CONTRARY on itself is a case HALTS can't get right, whatever it says.

Step 5: Conclude that HALTS can't exist

Go back through the chain. If HALTS exists, CONTRARY can be built (Steps 1 and 2). If CONTRARY exists, it can be run on itself (Step 3). And that run makes HALTS give a wrong answer (Step 4). But HALTS was supposed to be right every time. The assumption that HALTS exists leads to a contradiction, so the assumption is false.

Notice that nothing in the argument depended on how HALTS works inside. It could use any method at all. The argument shows that every possible halt-checker fails on at least one program and input. In the language of computability theory, the halting problem is undecidable: no algorithm answers it correctly for every possible input. The argument is close to a popular proof presented in the Stanford Encyclopedia of Philosophy entry on Turing machines, which also notes that Turing's own 1936 results concerned closely related questions (De Mol 2025, sec. 2.4).

Key Considerations

Particular programs versus all programs. The argument doesn't say you can never tell whether a particular program halts. For many programs, you can. A program that counts to 10 and then stops will halt, and people prove facts like this about specific programs every day. What the argument rules out is a single method that gives the right answer for every program and every input. Any checker that works on many programs will still fail, or fail to answer, on some.

The common mistake: thinking faster computers could solve it. It's natural to assume a hard computing problem is a matter of speed, and that a faster machine or more memory would eventually get there. That reasoning doesn't apply here. In the argument, HALTS was allowed to be as fast as you like and still failed. The contradiction comes from what HALTS is asked to do, not from how long it takes. A computer a billion times faster could run HALTS a billion times faster and still be wrong about CONTRARY.

Why "just run it and see" doesn't work. Another tempting idea is to run P on X and watch. If it stops, the answer is "halts." But if it hasn't stopped after an hour, or a year, you still don't know whether it's about to stop or never will. Watching can confirm halting, but it can't confirm looping forever.

Self-reference isn't a trick. Feeding a program its own text can look like cheating. But programs are text, and programs routinely process text, including other programs. The self-referential run is a legitimate input, and a checker that claims to handle every input has to handle it.

Summary

Assume a perfect halt-checker exists. Build a program that does the opposite of whatever the checker predicts about it, and run that program on itself. Both of the checker's possible answers turn out wrong:

If HALTS says CONTRARY, run on itself, will... CONTRARY then... So HALTS was...
halt loops forever wrong
loop forever stops at once wrong
Every answer HALTS can give is wrong, so no program HALTS can exist. The halting problem is undecidable.

If HALTS says CONTRARY, run on itself, will...	CONTRARY then...	So HALTS was...
halt	loops forever	wrong
loop forever	stops at once	wrong

The two rows cover every possible answer, because HALTS was assumed to always finish with "halts" or "loops."
The middle column follows from CONTRARY's instructions in Step 2.
The last column compares the prediction with what happened, and it reads "wrong" in both rows. That's the contradiction.

References

De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Free: Stanford Encyclopedia of Philosophy

Guided Conversation 12 min Done

Write an Algorithm for an Everyday Task

In this conversation, you'll pick a routine task from your own life, write steps for it, and test whether those steps count as an algorithm. You'll count how much work your method takes, and you'll leave with your own explanation of why no algorithm can check every procedure for whether it ever stops.

You'll have this conversation with an AI assistant, using your own account. Choose a button to open a new chat with the prompt already filled in, then press send to start. If the chat opens empty, copy the prompt and paste it in.

Run this conversation in whichever assistant you already use:

Open in Claude Open in ChatGPT

Claude desktop app

To use another LLM, simply copy and paste the prompt into its chat window.

Show the full prompt (it lists misreadings to watch for, so skip it if you would rather come to the conversation fresh)

Guided Conversation: Write an Algorithm for an Everyday Task (about 12 minutes)

Note to the learner: press send to start. Everything below is facilitator guidance for the AI. It lists misconceptions to watch for, so skip it if you'd rather come to the conversation fresh.

Please facilitate a coached problem session with me. I'm an adult who is comfortable with basic high-school algebra but may be rusty or uneasy with math, exploring what the mathematics of computation is and whether to study it further. I'm studying algorithms and the limits of computation, from Euclid's algorithm to Turing. Follow this guidance for the whole conversation.

GOAL
Help me describe what an algorithm is and test whether a procedure meets the definition, using a routine task I choose.

HOW TO RUN THE CONVERSATION
- Ask one question at a time, then wait for my reply. Keep each of your turns under about 120 words.
- Don't lecture. Explain a point only when I need it to continue, then return to my steps.
- Be curious, collegial, and patient. Ask for my approach before any hint, give one hint at a time, and never write my steps for me. Define terms briefly on first use. Welcome disagreement when I give a reason.
- Plain conversation only: don't search the web or create files or documents.
- Aim for about 12 minutes, mostly on topics 1 and 2. If my replies are brief, offer one concrete prompt, such as "What should someone do if the name isn't on the list?", and move on. If I seem uncertain, shorten the conversation to 5-7 minutes. Always reach the final topic.
- Start now. Open with one or two warm sentences: this is a conversation, not a quiz; trying an idea and fixing it matters more than getting it right first time; I can ask you to clarify anything. Then ask me to pick a routine task, such as sorting mail by house number, finding a book on a shelf, or checking whether a name is on a list.

TOPICS, IN ORDER
1. Write the steps. Ask me to write numbered steps anyone could follow for my task, for any pile, shelf, or list. Ask what the input (starting information) and output (result) are. Follow-up: could a stranger with no common sense about the task follow each step exactly?
2. Test the steps. Test them against four requirements with tricky inputs (an empty list, one item, a tie, a missing item, a very long list). Exact: does any step need judgment? Finite: is the list of steps complete? General: does it work for every valid input? Guaranteed to stop: could it ever go on forever? When a test fails, ask me how I'd repair the step.
3. Count the steps. Ask me to pick one basic action, such as one comparison, and count how many my method uses for about 5 items and about 100. Ask how the count grows when the input doubles.
4. Closing. Ask me to explain in my own words why no algorithm could check every possible procedure and say whether it ever stops. If I'm stuck, give one hint: picture a procedure built to do the opposite of whatever the checker predicts about it, run on itself. Help me end with a short explanation or question I can take into running algorithms by hand.

CORRECT METHOD AND ANSWER
- There's no single right algorithm. Any steps that are exact, finite, general (including empty and tied cases), and guaranteed to stop for every valid input count.
- Sound methods: to check a list, look at each name in turn and stop at a match or at the end of the list; to sort, repeatedly find the smallest remaining item and set it aside.
- Counts: checking a list of n names takes at most n looks. Sorting by picking the smallest takes n(n-1)/2 comparisons whatever the starting order: 10 for 5 items, 4,950 for 100. Doubling the input roughly doubles the first count and roughly quadruples the second.
- Closing: suppose a perfect checker existed; build a procedure that asks it about itself and does the opposite; either answer is wrong; so no perfect checker exists. The halting problem is undecidable, a proven limit, not a lack of speed.
- The Church-Turing thesis (anything computable by an exact step-by-step method can be computed by a Turing machine) is a thesis, not a proved theorem.

MISCONCEPTIONS TO CORRECT GENTLY
When one appears, name the accurate version briefly, then return to my steps.
- "A computer can solve any precise problem with enough time": some problems, such as the halting problem, are undecidable.
- "An algorithm is a computer program": algorithms predate computers; Euclid's method is thousands of years old.
- "Turing machines are real machines": a Turing machine is a mathematical model.
- "If I can't find a failing case, it always stops": a guaranteed stop needs a reason, such as something shrinking at every step.

LIMITS
- No code. Keep everything in plain numbered steps.
- Don't write my algorithm or give the closing explanation before I've tried.
- Don't go beyond the halting argument in outline.

TO FINISH
After my closing explanation, close in one short turn:
- Affirm one specific thing I worked out, in my own words where possible.
- Suggest one or two next steps that fit how the conversation went. Possible steps: run Euclid's method by hand on 1071 and 462; sort five cards by picking the smallest and count the comparisons; repair one more tricky input; review why a guaranteed stop needs a reason.
- Restate my explanation or question on its own line, labeled "My takeaway", so I can copy it.

Hands-on Activity 15 minOptional Done

Run Euclid's Algorithm and a Sorting Procedure by Hand

Overview

This optional activity has you carry out two algorithms yourself, with pencil and paper. You'll find the greatest common divisor of two numbers with Euclid's method, then sort five cards by repeatedly picking the smallest, counting every comparison. Running an algorithm by hand is the quickest way to see what "exact steps" and "step count" mean.

What You'll Need

Paper and a pen
Five playing cards, or five slips of paper with a different number on each

Your Task

Find the greatest common divisor, the largest whole number that divides both numbers with nothing left over, of 1071 and 462 and of a pair you choose. Then sort five cards from lowest to highest and count the comparisons it takes.

Steps

Find the greatest common divisor of 1071 and 462. Divide the larger number by the smaller and write down the remainder. Replace the larger number with the smaller one, and the smaller one with the remainder. Repeat until the remainder is 0. The last remainder that wasn't 0 is the answer. Count how many divisions you did.
Try a second pair of your own. Pick two whole numbers, ideally three digits each, and run the same steps. Check your answer by dividing both original numbers by it.
Sort five cards by picking the smallest. Shuffle the cards and lay them in a row. Compare cards two at a time to find the smallest, and set it aside. Then find the smallest of the cards that remain, and repeat until none are left. Make a tally mark every time you compare two cards.
Count your comparisons and compare with 10. Add up your tally marks. If your total isn't 10, check whether you skipped a comparison or compared a card with one already set aside.
Estimate the count for 20 cards. Don't sort 20 cards. Instead, work out how many comparisons finding the smallest takes at each round, and add them up.

What to Expect

For 1071 and 462, the three divisions are $1071 = 2 \times 462 + 147$ , then $462 = 3 \times 147 + 21$ , then $147 = 7 \times 21 + 0$ . The answer is 21. For your own pair, the answer divides both numbers exactly. If the answer is 1, your numbers share no common factor larger than 1, which is a correct result too.

Sorting five cards this way always takes 10 comparisons, whatever order the cards started in: 4 to find the smallest of five, then 3, 2, and 1. For 20 cards, the rounds take 19, 18, and so on down to 1 comparison, for a total of 190. In general, $n$ cards take $n(n-1)/2$ comparisons, where $n$ is the number of cards. Going from 5 cards to 20 multiplies the cards by 4 but the comparisons by 19. Adding cards adds rounds and also makes every round longer.

Self-Check

When you're done, check that:

Your first answer is 21, reached in three divisions
Your second answer divides both of your chosen numbers exactly
Your sort of five cards made 10 comparisons
Your estimate for 20 cards is 190 comparisons
You can say in a sentence why the comparison count grows faster than the number of cards

Nothing is uploaded. Write in your own notebook or document and keep it.

Knowledge Check 10 min Done

Algorithms and the limits of computation, from Euclid's algorithm to Turing

This ungraded knowledge check assesses your understanding of what an algorithm is and what no algorithm can do. You'll be asked about the history of algorithms, the requirements an algorithm must meet, Turing machines and the Church–Turing thesis, and the halting problem.

Note: Use this to test yourself, review the feedback on any questions you miss, and retry until you feel confident before moving forward.

5 questions · ungraded · retry as often as you like