Използване на резултати от затваряне за разрешими по Тюринг езици

Имам език L1 = {w в {0,1}*| w съдържа същия брой 1 и 0} и имам TM M, който решава L1.

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

Използвал съм подхода "затворен под допълнение" и съм доказал, че 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) като "брой 1 в w"):

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

И ето го L2:

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

От другата страна L1-лентата е:

L1-лента = {w∈ {0,1}*: n1(w) > n0(w) ИЛИ n1(w) ‹ n0(w)}

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

person Ahmad    schedule 10.06.2019