Изменения

Примеры неразрешимых задач: проблема соответствий Поста

205 байт убрано, 00:02, 2 января 2015

→‎Перечислимость языка ПСП

Таким образом, язык пар последовательностей, для которых существует решение ПСП, полуразрешим, а значит, перечислим.

}}

Для МПСП доказательство перечислимости имеющих решение пар аналогично, но перебор индексов ведётся с <tex>i_2</tex>.

== Неразрешимость языка ПСП ==

29

правок