Deliverable Overview
You'll write one explainer, 600 to 900 words long, for a reader with no background in mathematics or computer science. Picture a friend who has read a headline claiming that AI will soon solve any problem it's given. Your explainer gives that friend one precise reason to be careful, without swinging to the opposite mistake of claiming that computers can't do mathematics at all.
The explainer has six required components:
- The limit, stated in plain words
- Its status: proved, or believed and unproved
- The core idea of why it holds or is believed, as a short argument or example
- One real system where the limit matters
- One common misunderstanding, corrected
- At least two sources
Short headings for each component make the explainer easier to follow. Citations are required here, since the explainer must cite at least two sources. Give the author, year, title, and where to find each one, for example: Raatikainen, 2025, "Gödel's Incompleteness Theorems," Stanford Encyclopedia of Philosophy (free online).
Detailed Requirements
The Limit, in Plain Words
State the limit in one sentence a non-specialist can follow. Four limits fit well:
| Limit | One plain-sentence version |
|---|
| Undecidability of the halting problem | No algorithm can decide, for every program and input, whether the program will eventually stop |
| Incompleteness | Any consistent set of rules strong enough for basic arithmetic leaves some statements it can neither prove nor disprove |
| Combinatorial explosion | For many problems, the number of possible answers grows so fast that checking them all one by one is out of reach |
| P versus NP | Many problems whose answers are quick to check appear to have no quick way to find the answers |
You may choose another limit if you can justify it as a real limit on reasoning or computation. An algorithm here means a finite list of precise steps that any person or machine could follow. Whatever you choose, keep the sentence exact. "Computers can't predict programs" is too loose; the halting result is about a single method that works for every program.
Its Status: Proved or Believed
Say whether the limit is a theorem or a belief, and say so plainly. The halting problem's undecidability is proved. It goes back to Alan Turing's work of 1936–37, which showed that a closely related question, the decision problem in logic, has no algorithmic answer; Alonzo Church reached the same result independently (De Mol 2025, sec. 2.4). Gödel's incompleteness theorems are proved (Raatikainen 2025, sec. 1.1). The growth in the number of possible answers is a matter of counting, so it is proved too, but it rules out only checking every answer, not cleverer methods.
P versus NP is different. P is the class of problems an algorithm can solve in a number of steps that grows no faster than a fixed power of the input size. NP is the class of problems whose proposed answers can be checked that quickly. Whether the two classes are the same is unsolved (Clay Mathematics Institute n.d.-a). Most complexity theorists believe they differ, but no one has proved it (Cook n.d., sec. 3).
The Core Idea
Give the reason the limit holds, or the reason experts believe it, in a short argument or a worked example. You don't need a full proof. You need the one move that makes the limit make sense.
For the halting problem, the core idea is a self-referring program. Suppose a perfect halting checker existed. Build a new program that asks the checker about itself and then does the opposite of whatever the checker predicts. Either answer the checker gives turns out wrong, so no perfect checker can exist (De Mol 2025, sec. 2.4.3).
For combinatorial explosion, a count makes the point. A tour that visits n cities once and returns home can be drawn in (n-1)!/2 different ways, where n! ("n factorial") means n \times (n-1) \times \dots \times 2 \times 1. Four cities give 3 tours. Ten cities give 181,440. Twenty cities give about 6 \times 10^{16}, which is 60 million billion. Checking one tour stays easy as n grows; listing them all does not.
One Real System
Connect the limit to one system or practice your reader has met, and say what the limit means there. Software testing, encryption, scheduling, route planning, and AI are all good candidates.
Be specific about the link. Much of internet security depends on assumptions that certain problems, such as factoring very large numbers, are hard (Cook n.d., sec. 2). A tool that hunts for programs that never stop can work on many programs, but the halting result says no such tool can be right about every program. A delivery company's route planner faces the explosion in the number of tours, which is why such planners settle for very good routes rather than proven best ones.
One Misunderstanding, Corrected
Name one thing people commonly get wrong about your limit, then correct it in a sentence or two. Gödel's theorems are a rich source. A formal system is a fixed set of starting statements and rules for deriving new ones. The first theorem is about what a particular formal system can derive, not about truths that can't be proved by any means (Raatikainen 2025, sec. 1.1). Arguments that the theorems prove human minds outperform every machine are widely regarded as failing (Raatikainen 2025, sec. 6.3).
At Least Two Sources
Cite at least two sources a reader could find. Free reference works, such as the Stanford Encyclopedia of Philosophy or the Clay Mathematics Institute's problem pages, are good choices. Cite each where you use it, and list them at the end.
Success Criteria
Your explainer meets the requirements when:
- The limit is stated in one plain sentence
- Its status, proved or believed, is stated correctly
- The core idea is given as an argument or example
- One real system is connected, with what the limit means there
- One misunderstanding is corrected
- Terms are defined on first use, and at least two sources are cited
Step-by-Step Guidance
Step 1: Choose a limit and state it in one plain sentence. Pick the limit you understand best, not the most impressive one. Write the sentence, then read it to someone, or to yourself out loud, and cut any word a non-specialist wouldn't know.
Step 2: Find out its status: proved, or believed. Look the limit up in a reference work and find the sentence that settles its status. Note who proved it and when, or note that it's still open. Write the status into your draft as a separate sentence so it can't be missed.
Step 3: Write the core idea as a short argument or example. Choose either the self-referring trick, a count, or a check-versus-find contrast. Work any numbers yourself before you put them in the draft.
Step 4: Connect it to one real system and say what it means there. Ask what the people who build that system do differently because of the limit. A security engineer relies on a belief; a tool builder accepts that some answers will be "don't know"; a route planner accepts good-enough routes.
Step 5: Identify a common misunderstanding and correct it. The headline your friend read is one candidate. Another is the reverse claim that computers can't do mathematics. State the misunderstanding fairly before you correct it.
Step 6: Draft for a reader with no background. Define each term the first time you use it, including algorithm, formal system, and any class names such as P and NP. Cite at least two sources. Then cut until you're inside 600 to 900 words.
Resources
Common Pitfalls
- Treating a belief as a proof. "P is not equal to NP" is a widely held belief, not a theorem. Write "most experts believe," and say that the question is open.
- Overstating a limit. "Computers can't do math" is false. Computers check proofs and help find them every day. Each limit rules out one specific thing, such as a single method that works on every case, and nothing more.
- Stating the limit without saying why it holds. A limit with no reason attached reads as an opinion. Give the self-referring program, the count, or the gap between checking and finding.
- Picking a real system where the limit doesn't apply. Make sure the link is real. A proof that P differs from NP, for example, would not by itself show that any particular code is safe, because codes rest on specific problems such as factoring, and factoring isn't known to be among the hardest problems in NP (Cook n.d., sec. 2). Incompleteness concerns formal systems for arithmetic; it says nothing direct about a chatbot's accuracy.
References
- Clay Mathematics Institute. n.d.-a. "P vs NP." Millennium Prize Problems. Accessed October 13, 2026.
- Cook, Stephen. n.d. "The P Versus NP Problem." Official problem description, Millennium Prize Problems. Clay Mathematics Institute. Accessed October 13, 2026.
- De Mol, Liesbeth. 2025. "Turing Machines." Stanford Encyclopedia of Philosophy. First published 2018; substantive revision May 21, 2025.
- Raatikainen, Panu. 2025. "Gödel's Incompleteness Theorems." Stanford Encyclopedia of Philosophy. First published 2013; substantive revision October 8, 2025.