Towards a Theory of Bugs: The Ruliology of the Unexpected
13 hours ago
- Bugs are unexpected behaviors in programs, often arising from computational irreducibility, where a program's behavior cannot be predicted without running it.
- Even simple systems like Turing machines and cellular automata can exhibit bugs, showing that bugs are a fundamental phenomenon in computation.
- Testing programs exhaustively is impossible due to computational irreducibility; bugs can be rare and hard to detect, appearing only after many cases.
- Formal proofs can verify correctness for some programs, but they may require arbitrarily long proofs and are limited by computational irreducibility.
- Language design, such as in Wolfram Language, helps reduce bugs by providing primitives that align with human intent and computational reducibility.
- Ruliology (study of simple programs) reveals that surprises and bugs are common, challenging scientific induction and expectations.