Which languages, decided by a turing machine are decidable?

Question

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}.

Answer 1

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.}