Or in other words: there is no Turing machine that always halts for every input with the yes/no output.
Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.
Lists of undecidable problems.
Coolest ones besides the obvious boring halting problem:
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.
One of the most simple to state undecidable problems.
The reason that it is undecidable is that you can repeat each matrix any number of times, so there isn't a finite number of possibilities to check.
A:
- decidable problem is to a decision problem
- like a computable problem is to a function problem
The prototypical example is the Busy beaver function, which is the easiest example to reach from the halting problem.
Articles by others on the same topic
An undecidable problem is a decision problem for which no algorithm can be constructed that always leads to a correct yes-or-no answer for all possible inputs. In other words, there is no computational method that can determine the answer to these problems in a finite amount of time for every possible case. One of the most famous examples of an undecidable problem is the **Halting Problem**.