3
$\begingroup$

How do I decide if a language is decidable and/or semi-decidable?

I have theses languages:

a) { < M > | L(M) ⊆ 0*}

b) { < M > | L(M) contains at least one word of even length}

c) { < M > | L(M) is semi-decidable}

d) { < M > | L(M) is decidable}

My problem is, that I don’t quite now how to interpret this notation. I know that <M> is the code of a turing-machine and L(M) is the language decided by the turing machine.

But I’m not quite sure if I understand “language decided by a turing machine” correctly.

Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?

Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?

I guess there’s a major flaw in my thoughts, but which is it?

For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.

How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0* (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0*. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.

b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.

I know there are many errors in my argumentation (but don’t know which these are). This topic is very new to me. I’m thankful about hints on how to solve these kind of decidablity questions. The most examples I found online are about deciding whether M, not L(M) is decidable: { | M does this or that}.

$\endgroup$
  • 1
    $\begingroup$ If you are already familiar with Rice's theorem, then you should be able to tackle all of a)–d) (at least what concerns decidability). What is your actual question? "How do I decide if a language is decidable and/or semi-decidable?" This? $\endgroup$ – dkaeae Jul 16 at 11:40
  • 2
    $\begingroup$ The interpretation of the notation, and the meanings of such terms as "the language decided by" a given Turing machine should be covered by your course materials in some detail. Did you refer to them? $\endgroup$ – David Richerby Jul 16 at 14:53
  • 1
    $\begingroup$ Please edit the question to add a reference to the textbook or the online course material your are using. $\endgroup$ – Apass.Jack Jul 16 at 15:18
  • $\begingroup$ We don't use a textbook but the script written by my professor. Regarding L(M) it only says: "The language accepted by M is L(M) = {w ∈ Σ∗ | w is accepted by M}" (translated, because the script is in German). However, I realize that my question is to unspecific. I'm sorry, should I delete? $\endgroup$ – Mika2019 Jul 16 at 22:56
  • $\begingroup$ @Mika2019 If you can't narrow it down, it will most likely just end up being closed as "unclear what you're asking". I suggest you actually try to solve (at least one of) the questions (possibly with the help of your classmates and tutors) and come back when you have some particular conceptual difficulty you can ask about. $\endgroup$ – dkaeae Jul 17 at 7:18
2
$\begingroup$

Nice question.

Notations and terms

$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.

$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.

Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book introduction to the theory of computation by Michael Sipser. You could take a look at its definition at Wikipedia as well.

We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.

DEFINITION 3.6. Call a language Turing-decidable or simply decidable if some Turing machine decides it.

Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.

Application of Rice's theorem

Here is the Rice's theorem.

Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.

In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $\langle M_1\rangle \in P$ iff $\langle M_2\rangle \in P$. Here, $M_1$ and $M_2$ are any TMs. Then $P$ is an undecidable language.

a) $P=\{\langle M \rangle\mid L(M)\subseteq 0^*\}$.

  • WLOG, let 1 be an input alphabet symbol other than 0. $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{0\}$ but $P$ does not contain the description of a Turing machine whose language is $\{1\}$.
  • $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)\subseteq 0^*$ iff $L(M_2)\subseteq 0^*$

    By Rice's theorem, $P$ is undecidable.

b) $P=\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\}$.

  • $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{00\}$ but $P$ does not contain the description of a Turing machine whose language is $\{0\}$.

  • $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ contains at least one word of even length iff $L(M_2)$ contains at least one word of even length.

    By Rice's theorem, $P$ is undecidable.

c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\}$ contains all TM descriptions, which is a decidable language.

d) $P=\{\langle M \rangle\mid L(M)\text{ is decidable}\}$.

  • Let $R=L(D)$ be a decidable language. For example, we can take $R=\{0\}$ and $D$ is a Turing machine that accepts 0 and rejects all other inputs. $\langle D\rangle\in P$. Let $H=L(N)$ be a semi-decidable but not decidable language. For example, we can take $H$ to be the language of the halting problem. Then $\langle N\rangle\not\in P$. Hence $P$ is nontrivial.
  • $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ is decidable iff $L(M_2)$ is decidable.

    By Rice's theorem, $P$ is undecidable.

For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\{0\}$, then, of course, for every $M$, $L(M)\subseteq 0^*$. Then $\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^*\}$ contains all TM descriptions. It is decidable.

$\endgroup$
  • $\begingroup$ Minor nit: I like to distinguish between accepting and recognising. A TM accepts/rejects a string, whereas it recognises a language. $\endgroup$ – user679128 Jul 20 at 22:30
  • $\begingroup$ @user679128, thanks. Updated. $\endgroup$ – Apass.Jack Jul 21 at 6:48

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.