Здравствуйте!
Вообще-то я хотел вести блог про бенчмарки, многопоточность и хадуп. Но первый пост я всё-таки напишу про математику. Дело в том, что я целый день восхищаюсь задачкой и мне очень хочется ей поделиться.
Должен отметить, что математику я не знаю и являюсь дилетантом. Поэтому все определения и доказательства будут грубыми, неточными, не очень формальными и пропущенными через программистский мозг.
Понятие вычислимости
Еще в древности люди придумывали, как решить ту или иную задачу, и решение прописывали в виде шагов, которые надо проделать. Такая последовательность шагов называется «алгоритм». Но это неформальное определение алгритма (ладно, это не определение, а вoобще фигня какая-то :). Формализовать же понятие «алгоритм», оказалось не так-то просто. Этой проблемой занимались в первой половине XX века великие математики и логики, отцы всей компьютерной науки.Так Алан Тьюринг разработал формальную систему, которая называется «машина Тьюринга» (МТ). А Курт Гёдель ввел формализм «частично рекурсивные функции»(ЧРФ). Обе эти модели являются попыткой математически формализовать понятие «алгоритм». Я не буду рассматривать эти модели в данной статье, скажу одно: было доказано, что все задачи, которые можно решить с помощью одной модели, можно решить с помощью другой. Теорема о том, что классы задач, решаемых с помощью машины Тьюринга и с помощью частично рекурсивных функций, совпадают, называется тезисом Тьюринга-Чёрча.
Замечания
- Интуитивно, и МТ и ЧРФ похожи на языки программирования (а может и являются ими). И если я ничего не напутал, то доказательство тезиса Тьюринга-Чёрча сводится к разработке интерпретатора программ для ЧРФ на МТ и наоборот. Действительно, если мы на языке $A$ написали интерпретатор языка $B$, то все задачи, решаемые с помощью языка $B$, решаются с помощью языка $A$. Тогда говорят, что язык $A$ не менее мощный, чем язык $B$.
- Большинство современных языков программирования, начиная с ассемблера, заканчивая скалой, обладают Тьюринговой полнотой, т.е. класс задач, которые можно решить с помощью любого языка, совпадает с классом задач, решаемых с помощью МТ.
Bозникает вопрос: а для всех ли формально поставленных задач можно составить алгоритм решения?
Оказывается, существуют такие функции, которые полностью определены на допустимых параметрах, но для которых невозможно составить алгоритм вычисления. Такие функции называются невычислимыми. Те же функции, для которых существует алгоритм, называются вычислимыми.
Рассмотрим самую знаменитую невычислимую функцию, с которой и пошла теория вычислимости.
Задача об остановке
Фух, ну и введеньице...
Итак, задача: Можно ли составить компьютерную программу, которая принимает текст любой программы и входные данные этой программы, и на выходе дает ответ, остановится ли программа, полученная на вход, или зациклится?
По-моему сама проблема уже прекрасна. Такую программу написать нельзя. Доказательство этого факта очень простое, короткое и неожиданное. Я надеюсь вы получите от него удовольствие.
Понятно, что и программа и входные данные являются просто числами (и то и другое просто нули и единицы). Т.е. все существующие программы можно пронумеровать. То же относится и к данным. И по этому номеру можно получить текст программы.
Тогда определим функцию
$$ s(p, d) = \left\{ \begin{array}[h]{cl} 1 && \text{если } \begin{array}[t]{l} p \text{ не является номером синтаксически допустимой программы } \\ || d - \text{ не является номером данных, которые можно подать на вход программмы } p \\ || \text{ программа } p \text{ завершится за конечное время, получив на вход данные } d \end{array}\\ 0 && \text{если программа } p \text{ зацикливается, получив на вход данные } d \end{array} \right . $$Очевидно, что $s(p, d)$ определена на $p,d \in N$. Тем не менее $s(p,d)$ невычислима.
Докажем от противного. Допустим мы написали программу stops?(program, data), которая вычисляет $s(p,d)$. Тогда напишем программу try(program), которая вызывает внутри себя программу stops?
def try(program)
if (stops?(program, program))
while(true)
end
end
Фух. Дальше: пусть TRY - текст программы try(program). Что произойдет, если мы вызовем try(TRY)?
Понятно, что программа либо завершается либо зацикливается. Рассмотрим оба варианта. Если вызов try(TRY) завершается, то программа должна зациклиться. Противоречие. Если же он зацикливается, то она должна завершиться. Опять противоречие. Следовательно программу stops?(program, data) невозможно написать. QED
По-моему круто!
Замечания
- В данном доказательстве мы рассматриваем алгоритм как компьютерную программу, что позволяет показать интуицию этого доказательства, но имеет определенные проблемы. Известно, что в программу можно очень по разному передать входные данные. Тогда возникают вопросы: что такое входные данные и что значит выполнить программу на входных данных в нашем доказательстве? Исходное доказательство Алана Тьюринга гораздо более строгое и не имеет этих проблем. Но тем не менее, основная идея того доказательства такая же как и здесь.
- В книжке СИКП, проблема вычислимости обсуждается в параграфе 4.1.5. Идеи доказательства теоремы об остановке даются в упражнении 4.15. Если вы еще не читали эту книгу, обязательно прочитайте!
Последовательности нулей в числе $\pi$
Ради этой проблемы я статью и написал. Я нашел ее на cs.stackexchange.com, а точнее у antilamer'a.
Рассмотрим такую функцию:
$$ f(n) = \left\{ \begin{array}[h]{cl} 1 && \text{если в десятичном представлении числа } \pi \text{ встречается } 0^n \\ 0 && \text{ в ином случае } \end{array} \right . $$Докажем, что она вычислима.
Вообще, мы ничего не знаем про структуру числа $\pi$. Википедия говорит, что даже неизвестно, какие цифры встречаются в нем конечное число раз, а какие - бесконечное. Тем не менее $f(n)$ вычислимо.
Очевидно, в цифровом представлении $\pi$ либо встречается бесконечная последовательность нулей, либо есть самая длинная последоватльность нулей, возможно пустая.
В первом случае $f(n) = 1$ для всех $n$
Во втором случае $f(n)$ вычисляется тривиально:
def f(n)
if (n <= N)
return 1
else
return 0
end
end
где $N$ - длина этой самой длинной последовательности. QED
Еще раз. Число $N$ однозначно определенно (в первом случае можно считать $N = \infty$). Только никто не знает, чему оно равно. Вот и получается, мы доказали, что алгоритм вычисления $f(n)$ существует, а найти его мы один фиг не можем.
По-моему классная задачка!
Мега-бонус
Машина Тьюринга из Lego:
