Математика и секс
Июнь 22nd, 2014

Невычислимое, недоказуемое

Предположим, что у нас есть какое-то логическое утверждение, зависящее от натурального числа $$P(n)$$. Это утверждение, предположим, можно легко проверить для любого конкретного числа, но не понятно верно ли оно для любого числа.

Например, можно рассмотреть гипотезу Гольдбаха о том, что любое чётное число может быть представлено в виде суммы двух простых чисел (так, например, $$50=19+31$$ или $$100=11+89$$). Для любого конкретного чётного числа можно довольно легко перебором подобрать его разложение на сумму двух простых чисел. По крайней мере всегда у людей это получалось. А вот возможно ли это сделать в общем случае, то если получится ли представить в виде суммы двух простых вообще любое чётное число — вопрос, на который наука пока не нашла ответа.

Или вот можно рассмотреть последовательности Коллатца. Начальный элемент последовательности — это произвольное натуральное число, которое мы обозначим как $$K_0$$. $$K_{n+1}$$ получается из $$K_n$$ по следующему правилу: если $$K_n$$ чётное, то $$K_{n+1}=\frac{K_n}{2}$$. Если $$K_n$$ нечётное, то $$K_{n+1} = 3K_n + 1$$. Например, если за $$K_0$$ принять число 15, то мы получаем следующую последовательность:
$$15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1$$
Как видим, последовательность пришла в единицу. До сих пор с какого бы числа люди не начинали писать последовательность Коллатца, она всегда приходит в единицу, но приходит ли она в единицу всегда, или всё же есть исключения — никто не знает, это открытый вопрос математики.

Интуитивно должно казаться ясным, что чтобы ответить на такие вопросы, не достаточно перебрать просто большое количество вариантов. В обоих упомянутых проблемах математики перебрали уйму чисел (фактически все числа, на которые хватило вычислительных возможностей), но примера, чтобы какое-то число не раскладывалось в сумму двух простых или чтобы последовательность Коллатца для него не приходила в единицу, так и не нашли. Доказывает ли это что-либо? Конечно нет, потому что чисел, которых математики не проверили, куда больше — их ещё целая бесконечность, а проверена лишь малая конечная часть.

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

Теорема. Для установления истинности почти любого утверждения $$P(n)$$ достаточно проверить лишь истинность конечного числа утверждений $$P(n)$$ для $$n$$ от 1 до некоторого $$M$$.

Доказательство. Давайте представим себя на минуточку программистами. Мы хотим найти такое число $$f\in\mathbb{N}$$, что $$P(f)$$ окажется неверным, то есть мы ищем контрпример к нашей гипотезе.

Будем считать, что мы можем написать программу для проверки утверждения $$P$$ для любого конкретного номера (это предположение и составляет значение слова «почти» в формулировке теоремы). Напишем программу, которая будем перебирать все числа подряд начиная единицей и которая остановится лишь когда она найдёт такое $$f\in\mathbb{N}$$, что $$P(f)$$ не выполняется. Возможно, что мы не найдём его никогда и тогда программа будет работать бесконечно долго, а это значит, что у нас есть время попить чай и поразмышлять.

Код нашей программы имеет конечную длину, обозначим её N. Если рассмотреть все возможные программы длины $$N$$, то среди них найдутся конечно же те, которые будут работать бесконечно долго (можно сказать, что они «зависнут») и те, которые в итоге остановятся. Обозначим за $$B_N$$ самое долгое время работы программы длины $$N$$ (на английском эти числа называются Busy Beaver Numbers по фольклорным причинам, а как это адекватно переводится на русский я и не знаю). Как вычислить это самое $$B_N$$ не очень понятно, но такое число вполне определено. Предположим пока, что мы его знаем.

Посмотрим на часы, сколько уже работает наша программа по поиску контрпримера, пока мы пили чай? Что? Уже дольше, чем $$B_N$$? Но ведь $$B_N$$ это самое долгое время, которое может работать программа, которая останавливастся. Значит мы знаем, что программа не остановится уже никогда, то есть контрпример не будет найден. Утверждение об истинности $$P$$ можно считать доказанным, программу можно выключать.

Конечно же, наша программа за конечное время $$B_N$$ успела проверить лишь конечное число вариантов от 1 до некоторого $$M$$, но из рассуждений, приведенных выше, следует, что нам этого каким-то образом оказалось достаточно для того, чтобы утверждать об истинности $$P$$ для совсем любого $$n$$. В чём тут подвох? Подвоха тут нет.
$$\square$$

Задумайтесь на секундочку: почти любой сложный вопрос математики, касающийся натуральных чисел, может быть установлен путём перебора конечного числа вариантов. Будь то теорема Ферма, гипотеза Гольдбаха, Коллатца или кого ещё: достаточно проверить конечное число случаев. Не знаю как вам, но на меня в своё время этот факт произвёл неизгладимое впечатление.

Насколько этот результат практичен? На самом деле совершенно не практичен. Во-первых, не понятно как вычислить значение $$B_N$$. Во-вторых, даже если мы его вычислим для какого-то $$N$$, то оно наверняка окажется настолько гигантским, что вряд ли поместится в наш калькулятор. Так что выгоды мы из этого всего извлечь судя по всему не сможем, увы. Но сам факт!

Логично было бы, если бы после изложения этого результата я тут же показал бы, как считать числа $$B_n$$, однако сейчас мы уйдём в сторону и я покажу как эти числа ещё можно было бы использовать, если бы они были в нашем распоряжении.

Попробуем написать такую программу, которая будет анализировать другую программу, и говорить нам о том, зависнет она или же нормально остановится. Можно рассматривать такую программу как функцию $$H:P\to\{0,1\}$$, где $$P$$ — множество всех возможных программ. 0 означает, что программа зависнет, 1 что остановится.

При условии, что мы можем написать программу, вычисляющую $$B_n$$, мы нашу задачу можем очень легко решить. Пусть нам дана программа $$x$$ длины $$n$$, для которой надо установить остановится ли она. Поскольку программа — это просто описание каких-то действий, мы можем заставить выполнять эти действия не компьютер, а нашу программу $$H$$, то есть мы как бы будем симулировать выполнение программы $$x$$ внутри программы $$H$$. Это не сложно технически, но я не буду углубляться в детали как это реализуется. Если вы знакомы с компьютерными технологиями, то наверняка слышали про интерпретаторы, виртуализацию, виртуальные машины и подобное. Это именно то, это возможно и это не особо сложно.

По ходу выполнения программы $$x$$, программа $$H$$ будет считать, как долго $$x$$ работает. Если вдруг окажется, что программа $$x$$ работает дольше, чем время $$B_n$$, то мы знаем, что она не закончится, и $$H$$ останавливает $$x$$, выдавая нам результат 0. Если же $$x$$ остановится сама раньше, то $$H$$ даст результат 1. Вроде всё.

А теперь давайте напишем такую программу $$A$$, которая так же будет принимать на вход какую-то другую программу $$x$$, затем будет запускать на ней программу $$H$$, и если $$H(x)=1$$, то $$A$$ будет зависать (например, начнёт считать все натуральные числа подряд), а если же $$H(x)=0$$, то она будет возвращать какой-то результат. Такую программу так же легко написать.

Попробуем понять какой результат мы получим, если на вход программе $$A$$ мы дадим её же саму, то есть попробуем выполнить $$A(A)$$. Что будет? Предположим, что $$H(A)=0$$, тогда программа $$A$$ должна завершиться, вернув результат. Но это противоречит тому, что $$H(A)=0$$. Из этого противоречия видно, что $$H(A)\not=0$$. Пусть теперь $$H(A)=1$$, но тогда $$A$$ должна зависнуть, что противоречит тому, что $$H(A)=1$$, а значит $$H(A)\not=1$$. Как так? $$H$$ оказывается не равно ни одному своему возможному значению!

Это противоречие означает, что программа $$H$$ не может быть написана, не существует такой программы и существовать не может. Но как так, ведь мы же чётко указали, как её можно написать! Если вглядеться, то при описании работы программы $$H$$ мы опирались на то, что мы можем как-то вычислить числа $$B_n$$, но мы не показывали этого. И это единственный момент во всём рассуждении, который мы никак не обосновали. Значит, числа $$B_n$$ вычислить невозможно.

Тот факт, что есть такая функция $$B$$, которая вполне определена, но которую невозможно вычислить, может показаться невероятным. На самом деле если подумать, то это довольно не сложно. Из определения функции $$B$$ мы могли бы попробовать вычислить $$B(n)$$, запустив одновременно все возможные программы длины $$n$$, и, заведя таймер, пытаясь понять, какое самое большое время работы программы. Однако с учетом того, что есть программы, которые зависают, мы никогда не узнаем, когда таймер пора выключать, хотя конечно же такой момент во времени существует. Это и есть пример того, что функцию невозможно вычислить.

Мы получили два результата.

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

Теорема. Числа $$B_n$$ невычислимы. Другими словами невозможно определить максимальное время, которое может работать независающая программа длины $$n$$.

Приведённые рассуждения можно вывернуть ещё и вот под каким углом. Напишем программу $$E$$, которая будет проверять истинность произвольного утверждения $$x$$ путём последовательного перебора всех возможных доказательств (программа может начинать с коротких доказательств и постепенно переходить к более длинным, так что такая программа определённо может быть написана). Если предположить, что всё можно доказать или опровергнуть, то через какое-то время наша программа либо найдёт доказательство для $$x$$, либо доказательство для $$\neg x$$.

Используя эту программу, однако, мы опять же легко можем написать пресловутую программу $$H$$ проверяющую, остановится ли программа $$y$$ или нет. Просто вместо запуска программы $$y$$ и ожидания времени $$B_n$$ мы на этот раз будем искать доказательство остановки или зависания $$y$$. Поскольку мы уже знаем, что программа $$H$$ не может существовать, наше предположение, что программа $$E$$ всегда либо найдёт доказательство $$x$$ либо $$\neg x$$ так же не верно. Это значит, что существуют такие утверждения $$x$$, которые невозможно ни доказать ни опровергнуть. Как вы вероятно помните, это есть ни что иное как теорема Гёделя о неполноте:

Теорема. Существуют утверждения, которые невозможно ни доказать ни опровергнуть.

Я упомянул, что числа $$B_n$$ окажутся скорее всего довольно большими. Оказывается, мы можем примерно прикинуть насколько именно большими они будут.

Теорема. Числа $$B_n$$ с ростом $$n$$ растут быстрее, чем любая последовательность, которую мы могли бы вычислить.

Доказательство. Предположим, что это не так, и что существует некоторая последовательность $$x_n$$ такая, что мы можем её вычислить и что $$B_n\le x_n$$. Но тогда мы можем запустить все программы длины $$n$$ и останавливать их как только они отработают время $$x_n$$. Среди программ, остановившихся раньше, выберем ту, что работала дольше. Время, которое она работала — это и есть $$B_n$$. Но это значит, что мы смогли их вычислить, а это противоречит теореме 3.51. Значит, такой последовательности $$x_n$$ всё же не существует.
$$\square$$

Упражнение. Если предположить, что мы имеем в нашем распоряжения числа $$B_n$$ и неограниченный вычислительный ресурс, проверка истинности произвольных утверждений может всё равно вызывать трудности. Гипотеза Коллатца является как раз таким примером. Если наша программа поиска контрпримера не остановилась за время $$B_n$$, то она не остановится действительно никогда, но это может иметь разное значение: либо она нашла такое $$m$$, что последовательность Коллатца для него будет бесконечной (и соответственно программа будет бесконечно долго вычислять её значения), либо же что она такого $$m$$ никогда не найдёт. Таким образом мы не получили из работы программы никакой полезной информации. Однако простая модификация алгоритма поиска контрпримера может всё таки дать нам способ понять найден ли контрпример либо же он не будет найден никогда. Придумайте эту модификацию.

Упражнение. Великая теорема Ферма (на английском её называют последней теоремой) утверждает, что уравнение
$$x^n + y^n = z^n$$
не имеет решений для $$n>2$$. Покажите, как можно было бы её доказать при неограниченном вычислимом ресурсе и известных $$B_n$$.

У Великой теоремы Ферма интересная история. Ферма сформулировал её в 1637 году в виде пометки на полях книги, которую он читал. Там же он указал, что он нашёл элементарное доказательство этой теоремы, но поскольку места недостаточно, он его приводить не будет. В итоге первое доказательство этой теоремы появилось только в 1994 году (спустя 356 лет!) и занимало оно 130 страниц. В этом доказательстве спустя год была найдена ошибка, которую ещё год исправляли. В итоге финальное доказательство без ошибки было представлено лишь в 1996 году. Такая вот история.

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

Чтобы избавиться от всех мешающих факторов реальных компьютеров используется модель машины Тьюринга, которая представляет собой видимо самую простую модель компьютера. Я не буду её описывать, но если вы хотите понять как примерно устроен формализм того что я здесь изложил, вы можете поискать статьи о ней и о том как она соответствует реальным вычислительным машинам, рекурсивным функциям и понятию множеств. Так же рекомендую почитать трагичную и важную биографию самого Алана Тьюринга: будучи блестящим учёным, работающим в области вычислимости и криптографии (благодаря значительным образом его работе союзники могли перехватывать шифрованные сообщения Германии во Вторую Мировую войну; теорема 3.50 так же была сформулирована и доказана именно им), он был обвинён в гомосексуальных связях и принуждён к химической кастрации и употреблению гормональных таблеток «для лечения гомосексуализма». Закончилась история лишением его всех военных наград и званий, а так же полным запретом на занятия накой. Итогом таких мер по борьбе с гомосексуализмом стал его суицид.

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

Этот текст последний параграф третьей главы учебника. Напомню, что учебник целиком доступен в pdf, что гораздо удобнее читать.

13 комментариев »

  1. 1) В каком объеме планируешь сделать свой учебник?
    2) Какие области математики хочешь охватить?
    3) Будешь ли давать ссылки на различные исторические факты?
    4) Будешь ли давать ссылки на книги для дальнейшего изучения?
    5) Можно ли когда-нибудь будет увидеть учебник на полке магазина?

    Comment by Stranger — 22.06.2014 @ 17:43
  2. @ Stranger:
    1, 2) Пока не могу ответить на этот вопрос. Хочется охватить материал первых двух курсов технических ВУЗов в части математики, но сделать это максимально правильно (что такое правильно конечно очень субъективно). Сколько это займёт бумажного места — не знаю.
    3) Да, но довольно редко. Я плохо знаю историю математики, поэтому не могу написать много чего-то интересного.
    4) Да, начиная со следующей главы. Первые три главы по подаче материала очень нестандартные и я физически не видел книг, которые рассказывали бы то же самое что и я в том же ключе. С дальнейшими главами должно быть проще.
    5) Вряд ли. У меня планов издаваться нет, но если вдруг кто-то захочет эту книгу издать, я буду конечно этому только рад.

    Comment by Хеллер — 22.06.2014 @ 18:57
  3. Возможно, в тексте стоит отделить доказательство неразрешимости проблемы останова от доказательства невычислимости B_n. Тогда эта часть станет понятнее.

    Примерно так сейчас выглядят рассуждения в тексте:
    1) А давайте напишем программу H, решающую проблему останова. Для этого возьмём B_n и будем хитро считать время.
    2) С помощью некоторых рассуждений приходим к тому, что такая H не может существовать.
    3) Значит, проблема останова неразрешима, а B_n невычислимы.

    Проблема этих рассуждений в следующем: читатель легко может подумать, что во втором пункте речь идёт только о конкретной программе H, работающей на B_n, которую мы только что описали. Собственно, так подумать для читателя логично: иначе зачем автору надо описывать эту конкретную H?
    Когда читатель так подумает, у него возникнет логичный вопрос: а как из этого следует, что проблема останова неразрешима? Да, мы доказали невозможность существования нашей конкретной программы H, но могут ведь быть и другие программы, основанные на других принципах? И как потом из этого следует невычислимость B_n?
    Иначе говоря, во втором пункте рассуждений есть неочевидное обобщение, абстрагирование от только что написанного примера.

    Чтобы таких вопросов у читателя не возникало, предлагаю переделать рассуждения, чтобы стало как-то так:
    1) Возьмём абстрактную программу H, решающую проблему останова.
    2) С помощью некоторых рассуждений приходим к тому, что такая H не может существовать.
    3) Значит, проблема останова неразрешима.

    1) Представим, что мы научились вычислять B_n.
    2) Напишем на основе B_n программу, решающую проблему останова.
    3) Но проблема останова неразрешима, значит, наше предположение неверно, и B_n невычислимы.

    Comment by artli — 22.06.2014 @ 22:34
  4. Плюсуюсь к artli. Доказательство настолько хуёво написано, что понять где накосячил автор сложнее, чем понять предмет обсуждения.
    Логика в заметке:
    1) Напишем программу H, которая сводит решение проблемы останова к вычислимости BB(n), но не будем называть вещи своими именами.
    2) В добавок программа H будет решать проблему останова.
    3) Из части 2 докажем, что H не существует. Похуй, что часть 1 с этим никак не связана.

    Исходя из того, что часть 2, запущенная на зависающей программе длины k равной длине программы H, будет работать дольше, чем BB(k), но остановится, тоже ясно, что H не существует. Что характерно, это не доказывает ни неразрешимость проблемы останова, ни невычислимость BB(n).

    Ещё и классическое доказательство проблемы останова изуродовано тем, что программы выполняют друг друга и считают ресурс. Мало того что это порождает бесконечную рекурсию A(H(A(H(…)))) в голове читателя, так ещё и не доказывает общего случая.

    Можно продолжать, но если кратко, то после 3-го абзаца заметка написана плохо.

    Про Тьюринга, я считаю, необходимо вынести важный пример: «Не хочешь химической кастрации — держи свой гомосексуализм в клозете-с».

    Ну и к слову, для меня машина Тьюринга приобрела смысл только в контексте RE, CFL и тому подобных автоматов. Зачем её упоминают как модель компьютера, да ещё и рассматривают в некоторых вводных курсах «информатики» — я не представляю.

    Comment by Anonymous — 23.06.2014 @ 03:03
  5. Роман, можешь посоветовать чего-нибудь по комбинаторной/дискретной геометрии? Может это и слишком второкультурно, но вот давно хочу познакомиться похардкору с этой областью.

    Comment by inlovewithmath — 23.06.2014 @ 07:29
  6. Роман, читаю ваш блог и периодически листаю учебник: http://pavlovo.org/1/math-book.jpg

    На досуге пилю web2print сервис, можно будет вашу книжку выставить :)

    Comment by Дмитрий — 23.06.2014 @ 10:18
  7. […] Читать доказательства, в том числе и теоремы Гёделя, уз… […]

  8. @ artli:
    @ Anonymous:
    Да, согласен. Писал в таком ключе осознанно в попытке нагнать интриги. Видимо, не удалось и получилось хуже. Переделаю, вынесу тогда проблему останова перед рассуждением о невычислимости BB(n).

    Если под RE и CFL подразумеваются регулярные выражения и контекстно-свободные языки, то я не понимаю какое отношение к этому имеет машина Тьюринга. Она тогда уж имеет отношение к рекурсивным языкам. RE — к конечным автоматам, CFL — к стековым автоматам (или как их там называют, не помню). Машина Тьюринга как раз используется для _формального_ доказательства вот этого всего что я тут написал. Собственно BB(n) формулируются именно в терминах машин Тьюринга, если по-правильному.

    @ inlovewithmath:
    Увы, ничего про это не читал, не могу посоветовать.

    @ Дмитрий:
    Я смутно представляю себе работу таких сервисов, но выглядит очень круто. Если что, то я только «за» конечно же.

    Comment by Хеллер — 23.06.2014 @ 11:32
  9. Хеллер написал:

    Если под RE и CFL подразумеваются регулярные выражения и контекстно-свободные языки, то я не понимаю какое отношение к этому имеет машина Тьюринга. Она тогда уж имеет отношение к рекурсивным языкам. RE — к конечным автоматам, CFL — к стековым автоматам (или как их там называют, не помню).

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

    Comment by Anonymous — 23.06.2014 @ 14:24
  10. Будет ли обьясняться подробное доказательство БТФ в дальнейшем?

    Comment by ДОК — 30.07.2014 @ 14:26
  11. @ ДОК:
    Нет, Большая теорема Ферма совершенно не моя область, она никогда не вызывала моего интереса, я это доказательство сам не читал никогда.

    Comment by Хеллер — 31.07.2014 @ 09:39
  12. Интересно, зачем такие простые вещи доказывать так сложно (с привлечением компьютера)? Понятно и так, что доказательство не может быть бесконечным. Потому что предложить бесконечное доказательство — все равно, что предложить перебрать все числа. И как можно проверить бесконечное доказательство за конечное число шагов? Ясно, что никак. А бесконечное число шагов проделать в принципе невозможно.

    Интереснее доказать, что у данных задач (на существование) всегда существует решение. Они даже называются «да-нет» задачи. В статье Успенского «Можно ли доказать, что великую теорему Ферма нельзя ни доказать, ни опровергнуть?» как раз это и доказывается. Понятно, что число с заданным свойством либо существует, либо не существует, а третьего не дано. Но интересно, что вместе с этим числом (либо его отсутствием) существует и доказательство существования, либо отсутствия такого числа. Только не известно, «где» это доказательство существует, и как до него добраться.

    Конечно, решение можно искать долго и бесплодно, поскольку не существует алгоритма поиска таких решений (либо он пока неизвестен). Но когда решение найдено — а это либо доказательство, либо опровержение — то это доказательство, либо опровержение, конечно же, конечно.

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

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

    Comment by sturded — 11.05.2017 @ 22:03
  13. Про Геделя, кстати, есть забавная байка.

    В 1948 году, когда решался вопрос о получении им американского гражданства, Гедель должен был в соответствии с принятой процедурой сдать что-то вроде устного экзамена по азам американской конституции. Подойдя к вопросу со всей научной добросовестностью, он досконально изучил документ, и пришел к выводу, что в США законным путем, без нарушения конституции может быть установлена диктатура. Подобное открытие чуть не стоило ему провала на испытаниях, когда он вступил в дискуссию с принимавшим зачет чиновником, который, разумеется, считал основной закон своего государства величайшим достижением политической мысли. Друзья, среди которых был Альберт Эйнштейн, выступивший одним из двух поручителей Геделя при получении им гражданства, уговорили его повременить с развертыванием своей аргументации хотя бы до принесения присяги. Позднее история получила любопытный эпилог: четверть века спустя другой американец, Кеннет Эрроу, удостоился Нобелевской премии за доказательство в общем виде утверждения, к которому пришел Гедель, изучив американскую конституцию.

    Comment by starded — 16.05.2017 @ 17:10

RSS feed for comments on this post. TrackBack URI

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

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline