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.

Improve this question
$\endgroup$
10
  • $\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, 2013 at 17:47
  • 1
    $\begingroup$ When you say "decidability is undecidable", what is the input? $\endgroup$
    – Mahdi Cheraghchi
    Jun 14, 2013 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, 2013 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, 2013 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, 2013 at 20:56

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hey Cody! I hope you are doing well. Will you be in Pittsburgh this summer? $\endgroup$
    – Michael Wehar
    May 15, 2014 at 8:46
  • $\begingroup$ Hey! I'm not sure. Send me an e-mail though! $\endgroup$
    – cody
    May 15, 2014 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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