9
$\begingroup$

There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc.

In this case I wonder whether a problem can be meta-undecidable. This means (at least in my head) we cannot tell whether it is decidable or not.

Maybe it's known decidability is undecidable (everything is meta-undecidable) and no algorithm exists to prove decidability for anything, so decidability has to be proven by hand on a case by case basis.

Maybe my question doesn't make sense. Maybe I'm assuming we are carbon machines running very complex algorithms and that's why the question makes sense only in my head.

Please let me know if the question needs further clarification. I may need that myself at this moment.

Thank you.

$\endgroup$
  • $\begingroup$ Let us consider the statement "the monadic (second-order) theory of all linear orders is computable". There are reasons to belive (but I am not sure that independency has been proved) that this statement is independent (i.e., undecidable) in ZFC. More details about the reasons can be found in books.google.es/books?id=y3YpdW-sbFsC&pg=PA397 $\endgroup$ – boumol Jun 14 '13 at 17:47
  • 1
    $\begingroup$ When you say "decidability is undecidable", what is the input? $\endgroup$ – MCH Jun 14 '13 at 18:21
  • 2
    $\begingroup$ He might also be interested in en.wikipedia.org/wiki/Turing_degree but it's unclear from how the question is stated. :) $\endgroup$ – Daniel Apon Jun 14 '13 at 19:01
  • 1
    $\begingroup$ @boumol Shelah ("The monadic theory of order", Ann. Math. 102(3), 1975) proved (assuming CH) that "the monadic theory of order is undecidable" (Theorem 7(B), p. 409). $\endgroup$ – Yuval Filmus Jun 14 '13 at 19:31
  • 1
    $\begingroup$ $L = \begin{cases} \text{halting problem} & \text{if the continuum hypothesis holds} \\ \emptyset & \text{otherwise} \end{cases}$ $\endgroup$ – sdcvvc Jun 14 '13 at 20:56
8
$\begingroup$

Here's a quick sketch to show that there is no Turing machine to decide whether an arbitrary class of problems is decidable.

I should clarify what I mean by class of problems: a class of problems $T$ is a Turing machine which enumerates the elements (natural numbers, say) of a recursively enumerable set one after the other, such that each element in the set is eventually printed. The problem intuitively captured by $T(n)$ is: "is the number $n$ in this set?". This captures the usual problems in the field of computability, such as "is i the index of a Turing machine that halts on empty input?".

Suppose there was machine $M$ which, given as input a class of problems $T$ answered $\mathit{true}$ if that class is decidable and $\mathit{false}$ otherwise.

Now take an arbitrary Turing machine $T$. We build the following class of problems $T'$ in the following manner:

  1. Simulate $T$.
  2. If $T$ halts, enumerate the indices of the Turing machines that halt on empty input.

Now it is clear that if $T$ halts, then $M(T')$ returns $\mathit{false}$, as the set of indices halting Turing machines is not a decidable (recursive) set.

If $T$ does not halt, then $T'$ does not enumerate any numbers, which makes it exactly the class of problems containing no indices! Therefore $M(T')$ answers $\mathit{true}$, since that class is decidable (by the machine that always rejects).

Therefore, $M(T')$ returns $\mathit{true}$ iff $T$ does not halt, and $\mathit{false}$ otherwise. Thus the existence of $M$ allows us to solve the halting problem for an arbitrary machine $T$, which is a contradiction.

$\endgroup$
  • $\begingroup$ Hey Cody! I hope you are doing well. Will you be in Pittsburgh this summer? $\endgroup$ – Michael Wehar May 15 '14 at 8:46
  • $\begingroup$ Hey! I'm not sure. Send me an e-mail though! $\endgroup$ – cody May 15 '14 at 17:24
1
$\begingroup$

Very cool idea!

Idea: We can exploit the comprehension axiom in ZF set theory to define a language that depends on an independent statement.

Step 1: Take your favorite statement that is independent of ZF such as AC - the axiom of choice.

Step 2: Define a language L = {x in {0,1} | x = 0 if AC and x = 1 if NOT AC}. Notice that L is either {0} or {1}. Now, L is decidable, yet we are unable to provide with certainty a program that decides L. We could provide the program that decides {0} or we could provide the program that decides {1}, but we don't know with certainty which one decides L.

Step 3: Use this idea to define a language that is decidable if AC and undecidable if NOT AC. Let H be the halting set which is undecidable. Define L = {x | x is a string if AC and x is in H if NOT AC}. If AC, then L = the set of all strings and L is decidable. If NOT AC, then L = H and L is undecidable. Whether or not L is decidable is independent of ZF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.