<p>Sure.
There are Turing machines that always reject or always accept...
So, one of them is surely correct...</p>

CC BY-SA 4.0
2019-11-17T22:04:19.730Z
2019-11-17T22:04:19.730Z
Avi Tal
<p>This question depends on exactly what representation you use. I could imagine a few ways. The standard way would be to represent languages with machines whose languages are those we want to represent. For this context, I guess that's pretty unsatisfying. You could certainly imagine representing them with some predefined set of predicates and functions over languages and machines and get something interesting that probably resembles how we talk about languages.</p>

<p>The bottom line, though, is this If your representation is reasonable enough and powerful enough, there's definitely no way this thing is decidable or recognizable. Even if I'm giving you the input as a machine recognizing the language, you won't be able to tell if the language is decidable (as remarked in the comments, this follows immediately from Rice's Theorem).</p>

<p>In general, as long as our representation is strong enough, there is a many-one reduction from <span class="math-container">$\overline{A_{TM}}$</span> to this language (let's call it <span class="math-container">$D$</span>). Remember that <span class="math-container">$\overline{A_{TM}}$</span> is essentially "given a machine <span class="math-container">$M$</span> and an input <span class="math-container">$w$</span>, does <span class="math-container">$M$</span> <strong>not</strong> accept <span class="math-container">$w$</span>?"</p>

<p>The reduction could look like this: given a string <span class="math-container">$\left&lt;M,w\right&gt;$</span> (our instance of <span class="math-container">$\overline{A_{TM}}$</span>), we will produce a description of the language <span class="math-container">$L$</span> which is "the empty language if <span class="math-container">$M$</span> does not accept <span class="math-container">$w$</span> and <span class="math-container">$HALT_{TM}$</span> if <span class="math-container">$M'$</span> does accept <span class="math-container">$w$</span>". If our representation is the Turing machine one I mentioned, this would look like </p>

<pre><code><span class="math-container">$M'$</span>: 
On input <span class="math-container">$x$</span>:
Simulate <span class="math-container">$M$</span> on <span class="math-container">$w$</span>
If <span class="math-container">$M$</span> ever accepts <span class="math-container">$w$</span>, 
    Simulate <span class="math-container">$H(x)$</span> and accept if <span class="math-container">$H(x)$</span> accepts ----- where <span class="math-container">$H$</span> is some canonical machine whose language is <span class="math-container">$HALT_{TM}$</span>
</code></pre>

<p>But of course, we could imagine this reduction being just as straight forward for other powerful representations we might be interested in.</p>

<p>Since this is a many-one reduction and <span class="math-container">$\overline{A_{TM}}$</span> is not recognizable, we get that D is not recognizable.</p>

<p>Depending on the strength of your representation, I'm sure you could easily prove <span class="math-container">$D$</span> is also not co-recognizable. I don't immediately see how to prove it for this specific version, though, but I wouldn't be surprised if someone else saw it pretty quickly. </p>

CC BY-SA 4.0
2019-11-18T07:47:48.647Z
If the input is given by Turing machines, the problem is undecidable immediately from Rice’s theorem.
Emil Jeřábek
CC BY-SA 4.0
2019-11-18T15:49:47.443Z
I totally overlooked that Rice's theorem gave a very succinct explanation. Is there an extension of Rice's theorem which also tells us whether or not this language is recognizable or co-recognizable?
Dylan McKay
CC BY-SA 4.0
2023-10-24T08:50:30.127Z
Yes: https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem .
Emil Jeřábek
CC BY-SA 4.0
2019-11-18T00:41:23.190Z
2019-11-18T15:42:44.780Z
2019-11-18T15:42:44.780Z
Dylan McKay
<p>Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?</p>

<p>Comments + answer say trivially the answer is yes; however, I'm wondering here would it be possible without the use of excluded middle to construct such a machine. </p>

CC BY-SA 4.0
2019-11-17T22:17:06.527Z
As Avi Tal says, the answer is trivially yes using the law of excluded middle. Do you mean "Is there a Turing machine that takes some description of a language as input and decides/semi-decides if it is a decidable language?"
Max New
CC BY-SA 4.0
2019-11-17T23:21:14.240Z
How do you represent the languages as inputs to the turing machine?
Max New
CC BY-SA 4.0
2019-11-18T00:04:05.237Z
@MaxNew if we don't allow use of excluded middle--what is answer?
DeeDee
<fl.formal-languages><computability><turing-machines><decidability>
Is the decidability of a language decidable?
DeeDee
# Is the decidability of a language decidable?

(Asked by: username_0 on 2019-11-17)

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?

Comments + answer say trivially the answer is yes; however, I'm wondering here would it be possible without the use of excluded middle to construct such a machine.

**Tags:** fl.formal-languages, computability, turing-machines, decidability
> **Comments:**
> **username_1**: As Avi Tal says, the answer is trivially yes using the law of excluded middle. Do you mean "Is there a Turing machine that takes some description of a language as input and decides/semi-decides if it is a decidable language?"  
> **username_1**: How do you represent the languages as inputs to the turing machine?  
> **username_0**: @MaxNew if we don't allow use of excluded middle--what is answer?  

---

## 2 answers

### Answer by username_2 on 2019-11-17. Score: 1

Sure.
There are Turing machines that always reject or always accept...
So, one of them is surely correct...


---

### Answer by username_3 on 2019-11-18. Score: 0

This question depends on exactly what representation you use. I could imagine a few ways. The standard way would be to represent languages with machines whose languages are those we want to represent. For this context, I guess that's pretty unsatisfying. You could certainly imagine representing them with some predefined set of predicates and functions over languages and machines and get something interesting that probably resembles how we talk about languages.
The bottom line, though, is this If your representation is reasonable enough and powerful enough, there's definitely no way this thing is decidable or recognizable. Even if I'm giving you the input as a machine recognizing the language, you won't be able to tell if the language is decidable (as remarked in the comments, this follows immediately from Rice's Theorem).
In general, as long as our representation is strong enough, there is a many-one reduction from $\overline{A_{TM}}$ to this language (let's call it $D$). Remember that $\overline{A_{TM}}$ is essentially "given a machine $M$ and an input $w$, does $M$ not accept $w$?"
The reduction could look like this: given a string $\left$ (our instance of $\overline{A_{TM}}$), we will produce a description of the language $L$ which is "the empty language if $M$ does not accept $w$ and $HALT_{TM}$ if $M'$ does accept $w$". If our representation is the Turing machine one I mentioned, this would look like 
$M'$: 
On input $x$:
Simulate $M$ on $w$
If $M$ ever accepts $w$, 
    Simulate $H(x)$ and accept if $H(x)$ accepts ----- where $H$ is some canonical machine whose language is $HALT_{TM}$

But of course, we could imagine this reduction being just as straight forward for other powerful representations we might be interested in.
Since this is a many-one reduction and $\overline{A_{TM}}$ is not recognizable, we get that D is not recognizable.
Depending on the strength of your representation, I'm sure you could easily prove $D$ is also not co-recognizable. I don't immediately see how to prove it for this specific version, though, but I wouldn't be surprised if someone else saw it pretty quickly.

> **Comments:**
> **username_4**: If the input is given by Turing machines, the problem is undecidable immediately from Rice’s theorem.  
> **username_3**: I totally overlooked that Rice's theorem gave a very succinct explanation. Is there an extension of Rice's theorem which also tells us whether or not this language is recognizable or co-recognizable?  
> **username_4**: Yes: https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem .  

---

