Последнее время (начало 2009 года) мне довелось принять участие в обсуждении различных способов организации грамматического разбора (спасибо habrahabr). Эти обсуждения натолкнули меня на мысль о том, что очень многие программисты склонны разделять существующие задачи на сложные и простые. Они (программисты) находятся во власти наивных иллюзий, что любую задачу можно решить, надо только найти алгоритм. Из-за этого большинству даже не приходит в голову, что задачи можно (и нужно!) систематизировать; очень часто безосновательно делаются очень общие высказывания; неуместно используются слова «всегда», «никогда», «любой»; используются наивные характеристики типа «достаточно сложный». Всё это подтолкнуло меня к написанию заметки о неразрешимых задачах.

Формулировка проблемы остановки
Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет).

Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращать F(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно.

По сути, F(A, D) должна проанализировать строку.
Зачем решать задачу остановки?

Приведу один пример.

Всем, кто знаком с задачами криптографии, известно, какую важную роль в этой дисциплине играют простые числа Мерсенна. Человечество прилагает множество усилий по поиску этих чисел. Последнее (пока самое больше) было обнаружено 6 сентября 2008 года и насчитывало 11 185 272 десятичных знаков. И прямо сейчас десятки тысяч процессоров работают над поиском новых чисел.

Числа Мерсенна напрямую связаны с совершенными числами. Все эти числа пока таят множество загадок (во многом поэтому они и используются для шифрования и сокрытия информации), но мне хотелось бы остановиться только на совершенных числах.

Совершенные числа — это такие числа, сумма всех делителей которых равна самому числу. Например 6 делится на 1, 2 и 3; 1+2+3=6. 6 — совершенное число. 28 тоже совершенное число. Не смотря на то, что эти числа активно изучаются теоретиками и на их поиски брошены колоссальные вычислительные мощности, пока так и не понятно, сколько этих чисел, ограниченно ли их количество и существуют ли нечётные совершенные числа.

Гипотезы о не-существовании нечётных совершенных чисел и о бесконечном их количестве считаются одними из гипотез, особо остро требующих доказательства или опровержений.

Программу, которая ищет совершенные числа написать очень просто. Вот пример кода на Python:

#!/usr/local/bin/python

def perfect_number():
for n in xrange(1, 500):
if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n:
print «%5d is perfect number» % n

perfect_number()

Строго говоря, искать совершенные числа можно и более рациональными способами, но все они сводятся к перебору. Просто можно перебирать не все подряд числа.

Можно написать функцию, которая ищет совершенное число среди нечётных. Сделать это очень просто:

def odd_perfect_number():
n = 1
while True:
if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n:
return «OK! I FIND IT!»
n += 2

Эта функция завершит работу только если найдётся нечётное совершенное число.

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

На сегодняшний день доказано, что первое нечётное совершенное число должно быть больше, чем 10300. Перебор не обнаружил таких чисел, дойдя до 10500.

Это далеко не единственный вопрос, который легко решился бы сразу, как только мы получили бы решение проблемы остановки.

Точно таким же способом можно было бы доказать или опровергнуть очень многие гипотезы современной математики. Например, гипотезу Биля, за которую даже назначена награда в 100 000 долларов США.

Но проблема остановки неразрешима.
Доказательство неразрешимости проблемы остановки

На мой взгляд, программист, на каком бы языке он не программировал бы и какие задачи бы не решал, проходит в своём развитии три стадии. На первой он умеет очень мало и большинство задач кажутся ему запредельно сложными. На этом этапе он слеп. Он не видит решений, даже если они лежат на виду. Когда он набирается опыта у него появляется определённый кураж и он начинает считать все задачи разрешимыми. Он видит до самого горизонта и ему кажется, что он видит всё, знает всё и может всё. Я много раз видел, как программисты берутся за задачи, которые либо нельзя решить вовсе, либо нельзя решить теми средствами, которые они собираются применять. Но когда он набирается не только опыта, но и знаний, он начинает понимать как велик мир. В нём есть залитые светом равнины и пещеры в которые никогда не проникает солнце…

Неразрешимость проблемы остановки имеет много доказательств. В терминах функций её очень просто доказать от противного.

Допустим, у нас уже есть решение — функция F, которая принимает на вход некую функцию (вернее строку с текстом функции, байт-кодом или иной записью функции) и некие данные и отвечает на вопрос: «остановится ли функция-первый-аргумент, при работе с данными-вторым-аргументом, или будет работать вечно?»

Давайте создадим функцию P(x), такого вида (на C-образном языке):

P(x) {
if F(x,x) then { for(;;) }
}

Строку, которая кодирует эту функцию обозначим p. Что будет, если мы вызовем функцию F(p,p)? Возможны два исхода:

• True, если если P останавливается. Но при этом P(p) как раз не останавливается, если F(p,p)=True, то запускается бесконечный цикл.
• False, если P зависает. Но, как не трудно видеть, именно в этом случае P(p) не зависнет.

Мы получили противоречие потому, что наша начальная посылка о существовании магической функции F была не правильной.

Получается, что задача останова неразрешима. Вернее, нельзя написать программу, которая бы решала эту задачу. Иными словами, нельзя написать парсер программного кода, который бы мог оценить, зависнет разбираемый код или нет.

Неразрешимость проблемы остановки была впервые доказана в 1936 году Аланом Матисоном Тьюрингом (Alan Mathison Turing; 1912-1954).
Проблем, подобных проблеме остановки, великое множество

Проблема остановки только одна из множества так называемых массовых проблем. Эти проблемы существуют не только в теории алгоритмов, но и в математической логике. В алгебре такой проблемой является например проблема Туэ (о равенстве конечнопорождённых и конечноопределённых полугрупп). Одна из наиболее известных математических проблем для которой доказана алгоритмическая неразрешимость — десятая проблема Гильберта (кстати, доказал это наш соотечественник Юрий Владимирович Матиясевич).

Комментарии запрещены.