The Limits of Computation

Computation and Turing Machines · v1.0.1

2026-09-07 02:23:35

Where we are

Where this fits

  • The previous unit named the answer to Hilbert’s Entscheidungsproblem: No
  • Not every logical assertion is mechanically decidable
  • That answer was stated without justification
  • This unit builds the vocabulary the justification depends on

Outline of key topics

  • Problems, instances, and the decision problem
  • An informal notion of decidability
  • Formalizing a decision problem in predicate logic
  • The negative answer, with two examples
  • What a proof of undecidability requires

Problems, instances, and decision problems

Problem versus instance

Problem. MULT

Given two numbers \(x\) and \(y\), what is \(x \times y\)?

Instance. One case of MULT

\(67 \times 4.5 = 301.5\)

An algorithm answers every instance. One instance answers nothing about the problem.

The decision problem, as a function

A decision problem restricts the output to True or False.

\[P : \text{instance} \to \{\text{True}, \text{False}\}\]

A decision problem as a function with boolean output.
  • an instance goes in
  • a boolean value comes out
  • \(P\) names the problem itself

The decision problem, as set membership

\[P(x) = (x \in B)\]

  • \(A\): the set of all possible inputs
  • \(B \subseteq A\): the set of desirable — “yes” — inputs

Reduces a problem’s definition to defining one set, \(B\).

Primality as a decision problem

  • \(A\) = the set of all integers
  • \(B\) = the set of all prime numbers
  • \(P(n) = (n \in \text{Primes})\)

What decidable means, informally

Python decidability

A decision problem, \(P\), is decidable if it can be implemented in Python.

  • Python stands in for any general-purpose language
  • the program must halt on every instance
  • the program must compute the correct boolean answer

Scope of the informal notion

Reaching a formal definition requires more machinery:

  • mathematical logic
  • a model of computation

PRIME, formalized in the next section, is decidable under this notion.

Formalizing a decision problem

Predicate logic over integers

Denoted \(L\):

  • connectives: AND, OR, NOT
  • quantifiers: \(\forall\) (for all), \(\exists\) (exists)
  • variables ranging over the integers
  • constants: \(0, 1, 2, \ldots\)
  • integer addition and multiplication

Defining DIV

\[\text{DIV}(x, y) = \exists n.\ x = y \times n\]

\(x\) is divisible by \(y\): some integer \(n\) satisfies \(x = y \times n\).

Defining PRIME

\[\text{PRIME}(x) = \lnot\bigl(\exists y.\ \text{DIV}(x, y) \land \lnot(y = 1) \land \lnot(y = x)\bigr)\]

No \(y\), other than \(1\) or \(x\) itself, divides \(x\).

Checking the formalization

\[A = \mathbb{Z}, \quad B = \{\, x : \text{PRIME}(x) \,\}\]

The same decision problem stated informally earlier, now precise enough to check against its own definition.

The answer is no

The question, precisely

Are all decision problems expressible in \(L\) Python-decidable?

No.

Example 1: Gödel’s statement

  • a numbering system assigning a unique integer to every logical statement
  • a specific logical statement constructed about its own Gödel number
  • no computation can ever determine whether that statement is true or false

Example 2: Diophantine equations

  • a polynomial equation with integer coefficients
  • the question: does an integer solution exist?
  • no Python program solves all possible instances

Scope of the two examples

  • neither example is proved here from first principles
  • both are stated as results
  • both are given at the level of detail the informal notion of decidability supports

What a real proof would require

Five open questions

  1. Why are these decision problems Python-undecidable?
  2. How is a Diophantine equation a decision problem?
  3. What if a programming language “better” than Python is used?
  4. Are there other undecidable problems?
  5. How does one solve an undecidable problem?

The language-dependence question

Question 3 exposes the gap directly.

  • “Python decidable” is defined relative to one particular language
  • the informal notion has no way to rule out another language succeeding where Python cannot

Requirement for a proof

Answering any of the five questions requires:

  • replacing “can be implemented in Python” with a precise mathematical object standing in for algorithm
  • a mathematical model of computation general enough that “no algorithm exists” can be checked, and the result applies to every programming language

Summary

Summary

  • A decision problem is a boolean function, equivalently membership in a set
  • “Python decidable” is a working definition, not a final one
  • Formalizing PRIME makes it checkable against its own definition
  • The Entscheidungsproblem’s answer is no — stated here, not proved
  • Five open questions close the unit, naming what has not yet been justified

Where next

Basics of a Turing Machine, the next unit in this module.

  • builds the precise model of algorithm this unit leaves undefined
  • resolves the open questions this unit closes with