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$ – David Richerby Mar 30 '14 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$ – Jakob Abfalter Mar 30 '14 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$ – David Richerby Mar 30 '14 at 12:52


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

| cite | improve this answer | |

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.