Проблема будущего

gatoazul — 07.02.2025 Одна из фундаментальных вещей информатики - это проблема останова. Возможно ли написать такую программу, которая проверит другую программу и скажет, зависнет та или нет. Ответ на этот вопрос в общем случае отрицательный, увы. Такую программу сочинить невозможно. Не сейчас, а в принципе.

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

function will_halt(fun):boolean
{
  // тут идут миллионы строк хитрейшего алгоритма
}

А теперь напишем такую программу-обманщицу:

function deceiver()
{
  if (!will_halt(deceiver))
  {
    while(1);
  }
}

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

Но ведь ровно тот же ход рассуждений объясняет, почему в общем случае невозможно предсказывать будущее! Потому что если у нас есть предсказание, мы можем сделать все наоборот, так, чтобы оно стало неверным.

В художественной литературе, начиная с "Царя Эдипа", конечно, любят опровергать эту идею, показывая, как именно что попытки избежать предсказания позволяют ему сбыться. Но это не более, чем литературный прием, искусственное подыгрывание, хотя и поражающее воображение читателя.

Впрочем, есть один вариант: сделать предсказание так, чтобы о нем не знал никто - или по крайней мере, не знали заинтересованные лица. Аналог в случае программ - запретить программа проверять самих себя. Скорее всего, и это не поможет, потому что проблема останова фундаментальна, но интересно было бы увидеть ее доказательство с учетом такого ограничения.

Оставить комментарий

Популярные посты:

• Ранее
• Архив