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

<p>I should clarify what I mean by class of problems: a <em>class of problems</em> $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?".</p>

<p>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.</p>

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

<ol>
<li>Simulate $T$.</li>
<li>If $T$ halts, enumerate the indices of the Turing machines that halt on empty input.</li>
</ol>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-05-15T08:46:10.057Z
Hey Cody!  I hope you are doing well.  Will you be in Pittsburgh this summer?
Michael Wehar
CC BY-SA 3.0
2014-05-15T17:24:19.983Z
Hey! I'm not sure. Send me an e-mail though!
cody
CC BY-SA 3.0
2013-06-15T01:13:46.223Z
2014-05-14T21:46:42.480Z
2014-05-14T21:46:42.480Z
cody
<p>Very cool idea!</p>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-15T09:00:44.590Z
2014-05-16T04:08:37.037Z
2014-05-16T04:08:37.037Z
Michael Wehar
<p>There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<p>Thank you.</p>

CC BY-SA 3.0
2013-06-14T17:47:56.343Z
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 http://books.google.es/books?id=y3YpdW-sbFsC&pg=PA397
boumol
CC BY-SA 3.0
2013-06-14T18:21:56.917Z
When you say "decidability is undecidable", what is the input?
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-14T18:48:19.357Z
I suspect Trylks is using the same word with two different meanings, one about "computability" and the other about "independence in some formal system". Thus, "decidability is undecidable" can be read as "the computability of some particular decision problem is independent in ZFC (Zermelo-Fraenkel with Choice)". Trylks, is my interpretation the one you did?
boumol
CC BY-SA 3.0
2013-06-14T19:01:01.453Z
He might also be interested in http://en.wikipedia.org/wiki/Turing_degree but it's unclear from how the question is stated. :)
Daniel Apon
CC BY-SA 3.0
2013-06-14T19:31:58.670Z
@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).
Yuval Filmus
CC BY-SA 3.0
2013-06-14T20:14:51.427Z
@Yuval: This result of Shelah only proves that the statement I wrote in my remark is consistent with ZFC, but not that it is independent in ZFC. Indeed, it is better (to avoid problems) to read Shelah's result as "the monadic theory of order is non computable (under CH)". As far as I know it is still open whether it is independent in ZFC (i.e., undecidable in ZFC).
boumol
CC BY-SA 3.0
2013-06-14T20:56:31.900Z
$L = \begin{cases} \text{halting problem} & \text{if the continuum hypothesis holds} \\ \emptyset & \text{otherwise} \end{cases}$
sdcvvc
CC BY-SA 3.0
2013-06-15T09:54:47.460Z
The question is more in the sense of: Having a problem _p_ upon inspection we cannot find a solution for _p_, prove _p_ is unsolvable or prove _p_ is undecidable. Therefore the problem would remain open for ever. Some Millenium Prize problems could be eternal, and the question is whether we can or cannot tell whether they are eternal beforehand. The wording may be horrible, but I guess the answer given by @cody means we cannot know beforehand whether we can solve a problem or not until we solve that problem, or we solve that metaproblem specifically. I'm sorry that I'm so confused.
Trylks
CC BY-SA 3.0
2014-05-14T21:51:24.590Z
I think you're confused because you don't distinguish a *class of problems* (or just "a problem") from a *problem instance*. In the first case you have an infinite set of different problems (like "does this turing machine halt" for each turing machine), in which case it can be an undecidable problem: there are always *some* examples of instances we won't know how to solve. In the case of an *instance of a problem*, the situation is binary: either we've solved it or we haven't it yet.
cody
CC BY-SA 3.0
2014-05-14T21:54:04.300Z
For an instance, it makes sense to say it's undecidable *in a given formal system* (say ZFC), if neither the statement nor it's negation is provable. It doesn't make sense to say it's undecidable *in the absolute*. The proof I sketched showed that you can't decide whether problem *classes* are undecidable, and furthermore you can show that knowing whether a given instance is undecidable *with respect to a given formal system like ZFC* is undecidable as well. There's no free lunch in logic!
cody
<computability><decidability><undecidability>
Is meta-undecidability possible?
Trylks
# Is meta-undecidability possible?

(Asked by: username_0 on 2013-06-14)

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.

**Tags:** computability, decidability, undecidability

> **Comments:**
> **username_1**: 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 http://books.google.es/books?id=y3YpdW-sbFsC&pg=PA397  
> **username_2**: When you say "decidability is undecidable", what is the input?  
> **username_1**: I suspect username_0 is using the same word with two different meanings, one about "computability" and the other about "independence in some formal system". Thus, "decidability is undecidable" can be read as "the computability of some particular decision problem is independent in ZFC (Zermelo-Fraenkel with Choice)". username_0, is my interpretation the one you did?  
> **username_3**: He might also be interested in http://en.wikipedia.org/wiki/Turing_degree but it's unclear from how the question is stated. :)  
> **username_4**: @username_1 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).  
> **username_1**: @Yuval: This result of Shelah only proves that the statement I wrote in my remark is consistent with ZFC, but not that it is independent in ZFC. Indeed, it is better (to avoid problems) to read Shelah's result as "the monadic theory of order is non computable (under CH)". As far as I know it is still open whether it is independent in ZFC (i.e., undecidable in ZFC).  
> **username_5**: $L = \begin{cases} \text{halting problem} & \text{if the continuum hypothesis holds} \\ \emptyset & \text{otherwise} \end{cases}$  
> **username_0**: The question is more in the sense of: Having a problem _p_ upon inspection we cannot find a solution for _p_, prove _p_ is unsolvable or prove _p_ is undecidable. Therefore the problem would remain open for ever. Some Millenium Prize problems could be eternal, and the question is whether we can or cannot tell whether they are eternal beforehand. The wording may be horrible, but I guess the answer given by @username_6 means we cannot know beforehand whether we can solve a problem or not until we solve that problem, or we solve that metaproblem specifically. I'm sorry that I'm so confused.  
> **username_6**: I think you're confused because you don't distinguish a *class of problems* (or just "a problem") from a *problem instance*. In the first case you have an infinite set of different problems (like "does this turing machine halt" for each turing machine), in which case it can be an undecidable problem: there are always *some* examples of instances we won't know how to solve. In the case of an *instance of a problem*, the situation is binary: either we've solved it or we haven't it yet.  
> **username_6**: For an instance, it makes sense to say it's undecidable *in a given formal system* (say ZFC), if neither the statement nor it's negation is provable. It doesn't make sense to say it's undecidable *in the absolute*. The proof I sketched showed that you can't decide whether problem *classes* are undecidable, and furthermore you can show that knowing whether a given instance is undecidable *with respect to a given formal system like ZFC* is undecidable as well. There's no free lunch in logic!  

---

## 2 answers

### Answer by username_6 on 2013-06-15. Score: 8

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.

> **Comments:**
> **username_7**: Hey Cody!  I hope you are doing well.  Will you be in Pittsburgh this summer?  
> **username_6**: Hey! I'm not sure. Send me an e-mail though!  

---

### Answer by username_7 on 2014-05-15. Score: 1

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.


---

