8_1 (1019126), страница 3
Текст из файла (страница 3)
Впервые Курт Гедель в 1931 году представил строго сформулированную математическую проблему, для которой не существует решающего ее алгоритма. Сам по себе этот факт является удивительным, однако он имеет также большое практическое значение. Для проблем, алгоритмическая неразрешимость которых доказана, бессмысленно искать методы их решения точно так же, как бессмысленны поиски вечного двигателя. Оказалось, что таких алгоритмически неразрешимых проблем много, например, не существует алгоритма проверки общезначимости логической формулы в логике предикатов. Мы сейчас сформулируем одну из таких проблем и докажем ее алгоритмическую неразрешимость. Эта проблема известна как «проблема останова». Она состоит в том, что не существует алгоритма, позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
