Для первых двух, техника под названием ласточкин хвост может помочь вам показать, что языки перечислимы.Для L_1: с учетом нумерации Гёделя всех машин Тьюринга вычислите шаг 1 из M1 (eps), затем шаг 1 из M2 (eps), затем шаг 2 из M1 (eps), 1 из M3 (eps), 2 из M2(eps), 3 из M1 (eps) ... другими словами, нижний левый треугольник системы координат с "числом шагов" и "номером Тьюринга" x в качестве осей.
Если epsilon находится вL (Mx), то оно принимается за ряд n шагов.С помощью вашего метода вы обнаружите это, когда достигнете координаты [x, n].Это верно для каждого [x, n], поэтому вы можете перечислить все машины следующим образом.
Поскольку слово имеет только конечное число префиксов, вы также можете применить этот метод для L2, выполнивчерез систему координат, как указано выше для каждого префикса (не последовательно, а также переплетены).Таким образом, L2 тоже перечислимо.
Для L3 существует w, где M принимает все префиксы w, тогда это также верно для строки, состоящей только из первой буквы w.Поэтому вам нужно проверить его только для конечного числа символов алфавита, точно так же, как для L2.
Что касается рекурсивности трех языков, прочитайте, например, этот ответ , который относится к вашемуL1.