577
правок
Изменения
Нет описания правки
Доказательство того, что следующие языки неразрешимы:# <tex>A_{TM} = \{ (M, w) \mid M - </tex> машина Тьюринга, допускающая строку <tex>w \}</tex> # <tex>L_{TM} = \{ (M, w) \mid M - </tex> машина Тьюринга, допускающая строку <tex>w^R</tex> и не допускающая строку <tex>w \}</tex># <tex>A\varepsilon_{TM} = \{ M \mid M - </tex> машина Тьюринга, допускающая <tex>\varepsilon \}</tex># <tex>R_{TM} = \{ M \mid M - </tex> машина Тьюринга и <tex>L(M) - </tex> регулярный <tex> \}</tex># <tex>E_{TM} = \{ M \mid M - </tex> машина Тьюринга и <tex>L(M) = \varnothing \}</tex>
