Lecture notes — The Limits of Computation
ver. 1.0.1, limits_of_computation
ver. 1.0.1 · 2026-09-07 05:38 UTC
Where this fits
The previous unit named the answer to Hilbert’s Entscheidungsproblem — no, not every logical assertion is mechanically decidable — without stopping to justify it. This unit takes the question seriously enough to build the vocabulary the answer depends on: what a decision problem is, precisely, and what it would even mean to prove that no algorithm exists for one.
Learning outcomes
distinguish-problems-and-instances— Distinguish a general problem from a specific instance of it, and define a decision problem precisely.explain-informal-decidability— Explain decidability informally: a problem is decidable if you can write a program that always answers it correctly and halts.formalize-a-decision-problem— Express a decision problem in formal logic, and verify a formal definition matches an informal one.state-the-negative-answer— State that the answer to the Entscheidungsproblem is no, and give two examples of why.pose-the-open-question— Pose, without yet answering, what a proof of undecidability actually requires.
Concepts introduced
- Entscheidungsproblem — the question of whether every mathematical statement expressible in formal logic can be algorithmically decided.
- Decision Problem — a problem whose solution is a boolean output, equivalently defined by membership in a set.
- Decidability — the property of a decision problem being solvable by an effective algorithmic procedure.
- Gödel’s Statement — a self-referential logical statement, constructed via Gödel numbering, whose truth cannot be mechanically determined.
- Diophantine Equations — polynomial equations over the integers, whose general solvability is an undecidable decision problem.
Problems, instances, and decision problems
A problem and an instance of it are different things. MULT, the problem “given two numbers \(x\) and \(y\), what is \(x \times y\)?”, is a general question. 67 \times 4.5 = ? is one instance of it, with one particular answer, 301.5. Answering an instance answers nothing about the problem; solving the problem means answering every instance.
A decision problem is a problem whose output is restricted to True or False. Formally, it is a function \(P\) from an instance to a boolean value.
An equivalent, and often easier, formulation uses sets. Define \(A\), the set of all possible inputs, and \(B \subseteq A\), the set of desirable — “yes” — inputs. Then
\[P(x) = (x \in B)\]
This formulation is easier because it reduces the problem to defining a single set, \(B\), rather than a function.
For primality testing: \(A\) is the set of all integers, \(B\) is the set of all prime numbers, and \(P(n)\) is true exactly when \(n\) is prime — \(P(n) = (n \in \text{Primes})\).
Learning outcomes
- distinguish-problems-and-instances Distinguish a general problem from a specific instance of it, and define a decision problem precisely.
Concepts
- decision-problem a function returning a boolean output, equivalently expressed as membership in a set \(B \subseteq A\)
What decidable means, informally
A decision problem’s decidability is, for now, given an informal, working definition:
(Python) Decidability. A decision problem, \(P\), is decidable if it can be implemented in Python.
That is: a decision problem is decidable if there exists a program — Python stands in for any general-purpose language — that, given any instance, correctly computes the boolean answer. Reaching a formal definition would require more machinery: mathematical logic, and a model of computation.
PRIME, defined formally in the next section, is confirmed decidable under this informal notion: it definitely can be implemented in Python.
Learning outcomes
- explain-informal-decidability Explain decidability informally: a problem is decidable if you can write a program that always answers it correctly and halts.
Concepts
- decidability an informal, Python-implementability notion, used before a formal one is available
Formalizing a decision problem
To state a decision problem with mathematical precision, rather than in English, requires a formal logic. This unit works with predicate logic over integer arithmetic, denoted \(L\): the logical connectives AND, OR, NOT; the quantifiers \(\forall\) (for all) and \(\exists\) (exists); variables ranging over the integers; the constants \(0, 1, 2, \ldots\); and integer addition and multiplication.
Using \(L\), define DIV, divisibility, and then PRIME in terms of it:
\[\text{DIV}(x, y) = \exists n.\ x = y \times n\]
\[\text{PRIME}(x) = \lnot\bigl(\exists y.\ \text{DIV}(x, y) \land \lnot(y = 1) \land \lnot(y = x)\bigr)\]
PRIME(x) reads: there is no \(y\), other than \(1\) or \(x\) itself, that divides \(x\). With \(A\) the set of all integers and \(B = \{\, x : \text{PRIME}(x) \,\}\), this is the same decision problem introduced informally in the previous section — now stated precisely enough that its correctness can be checked against the definition rather than against intuition.
Learning outcomes
- formalize-a-decision-problem Express a decision problem in formal logic, and verify a formal definition matches an informal one.
- explain-informal-decidability Explain decidability informally: a problem is decidable if you can write a program that always answers it correctly and halts.
Concepts
- entscheidungsproblem the question this formal vocabulary exists to make precise: can every statement in this kind of logic be decided?
The answer is no
The question can now be asked precisely: are all decision problems expressible in the logic \(L\) Python-decidable? The answer is no.
Two witnesses are given.
- Gödel’s statement. Gödel defined a numbering system assigning a unique integer to every logical statement — true and false alike — then constructed, using a recursive technique on this numbering, a specific logical statement about its own Gödel number. He proved that no computation can ever determine whether this statement is true or false.
- Diophantine equations. No Python program can solve all possible instances of the general Diophantine equation problem — deciding, for an arbitrarily given polynomial equation with integer coefficients, whether an integer solution exists.
Neither witness is proved here from first principles; both are stated as results, at the level of detail this unit’s informal notion of decidability supports.
Learning outcomes
- state-the-negative-answer State that the answer to the Entscheidungsproblem is no, and give two examples of why.
Concepts
- goedels-statement constructed via Gödel numbering and self-reference; no computation determines whether it is true or false
- diophantine-equations no Python program decides solvability for every instance
- entscheidungsproblem answered negatively: not every problem expressible in \(L\) is decidable
What a real proof would require
Having stated the negative answer, the unit closes by naming what has been left open — the questions its own informal treatment cannot yet settle:
- Why are these decision problems Python-undecidable?
- How is a Diophantine equation a decision problem?
- What if a programming language “better” than Python is used?
- Are there other undecidable problems?
- How does one solve an undecidable problem?
The second question is the sharpest one to sit with. “Python-undecidable” was never given a proof — only two named results, taken on report. The third question exposes exactly why: “Python decidable” was defined relative to one particular language, and the informal notion has no way yet to rule out some other language succeeding where Python cannot.
Answering any of these requires replacing “can be implemented in Python” with a precise mathematical object standing in for “algorithm” — one general enough that a claim like “no algorithm exists” can be checked against it, rather than merely asserted.
Learning outcomes
- pose-the-open-question Pose, without yet answering, what a proof of undecidability actually requires.
- state-the-negative-answer State that the answer to the Entscheidungsproblem is no, and give two examples of why.
Conclusion
A decision problem is a boolean function, equivalently membership in a set.
\(P(x) = (x \in B)\). The set formulation is often easier to work with, because it reduces the problem to defining one set rather than a function’s full behaviour.
“Python decidable” is a working definition, not a final one.
It says a program exists that always halts with the right answer, for any general-purpose language Python stands in for. It builds intuition, and it is not yet precise enough to prove a negative result with.
Formalizing PRIME in predicate logic makes it checkable rather than merely plausible.
\(\text{PRIME}(x) = \lnot(\exists y.\ \text{DIV}(x, y) \land \lnot(y=1) \land \lnot(y=x))\) says exactly what “no divisor but 1 and itself” means, in a notation whose correctness can be verified against its own definition.
The Entscheidungsproblem’s answer is no, given here on report rather than by proof.
Gödel’s statement and the general Diophantine equation problem are both named as undecidable, without either result being derived from first principles in this unit.
The unit ends by naming exactly what it has not yet justified.
Five open questions, the source’s own list: why these problems are undecidable, how a Diophantine equation is a decision problem at all, whether a “better” language could decide them, whether other undecidable problems exist, and how one works with an undecidable problem once it is found.
The next two units in this module, Basics of a Turing Machine and Algorithms and the Limits of Computation, are built to resolve the open questions this unit closes with: a precise mathematical model of “algorithm” is exactly the missing ingredient that would let “Python-undecidable” become a proved claim rather than a reported one.
References
- Course material, Ken Pu