Why Performance in Programming Is Always a Problem
summary
Argues that a universal brute force works if performance is irrelevant: start with zero bits, backtrack through every permutation, increase bit length and use a user-provided solution is valid acceptance function to check candidates. Explains algorithmic tools as backtracking and exhaustive permutation enumeration, gives the concrete (absurd) example of one million bits, and classifies problems into S, P and E programs. Algorithm is correct in theory but practically unusable without infinite time or human validators.
AI-written summary · about
chapters (8)
- 0:00Introduction: Not a Comedy, Not a Documentary
- 0:22The Quicksort vs Bubble Sort Debate
- 1:03What If Performance Didn’t Matter?
- 1:40The Ultimate (Bogus) Algorithm
- 2:19Trying All Bit Permutations
- 3:15The S, P, and E Program Taxonomy
- 4:05Solving P and E Programs with Humans
- 4:28Conclusion: Performance Is Always a Problem
related talks
51mFun with Algorithms
01h 05mA Survey of Automatability
01h 32mPlenary: Six Impossible Things
43m(Programs), Proofs and Refutations (and Tests and Mutants)
51mAlgorithms Demystified
01h 05mVerifying Infinitely Many Programs at Once
52mBehavioral Programming: Aligning Code with How We Think -
26mInfinite Possibilities