Понедельник, 24.07.2017, 21:47
ОТКРЫТАЯ ИНФОРМАТИКА
Приветствую Вас Гость | RSS
Главная Алгоритмически неразрешимые задачи Регистрация Вход
Меню сайта

Форма входа

Поиск

Календарь
«  Июль 2017  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930
31

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

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

Вычислимая функция - это функция, для вычисления которой существует алгоритм.

Любая вычислимая функция может задаваться разными алгоритмами (разными программами для выбранного универсального исполнителя).

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

Существуют и невычислимые функции.
Рассмотрим простой пример, предложенный В.А. Успенским в книге "Машина Поста”. Известно, что математическая постоянная πи — иррациональное число, его десятичная запись бесконечна и не периодична. Введем функцию h(n), которая для любого натурального числа n равна 1, если в десятичной записи числа π есть n стоящих подряд девяток, окруженных другими цифрами, и равна нулю, если такой цепочки девяток нет. Как вычислить значение этой функции при некотором заданном n?

Конечно, можно вычислять друг за другом десятичные знаки числа π (такие алгоритмы математикам известны!) и проверять, не нашлась ли в полученной последовательности цифр цепочка из n девяток. С помощью такого "наивного” алгоритма можно найти такие значения n, при которых h(n) = 1: обнаружив требуемую цепочку, алгоритм закончит работу. Например, анализ первых 800 знаков показывает, что h(n) = 1 при n = 0, 1, 2, 6. Но если для какого-то n функция h(n) равна нулю, то наивный алгоритм никогда не остановится. Более того, для этой функции вообще не существует алгоритма, который при любом n останавливается и выдает значение h(n) в качестве результата. Поэтому такая функция невычислима.

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

Поскольку алгоритм работает только с дискретными объектами, любая алгоритмическая задача — это функция, заданная на множестве дискретных объектов (входных слов).

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

Если определенная в задаче функция невычислима, то алгоритма для ее решения не существует. Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.

В 1900 году на Международном математическом конгрессе в Париже известный математик Давид Гильберт сформулировал 23 нерешенные математические проблемы.


Вопросы:

1. Что такое вычислимая функция?
2. Приведите пример невычислимой функции.
3. Что такое алгоритмически неразрешимые задачи? Приведите известные вам примеры.
4. Что такое "проблема останова”? Каковы ее следствия?
5. Что такое "проблема эквивалентности”?
6. Как обычно доказывается алгоритмическая неразрешимость новых задач?

Использованная литература:
1. Журнал "Информатика". "Алгоритм - понятие неопределяемое? Основы теории алгоритмов". К.Ю. Поляков, Е.А Еремин
Наш опрос
Сколько времени вы обычно проводите за комьпютером?
Всего ответов: 950

Друзья сайта
  • Министерство образования РБ
  • Официальный портал подготовки к ГИА и ЕГЭ
  • Всероссийская олимпиада школьников
  • Федеральный портал Российского образования
  • Институт развития образования РБ

  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0

    Copyright MyCorp © 2017 Бесплатный конструктор сайтов - uCoz