Ciro Santilli There is a Turing machine that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.
Subset of recursively enumerable language as explained at: difference between recursive language and recursively enumerable language.
Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.
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?
Same as recursive language but in the context of the integers.
This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).
By Noam Chomsky.
TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!