29
правок
Изменения
м
→Неразрешимость языка ПСП
{{Определение
|definition=
Назовём '''снимкомсостояния [[Машина Тьюринга|МТ]]''' состояния МТ строку вида <tex>c_1 c_2 \dots c_k \#_p c_{k+1} \dots c_t</tex>, где <tex>c_1 c_2 \dots c_t</tex> — строка на ленте, за исключением бесконечных последовательностей пробелов слева и справа, <tex>p</tex> — текущее состояние автомата МТ, головка расположена справа от <tex>\#_p</tex>.
}}
Построим списки <tex>A</tex> и <tex>B</tex> таким образом, чтобы решение МПСП образовывало строку
