Использование результатов закрытия для разрешимых по Тьюрингу языков

Question

У меня есть язык L1 = {w в {0,1} * |w содержит одинаковое количество 1 и 0}, и у меня есть TM M, который решает L1.

Я хочу доказать, что L2 = {w в {0,1} * |w содержит больше 1, чем 0}, разрешима по Тьюрингу.

Я использовал подход "закрыто по дополнению" и доказал, что M 'решает дополнение L1 (~ L1).

MyВопрос в том, могу ли я предположить, что ~ L1 = (L2 или ~ L2), и заключить, что, поскольку M 'решает ~ L1, что L2 и ~ L2 оба являются разрешимыми языками?

Спасибо за любой совет (Извините,еще не понял, как использовать LaTex здесь ...)

Answer 1

Я просто хочу конкретизировать ответ Веллбога. Вот L1 (Прочитайте n ₁ (w) как «число 1 в w»):

L1 = {w∈ {0,1} ^*: n ₁ (ш) = n ₀ (ш)}

А вот и L2:

L2 = {w∈ {0,1} ^*: n ₁ (ш)> n ₀ (ш)}

С другой стороны, L1-бар это:

L1-bar = {w∈ {0,1} ^*: n ₁ (ш)> n ₀ (ш) ИЛИ n ₁ (ш) 0 (ш)}

И ясно, что L1-бар и L2 различны.