0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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?" $\endgroup$ – Max New Nov 17 '19 at 22:17
  • 1
    $\begingroup$ How do you represent the languages as inputs to the turing machine? $\endgroup$ – Max New Nov 17 '19 at 23:21
  • $\begingroup$ @MaxNew if we don't allow use of excluded middle--what is answer? $\endgroup$ – DeeDee Nov 18 '19 at 0:04
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is there a "constructive" answer to this question (no excluded middle). $\endgroup$ – DeeDee Nov 18 '19 at 0:02
0
$\begingroup$

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<M,w\right>$ (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.

| cite | improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ If the input is given by Turing machines, the problem is undecidable immediately from Rice’s theorem. $\endgroup$ – Emil Jeřábek Nov 18 '19 at 7:47
  • $\begingroup$ 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? $\endgroup$ – Dylan McKay Nov 18 '19 at 15:49

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