Ciro Santilli Is a decision problem of determining if something belongs to a non-recursive language.
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.
Some undecidable problems are of recursively enumerable language, e.g. the halting problem.
Lists of undecidable problems.
Coolest ones besides the obvious boring halting problem:
- mortal matrix problem
- Diophantine equation existence of solutions: undecidable Diophantine equation problems
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.
There are only boring exampes of taking an uncomputable language and converting it into a number?