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

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

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

Я использовал подход «замкнутость относительно дополнения» и доказал, что M' определяет дополнение L1 (~L1).

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

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


closures turing-machines
person skerr4311    schedule 14.05.2019    source источник
comment
~L1 не L2 or ~L2. ~L2 содержит L1: L2 равно number of 1s > number of 0s, поэтому ~L2 равно number of 1s <= number of 0s. Дополнением > является <=, а не <.   -  person Welbog    schedule 14.05.2019

Ответы (1)


arrow_upward
0
arrow_downward

Я просто хочу конкретизировать ответ Wellbog. Вот L1 (прочитайте n1(w) как «количество единиц в w»):

L1 = {w∈ {0,1}*: n1(w) = n0(w)}

А вот Л2:

L2 = {w∈ {0,1}*: n1(w) > n0(w)}

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

L1-bar = {w∈ {0,1}*: n1(w) > n0(w) ИЛИ n1(ш) ‹ n0(ш)}

И понятно, что L1-bar и L2 разные.

person Ahmad    schedule 10.06.2019