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