Something like a Turing machine, with its finite states, deterministic transitions, and simple tape seems so mechanical, so physical. So predictable.
Sure, there's the halting problem, but that relies on a paradox.
Surely something as artifical as self-referential statements would seem a bit pointless.
And yet, with the help of that principle, it turns out we can write simple, mechanical programs where if the input is < N we can calculate the answer, and if the input is > N we can't figure out what the program will do (using standard mathematical thinking).
For some N we can get creative, but for a yet bigger N, we may well find ourselves unable to be creative enough to work out if we could ever work out the the answer.
"In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which Σ(n) is unprovable in ZFC. To do so they constructed a 7910-state[2] Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (stationary Ramsey property).[3][4] This was later reduced to 1919 states, with the dependency on the stationary Ramsey property eliminated.[5][6]"
Sure, there's the halting problem, but that relies on a paradox.
Surely something as artifical as self-referential statements would seem a bit pointless.
And yet, with the help of that principle, it turns out we can write simple, mechanical programs where if the input is < N we can calculate the answer, and if the input is > N we can't figure out what the program will do (using standard mathematical thinking).
For some N we can get creative, but for a yet bigger N, we may well find ourselves unable to be creative enough to work out if we could ever work out the the answer.
https://en.wikipedia.org/wiki/Busy_beaver#Non-computability
"In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which Σ(n) is unprovable in ZFC. To do so they constructed a 7910-state[2] Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (stationary Ramsey property).[3][4] This was later reduced to 1919 states, with the dependency on the stationary Ramsey property eliminated.[5][6]"