Обсуждение участницы:Анна

Доказательство того, что следующие языки неразрешимы:

1. [math]A_{TM} = \{ (M, w) \mid M - [/math] машина Тьюринга, допускающая строку [math]w \}[/math]
2. [math]L_{TM} = \{ (M, w) \mid M - [/math] машина Тьюринга, допускающая строку [math]w^R[/math] и не допускающая строку [math]w \}[/math]
3. [math]A\varepsilon_{TM} = \{ M \mid M - [/math] машина Тьюринга, допускающая [math]\varepsilon \}[/math]
4. [math]R_{TM} = \{ M \mid M - [/math] машина Тьюринга и [math]L(M) - [/math] регулярный [math] \}[/math]
5. [math]E_{TM} = \{ M \mid M - [/math] машина Тьюринга и [math]L(M) = \varnothing \}[/math]