Информатика




Информатика
Алгоритмическая неразрешимость - Понятие математической логики, означающее, что существуют задачи, для решения которых невозможно в принципе построить алгоритм. Для того чтобы доказать алгоритмическую неразрешимость каких-либо задач, необходимо было уточнить понятие алгоритма, сделать его математически строгим. Математически строгие понятия алгоритма существуют. Это машина Поста, машина Тьюринга, нормальный алгоритм Маркова и пр. Доказательства неразрешимости какой-либо задачи, в большинстве случаев, очень сложны. Приведем формулировку классической алгоритмически неразрешимой задачи: десятой проблемы Гильберта. Задано произвольное алгебраическое уравнение с целыми коэффициентами, надо определить, существует ли у данного уравнения решение в целых числах. Через 70 лет после постановки задачи, в 1970 г., математик Ю. Матиясевич (СССР) доказал невозможность разработки алгоритма, который бы решал эту задачу. Ясна практическая ценность введения понятия «алгоритмическая неразрешимость»: задачи, для которых доказана алгоритмическая неразрешимость, не надо и пытаться решать на компьютере.

Заказать работу



наверх страницынаверх страницы на верх страницы





© Библиотека учебной и научной литературы, 2012-2016 Рейтинг@Mail.ru Яндекс цитирования