Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | Доказательство того, что следующие языки неразрешимы:
| + | |
| − | # <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>
| |
Версия 01:00, 24 декабря 2016
