Suppose L1, L2, and L3 are languages and T1, T2, and T3 are Turing machines such that L(T1) = L1, L(T2) = L2, L(T3) = L3.

Suppose further that T3 always halts on all inputs (i.e., L3 is recursive). For any input, T3 will either halt and accept it or halt and reject it. On the other hand, both T1 and T2 may get stuck in infinite loopsbut only for input words that they do not accept (i.e., L1 and L2 are recursively enumerable).

For each of the following languages, describe the Turing machine that would accept it, and state whether this machine always halts for all inputs or might loop forever on some rejected words. Remember that you can use multiple tapes and non-determinism in your description, and you do not need to give the Turing machine as a state diagram but rather just a higher-level algorithm description as we did for the one-tape machine that simulates a two-tape machine in class.

(a) (2 points) L1 L2 L3.

(b) (2 points) L1 L2 L3.

(c) (2 points) L1 \ L3.

(d) (2 points) L1L2L3 (i.e., the concatenation of the language).

(e) (2 points) L1 L1.