Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ The answer of @Peter shows that a question that was received rather negatively can have a proper interpretation: the language is "recursive" relative to an oracle. $\endgroup$– Hendrik JanCommented Jul 21, 2014 at 19:35
-
1$\begingroup$ What have you tried? What are your thoughts? What research have you done? This is covered in some textbooks on complexity theory / decidability (the different "levels" of undecidability). $\endgroup$– D.W. ♦Commented Jul 21, 2014 at 22:08
-
$\begingroup$ The question is naively stated, but does make sense when properly addressed, as shown by the accepted answer. To state it cleanly, the OP would have to know this answer. $\endgroup$– babouCommented Jul 21, 2014 at 22:25
-
2$\begingroup$ This has been dealt with before here and here. $\endgroup$– RaphaelCommented Jul 22, 2014 at 7:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
While we know for sure that the halting problem is (and always will be) undecidable by a Turing machine, we can take the following approach to investigate your question:
Assume that we have a magical machine that can solve the halting problem. We call this machine an oracle. We can now wire this machine into a Turing machine, creating Turing machines that can solve the halting problem.
Unfortunately, the same problem we had with the original Turing machines occurs again: we can enumerate our oracle-enriched Turing machines. We can define the function that computes $T_i(i)+1$. This function cannot occur in our enumeration, because it differs from all Turing machines. In short, if we have machines that can solve the halting problem, we get a new halting problem for those machines.
This principle gives us a hierarchy of uncomputable functions (called the Turing hierarchy). Some functions become computable if we have machines with an oracle for the first halting problem, while others stay incomputable. If we give our machines an oracle for the second level halting problems, more functions become computable, but some functions will always be uncomputable.
And yes, languages that are only recursively enumerable to regular Turing machines are fully recursive to oracle-enriched Turing machines. Let's use the following definitions:
- A recursive set is one for which there exists a TM which can answer yes if a given element is in the set, and no if it isn't.
- A recursively enumerable set is one for which there exists a TM which can answer yes if a given element is in the set and compute indefinitely if it isn't.
In the second case, we can create an oracle enriched TM which checks if the non-enriched TM halts. So the enriched TM can give a yes-or-no answer.
Of course, there will be new languages which are recursively enumerable in the oracle-enriched world, but not recursive. In the non-enriched world, these languages were not enumerable in any way.
NB: In general, the phrase 'oracle' can mean any addition to enrich a Turing machine, not just one to solve the halting problem. If the type of oracle isn't clear from context a phrase like "a Turing machine with an oracle for the halting problem" should be used to avoid confusion.
-
$\begingroup$ Good answer! Although context makes it clear that, by "oracle-enriched Turing machine", you mean "a Turing machine with an oracle for some undecidable problem", it's best not to use phrases like that. It's common to consider Turing machines with oracles for much weaker problems, specifically, computable ones: for example, the $n$th level of the polynomial hierarchy is the set of polynomial time Turing machines with oracles for level $n-1$. None of those machines can decide undecidable problems. The power comes from the oracle being undecidable, not just from it being an oracle. $\endgroup$ Commented Jul 22, 2014 at 8:11
-
$\begingroup$ @DavidRicherby, that's true. I tried to simplify my answer so that the OP could understand it. That's why I phrased it in terms of a "magical machine". I'll add a note to avoid any confusion. $\endgroup$– PeterCommented Jul 22, 2014 at 11:00
$\begingroup$
$\endgroup$
6
This is an impossible situation to occur. It will not become decidable. It was proven by Turing in 1936 to be undecidable. So technically you can say anything will happen if it is decidable since it can never be, and would cause a contradiction if it was.
-
$\begingroup$ AFAIK Tuting only proved that the Halting problem cannot de decided with a Tuting Machine. Hence your assertion relies on an unproved statement, the Church-Turing Thesis. Of course, if you limit decidability by definition to Turing decidability, then you are right ... because you are restricting the world to what makes you right, without actually knowing for sure whether the world is thus restricted. $\endgroup$– babouCommented Jul 21, 2014 at 21:17
-
4$\begingroup$ Except that the person asking the question has already restricted the question to Turing decidability by defining the problem to be on decidability and the relation to recursive and non recursive languages, which are defined by Turing decidability. $\endgroup$– lPlantCommented Jul 21, 2014 at 21:34
-
1$\begingroup$ @babou In computer science, "decidable" means "decidable by a Turing machine" unless some other model of computation is stated explicitly or is very obvious from context. $\endgroup$ Commented Jul 21, 2014 at 22:08
-
$\begingroup$ Because we all believe in Church-Turing thesis ... However, the OP should be given the benefit of the doubt ... and the question made sense, even though naively stated, as shown by the accepted answer. It is normal that many questions are naively stated. CC @DavidRicherby $\endgroup$– babouCommented Jul 21, 2014 at 22:24
-
$\begingroup$ @babou It usually makes most sense to view the Church-Turing thesis as the definition of computation (i.e., computation is anything that's equivalent to a Turing machine) rather than as a hypothesis that may or may not be true (e.g., something like P$\neq$NP). When somebody posts here asking for an algorithm for problem X, you don't comment "Algorithm using what model of computation?" so I'm not sure why you keep making the corresponding point for the halting problem. $\endgroup$ Commented Jul 22, 2014 at 8:06
$\begingroup$
$\endgroup$
3
In classical logic, everything follows from a contradiction. Since we know that the halting problem is not decidable, then if we assume that it is decidable, we reach a contradiction, and so everything follows. So the answer is both TRUE and FALSE.
answered Jul 21, 2014 at 15:57
-
$\begingroup$ No, the answer is just TRUE: "if the halting problem is undecidable, then X" is universally true. $\endgroup$ Commented Jul 21, 2014 at 16:35
-
$\begingroup$ @David It depends on how you interpret the question. If it asks whether, assuming the premise, (1) X is true or (2) X is false, then both options are correct. $\endgroup$ Commented Jul 21, 2014 at 17:25
-
$\begingroup$ If decidability is the same as Turing decidability ... which depends on Church-Turing thesis. $\endgroup$– babouCommented Jul 21, 2014 at 21:21