Timeline for How to tell if a language is recognizable, co-recognizable or decidable?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2013 at 18:03 | comment | added | Joey Eremondi | I've edited my answer to reflect the flaws Raphael found. | |
| Apr 23, 2013 at 18:02 | history | edited | Joey Eremondi | CC BY-SA 3.0 | added 270 characters in body |
| Apr 23, 2013 at 18:01 | comment | added | Joey Eremondi | I guess I should clarify. The idea is that you can't brute-force the halting problem the way you can, say, 3-SAT. Or how, when you run something on a PDA, you can try all possible paths even though it's non-deterministic. But for a TM, you can't because it could run infinitely long, so the set of "things to try" i.e. the possible paths through the program, is not finite. | |
| Apr 23, 2013 at 17:46 | comment | added | Raphael | @Steven Yes, but that's an even harder proof. (The set you are referring to is typically denoted with R, the set of recursive(ly decidable) languages.) | |
| Apr 23, 2013 at 17:45 | comment | added | Raphael | Also: "Anything with a finite "set of possibilities" to try will be decidable" -- no. The halting problem has two possible answers but is undecidable. | |
| Apr 23, 2013 at 17:45 | comment | added | Steven | Ah, that sparks an idea. We know that $NP \subseteq \{L|\ L\ Decidable\}$, so that would imply that if we can show a problem to be in NP (or P for that matter) then it simply follows from that. That could help narrow it down. | |
| Apr 23, 2013 at 17:44 | comment | added | Raphael | "If the solution space is countably infinite, then we know that the problem is recognizable." -- Not necessarily. First, the solution space may not be effectively enumerable (Example: "Is there a TM that computes a total function and so that [non-trivial predicate]?"). Second, the decision whether the considered object is a solution may be undecidable itself (Example: "Find a TM that does not halt on 77."). | |
| Apr 23, 2013 at 17:34 | history | answered | Joey Eremondi | CC BY-SA 3.0 |