For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could explain it to me.

In this question, L1, L2, L3, L4 refer to languages and M, M1, M2 refer to Turing machines.  

Let

L1 = {(M1,M2) | L(M1) is a subset of L(M2)},
L2 = {M | There exists an input on which TM M halts within 100 steps},
L3 = {M | There exists an input w of size less than 100, such that M accepts w},
L4 = {M | L(M) contains at least 2 strings}.

Decide whether each of L1, L2, L3 and L4 are recursive, RE or neither. Then identify the true statement below.

     a)      The complement of L3 is recursively enumerable.
     b)      The complement of L2 is recursive.
     c)      The complement of L2 is not recursively enumerable.
     d)      L1 is recursively enumerable.

My guesses (probably wrong) were:

L1: ?

L2: recursive enumerable (I thought this since obviously there are inputs on which the TM halts but we can not say if it halts every time – therefore only recursive enumerable and not recursive)

L3: recursive enumerable (Same explanation as for L2)

L4: not recursive (This is only a guess, I don't get how the number of minimum strings of the language can imply any type of recursiveness.)

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could explain it to me.

In this question, L1, L2, L3, L4 refer to languages and M, M1, M2 refer to Turing machines.  

Let

L1 = {(M1,M2) | L(M1) is a subset of L(M2)},
L2 = {M | There exists an input on which TM M halts within 100 steps},
L3 = {M | There exists an input w of size less than 100, such that M accepts w},
L4 = {M | L(M) contains at least 2 strings}.

Decide whether each of L1, L2, L3 and L4 are recursive, RE or neither. Then identify the true statement below.

     a)      The complement of L3 is recursively enumerable.
     b)      The complement of L2 is recursive.
     c)      The complement of L2 is not recursively enumerable.
     d)      L1 is recursively enumerable.

What I do not understand is, how the definitions of L1, L2, L3, L4 can tell me whether or not they are recursive (enumerable).

My guesses (probably wrong) are:

L1: ?

L2: recursive enumerable (I thought this since obviously there are inputs on which the TM halts but we can not say if it halts every time – therefore only recursive enumerable and not recursive)

L3: recursive enumerable (Same explanation as for L2)

L4: not recursive (This is only a guess, I don't get how the number of minimum strings of the language can imply any type of recursiveness.)