Неразрешимые задачи

Привет! Сегодня я хочу обзорно пройтись по нескольким задачам времен рассвета информатики aka Сomputer Science, которые относятся к неразрешимым.

Что такое неразрешимая задача? Наверное, стоило бы начать с иерархии Хомского — регулярные, контекстно-свободные, контекстно-зависимые, рекурсивно-перечислимые языки, — а уже потом перейти к тому, что лежит за её пределами, но, честно, это не слишком весело. Я не буду давать ни формальных определений, ни доказательств. У вас не получится поддержать научный диспут, но ввернуть умную фразу в компании — вполне. Если вас это устраивает — прошу под кат.

И снова, что такое неразрешимые задачи и чем они отличаются от NP-полных? Для NP-полных задач всегда существует долгий, но очевидный алгоритм полного перебора. Перед неразрешимыми пасует и он. Либо перебирать нечего, либо непонятно, что делать с тем, что мы перебираем.

Надо понимать, что в обоих категориях встречаются задачи, достаточно важные на практике — транспортным компаниям нужно знать хорошие маршруты, даже если они оказываются на 10% длиннее оптимальных, а покупателям Матлаба важно получить читабельный ответ к дифференциальному уравнению. В обоих случаях получается достаточно шустро находить приемлимые решения, но математики — перфекционисты, и способ, которым это достигается их не устраивает. Помня об этом и следует продолжать чтение статьи.

Начнем с самой известной.

Проблема остановки

Формулировка её достаточно проста.

Для данной машины Тьюринга и её конфигурации определить, закончит ли она когда-нибудь свою работу.

Что такое машина Тьюринга и что такое конфигурация? В сущности, плевать. Чтобы расширить ЦА статьи с категории «мехматовцы, которые и так это всё это знают, но всё-равно зачем-то прочитают» до какой-нибудь более широкой, переформулирую задачу более обыденно:

Для данной функции на Си-подобном языке и для данных входных данных определить, не зависнет ли она при выполнении.

Давайте попробуем самый очевидный способ. Запустим программу. Если она быстро завершилась, то нам повезло. В противном случае, всё усложняется. Как отличить ситуацию, когда функция просто выполняется очень долго от ситуации, когда она зацикливается и топчется на месте? Есть задачи, которые придется считать до конца жизненного цикла Вселенной, но они, тем не менее, решаемы в принципе. Для начала, попробуем отследить, как меняется состояние компьютера по мере исполнения программы. Самый простой случай — это циклы вида

 while (true) {}

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

For (int j = 0; j < 10; ++i){}

Я не пытаюсь ничего оптимизировать префиксным инкрементом. Просто этот вариант выглядит, как минимум, на 20% эстетичнее классического.

Одна маленькая опечатка делает подход, который работает в предыдущем варианте, бесполезным. Меняется еще, как минимум, одна переменная. Если судить только содержанию памяти программы, то мы сможем обнаружить зацикленность алгоритма только когда переменная i вернется в первоначальное состояние из-за арифметического переполнения. Всё это время состояние компьютера нужно будет сохранять после каждого такта процессора и после каждого же такта проверять, не вернулись ли мы в какое-то старое состояние, хотя это уже не сильно страшно в контексте.

И, наконец, строки, окончательно вынуждающие сложить лапки.

Int a;
For (int j = 0; j < 10; ++i){
	a = new Int;
}

Здесь не спасет даже арифметическое переполнение — «а» каждый раз будет ссылаться на какой-то новый объект, а если в языке есть сборщик мусора, то даже надежды получить однажды нулевой указатель не остается.

Итак, анализировать память даже в случае тупейших циклов, которые ничего не делают, оказывается бесполезно. Значит, нужно анализировать сами программы. Но отвлечемся.

Что мы могли бы сделать, будь у нас готовый алгоритм? Если говорить о чем-то абстрактном, то, например, мы могли бы легко и просто доказывать теоремы типа Большой Теоремы Ферма. Посмотрим на строки:

for (x in [1 .. infinity])
	for (y in [1 .. infinity])
		for (z in [1 .. infinity])
			for (n in [3 .. infinity])
				if (x ^ n + y ^ n == z ^ n)
					return (x,y,z,n)

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

Текст задачи можно также переписать как «программа никогда не вызовет исключения» или «в программе никогда не возникнет переполнения или разыменования нулевого указателя» без потери смысла. Что делают статические анализаторы? Они ищут самые распространенные шаблоны ошибок в коде и призывают немного помедитировать над определенными строками. Разрешимость задачи останова не сняла бы все проблемы команды PVS-studio, но определенно была бы им полезна. Понятно, что никто из разработчиков подобных инструментов не задавался целью решать фундаментальные задачи информатики, но возможно ли это таким способом? Очевидно, нет. Конструкций в языках программирования бесконечное число, и под каждую шаблон не подберешь.

Колмогоровская сложность

В этой задаче, речь идет об идеальном архиваторе:

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

Возьмем текстовый файл, который содержит 100 миллионов букв «a» в ASCII. Его размер около 100 мегабайт. Попробуем сжать обычным zip. Результат — около 100 килобайт. Даже с учетом того, что вместе с архивом придется передать программу программу-архиватор, размер получается вполне приемлимым для передачи по dial-up на случай, если у товарища на клавиатуре сломалась клавиша A. Но ведь явно можно добиться лучших результатов! Конкретно этот файл был получен крохотной программой размером в шесть строк.

#include <stdio.h> 
int main(){ 
	for (int i = 0; i < 100000000; ++i) 
		printf("a"); 
	return 0; 
} 

Я даже не удивлюсь, что тоже самое можно написать в 20 символов с учетом инклуда, но, в принципе, это довольно близко к решению данной задачи для конкретной простой строки.

Рассмотрим файл такого плана:

Всего такой абракадабры набралось на 50 мегабайт. Сжатие тем же zip дало уменьшение размера всего-лишь в 2 раза. Это разочаровывает, учитывая, что сгенерирован файл чуть более длинной программой, чем предыдущий:

#include <stdio.h> 
int main(){ 
	int a = 35; 
	for (int i = 0; i < 50000000; ++i){ 
		printf("%c", 'a' + a % 26); 
		a = ((a + 76) * 91) % 4534534; 
	} 
return 0; 
} 

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

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

Можно действовать следующим образом. Любой файл на жестком диске можно представить как обычное многобайтовое число. Так давайте мы будем перебирать все числа от 0 до бесконечности и пытаться интерпретировать файлы как исполняемые. Таким образом, мы, в один прекрасный момент, неизбежно натолкнемся на что-то, что запускается и делает то, что нам нужно.

Но проблема всё та же. Как определить, что программа не зависла, а просто выполняет очень сложную операцию? Выполнение можно прервать досрочно, но тогда нельзя быть уверенным, что мы не отказались от самого оптимального варианта.

Равенство алгебраического выражения нулю

Вы не поверите, но задача звучит так:

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

Очевидно, что к этой же задаче сводится та же задача для любого другого конкретного числа.
Допустим вы реализуете символьное дифференцирование выражения 3 * sin(x).
Если подходить формально, т. е по формулам (v*w)' = v'*w + v*w' и (v(w))' = v'(w) * w', то у вас получится что-то такое:

0 * sin(x) + 3 * cos(x) * 1

Это «немножко» неудобно читать, при том, что функция элементарнейшая. Очевидно, что результат надо упрощать. Это сложно. Наверняка про это написано десятки диссертаций, некоторые из которых даже к информатике непонятно как относятся. Однако, сводится всё опять к перебору шаблонов. Среди тонны прочих правил, вам обязательно понадобятся следующие:

• Если в произведении один из множителей равен единице, то нужно оставить второй множитель.
• Если в сумме одно из слагаемых равно 0, то нужно оставить второе слагаемое.

Эти два правила должны успешно справиться с моим примером с дифференцированием, ибо то, что 0 = 0 или 1 = 1 даже проверять не нужно. Но что, если мы возьмем выражение (sin^2 (x))/(1-cos^2 (x))?

По основному тригонометрическому тождеству, числитель и знаменатель выражения равны. Человек это увидит сразу и смело напишет единицу. Компьютер придется этому научить. И, думаю, уже понятно, что про каждый такой шаблон программе придется рассказать отдельно. Всё, что нужно, чтобы написать свой клон Wolfram Alpha есть в одной не самой толстой книге. А вот сделать так, чтобы на просьбу сложить два числа, результатом не был бесконечный ряд — это уже и и есть то, из-за чего полнофукциональный пакет стоит таких денег.

На этом всё. Надеюсь, вы узнали что-то интересное. Понятно, что нас не слишком интересует, скажем, решение задачи о Колмогоровской сложности. Нас вполне устраивает необходимость для сжатия текстов иметь формат bzip2, для видео — MPEG4, а для картинок JPEG и только JPEG. Да и то, что операционная система определяет зависание приложений каким-то несовершенным способом мало кого колышет. Статьей мне хотелось бы продемонстрировать разницу между математическим и инженерным направлением мысли. Математическое стремится охватить общую картину, а инженерное фокусируется на том, чтобы находить решения, невзирая на теоретическую красоту. Без первого мы бы не смогли двигаться вперед, а без второго мир, который мы знаем, просто не мог бы существовать.

Автор: Salabar

Источник