Лекция 4. Понятие алгоритмической разрешимости

§ 4.1. Алгоритмически неразрешимые задачи

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

Да­лее будут рас­смо­трены при­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых про­блем и до­ка­за­те­ль­ст­ва их нераз­ре­ши­мо­сти. Вна­ча­ле от­ме­тим, что до­ка­за­те­ль­ст­вам не­воз­мо­жнос­ти, при­во­ди­мым в те­ории ал­го­рит­мов, при­су­ща та же ма­те­ма­ти­че­с­кая стро­гость, что и до­ка­за­те­ль­ст­вам не­воз­мо­жнос­ти, про­во­ди­мым в дру­гих об­лас­тях ма­те­ма­ти­ки.

Су­ще­ст­ву­ют два ме­то­да до­ка­за­те­ль­ст­ва не­раз­ре­ши­мо­сти.

Пер­вый, пря­мой ме­тод, со­сто­ит в том, что исходя из пред­по­ло­же­ния о раз­ре­ши­мо­сти дан­ной про­бле­мы, путем набора логических преобразований (переходов) мы при­хо­дим к про­ти­во­ре­чию с доказанными ранее утверждениями либо с элементарной логикой (со здравым смыслом).

Вто­рой, кос­вен­ный ме­тод (на­зы­ва­емый ещё ме­то­дом све­де­ния) со­сто­ит в сле­ду­ющем. По­ка­зы­ва­ет­ся, что раз­ре­ши­мость ис­сле­ду­емой про­бле­мы вле­чёт раз­ре­ши­мость про­бле­мы, о ко­то­рой уже из­ве­ст­но, что она не­раз­ре­ши­ма. Ме­тод све­де­ния час­то бы­ва­ет бо­лее удоб­ным, чем пря­мой ме­тод.

Первый метод используется вообще достаточно широко в доказательстве теорем различного типа. В общем виде он называется reductio ad absurdum - доказательство «от противного». Это один из самых часто используемых методов доказательства утверждений. Доказательство утверждения A проводится следующим образом. Сначала принимают предположение, что утверждение A неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение B, которое заведомо неверно. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение «отрицание отрицания А», которое по закону двойного отрицания равносильно утверждению A.

Кроме этого, во многих доказательствах применяется так называемая апагогия (греч. лат. deductio) - логический прием, которым доказывается несостоятельность какого-нибудь мнения таким образом, что или в нем самом, или же в необходимо из него вытекающих следствиях, мы открываем противоречие. Поэтому апагогическое доказательство является доказательством косвенным: здесь доказывающий обращается сперва к противоположному положению, чтобы показать его несостоятельность, и затем по закону исключения третьего делает вывод о справедливости того, что требовалось доказать. Этот род доказательства называется также приведением к нелепости: deductio ad absurdum. Существенной его принадлежностью является довод, что третье не существует: tertium non datur, т. е., что кроме мнения, справедливость которого должно доказать, и второго, ему противоположного, которое служит исходным пунктом доказательства, никакой третий факт не допускается. Поэтому косвенное доказательство исходит из факта, противоречащего положению, справедливость которого требуется доказать.