Undecidability requires infinitely many inputs
ID: undecidability-requires-infinitely-many-inputs
Undecidability requires infinitely many inputs by Ciro Santilli 35 Updated 2025-01-29 +Created 2024-07-12
If there are infinitely many inputs, we can always construct a (potentially exponentially huge) Turing machine that hardcodes the outcome for every possible input, so the problem is never undecidable.
The problem is of course deciding and proving the outcome for each possible input, notably as it is possible that calculation for some of the inputs may be independent from ZFC.
New to topics? Read the docs here!