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.  


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

  • 1
    $\begingroup$ It would help if you could be a bit more specific about what you don't understand. Our telling you the answer to a couple of questions won't help you very much when the next question comes along. $\endgroup$ Commented Mar 30, 2014 at 12:22
  • $\begingroup$ What I do not understand is how the definitions of L1, L2, L3, L4 can tell me whether they are rec or RE. $\endgroup$ Commented Mar 30, 2014 at 12:37
  • $\begingroup$ The definitions can't tell you. You have to think about the concepts behind them and think about how you'd try to determine that some string is or isn't in each of the languages. $\endgroup$ Commented Mar 30, 2014 at 12:52

1 Answer 1



  1. If you're trying to figure out some property of a Turing machine and the only thing you can think of is, "Check every input" then it's probably not recursive.

  2. If a language is RE and so is its complement, both are actually recursive (this is a good way of proving that languages aren't RE: for example, the language of pairs $\langle M,x\rangle$ such that Turing machine $M$ does not halt on input $x$ is not RE for this reason).

  3. If a Turing machine halts within 100 steps, how much of its input has it seen?

Note that L2 and L3 are subtly different so you can't use the same explanation for both (the answers are actually different).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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