AI summary by TwinMind
Are There Problems That Computers Can't Solve?
Tom Scott
7m 58s
Introduction: Computational Impossibility
- Question: Are there problems computers cannot solve even with infinite time, energy, computing power?
- Short answer: Yes
- Example: Old BBC micros where kids could type infinite loops in shop displays
- Programs can halt accidentally (endless loops, freezing)
- Desire: Analyze any code to determine if it will halt or loop forever
- Reality: This is mathematically impossible
Historical Context: Hilbert's Decision Problem
- Early 20th century mathematician David Hilbert posed series of problems
- Decision problem: Can we determine if any given logical statement/problem is provable?
- Question: Given enough time, could we find answer to everything?
- Hilbert was optimistic answer would be yes
- Mathematicians proved him wrong, including Alan Turing
Turing Machines: The Theoretical Foundation
- Turing studied mechanization of logic and computation
- "Computer" was job description for people doing calculations
- Goal: Automate process by encoding everything into numbers
- Turing machine components:
- Infinitely long tape divided into cells (computer memory)
- Read/write head moving left/right over tape
- State register and table of instructions (code)
- Instructions include: move left, move right, change tape contents, read tape
- Machine either halts at end of instructions or enters endless loop
- Minimum possible computer but equivalent to any modern computer
- Any program in any language can be converted to run on Turing machine
The Halting Problem Proof
- Turing restated decision problem: Can we determine if any given program will halt or not?
- Proof by contradiction approach:
Step 1: Assume Solution Exists
- Imagine Turing machine called "halts" that analyzes code
- Input: Code for any program
- Output: "Yes" (program halts) or "No" (loops forever)
Step 2: Create Opposite Machine
- Build new machine that uses "halts" as component
- If "halts" says "yes" (will halt) → new machine loops infinitely
- If "halts" says "no" (will loop) → new machine halts
- Call this combined machine "opposite" (does opposite of prediction)
Step 3: The Paradox
- Feed "opposite" machine's own code into itself
- Logic breakdown:
- If it thinks code will halt → it loops (so code doesn't halt)
- If it thinks code will loop → it halts (so code doesn't loop)
- Creates logical mathematical impossibility/paradox
- Therefore, "halts" program cannot exist
Implications and Limitations
- Proves there's at least one thing computers cannot solve
- Many programs obviously halt or loop (easy to determine)
- Problem isn't about some programs - it's about every program
- Fundamental limitation: some things computers cannot possibly solve
- Blow to mathematicians like Hilbert who believed pure mathematics could solve anything
- Even before first digital computer existed, Turing proved computational limits
