Про Гёделя, Пенроуза и вычислимость
Ещё раз про вычислимость, теорему Гёделя о неполноте, алгоритмизуемость человеческого сознания и Роджера Пенроуза, получившего в этом году Нобелевку.
Почему это интересно?
С одной стороны это одна из наиболее удивительных и неожиданных теорем математики - о том, что (если опустить детали) в любой математической системе найдутся утверждения, которые невозможно ни доказать, ни опровергнуть на основании аксиом этой системы.
С другой - потому что Роджер Пенроуз использовал этот факт и немного модифицированный метод доказательства Гёделя для того чтобы доказать, что человеческое сознание неалгоритмизуемо, т.е. принципиально немоделируемо на обычном компьютере (причём квантовый компьютер тоже "обычный").
Для начала повторю некоторые базовые положения.
Алгоритм - это описание какой-то последовательности действий, описание всегда конечное, а последовательность может быть и бесконечной (бывают алгоритмы, которые работают вечно и никогда не останавливаются). Понятие алгоритма возникло задолго до компьютеров. Например, есть алгоритм Евклида для нахождения наибольшего общего делителя двух чисел.
Алгоритм - формальное математическое понятие, примерно как "функция". Его формализовали Тьюринг, Пост и Чёрч (и не только), причём они дали разные определения алгоритма, но эти определения оказались эквивалентными. Математика может изучать свойства алгоритмов, доказывать про них теоремы и т.д. Есть разные способы описания алгоритмов, математики часто обращаются к машине Тьюринга - она достаточно проста, поэтому её свойства проще изучать, но при этом на ней можно реализовать произвольный алгоритм. Можно описывать алгоритм и на любом привычном языке программирования. Важное свойство алгоритма - он (в отличие от функции) выполняется пошагово.
Алгоритмов счётное количество (корректнее говорить "счётное множество"), т.е. каждому алгоритму можно поставить в соответствие натуральное число. Это следует из того, что любой алгоритм можно записать конечной фразой на языке с конечным набором символов (алфавитом) - например, в виде машины Тьюринга.
А вот действительных чисел или функций больше, их перенумеровать не получится. В отличие, например, от формул или математических теорем - их тоже счётное количество, как и алгоритмов.
Алгоритму на вход можно давать какие-то данные, и он на выходе выдаст какие-то другие данные. Подобно функции, но функции с конечным описанием. Например, алгоритм Евклида получает на вход два числа, а на выходе возвращает их наибольший общий делитель.
Поскольку алгоритму можно поставить в соответствие число, на вход алгоритму можно передать другой алгоритм. Существует алгоритм, который, получив на вход другой алгоритм P и входные данные D, на выход выдаёт то же, что дал бы алгоритм P на входных данных D. Такой алгоритм называют "интерпретатор" (иногда "универсальная машина Тьюринга"). Причём интерпретатор в некоторых случаях может выдать результат даже быстрее, чем выдал бы интерпретируемый алгоритм, проходить по шагам - не единственный вариант. Например, если интерпретатор обнаружит и распознает цикл, в котором к переменной миллион раз прибавляется единичка, то он может вместо этого сразу прибавить к переменной миллион и пойти дальше.
Пару чисел всегда можно объединить в одно число (набор данных). И для любого алгоритма P, запущенного на входных данных D, существует (можно написать) некий алгоритм Q, который выдаст такой же результат, но на пустых входных данных.
Важное значение имеет так называемая "задача останова". Алгоритм может через какое-то количество шагов выдать результат и завершиться, а может никогда не завершиться, "зациклиться". Для простых алгоритмов может быть очевидно, остановится он или зациклится. Но если взять, например, алгоритм последовательного перебора чётных чисел, начиная с четырёх, который остановится, когда найдёт число, которое нельзя представить в виде суммы двух простых чисел, то мы не сможем сказать, остановится он когда-либо или нет. Существование таких чисел - нерешённая математическая задача, проблема Гольбаха.
Существует ли алгоритм U, которому можно было бы на вход дать произвольный другой алгоритм P, а на выходе он выдал бы ответ: завершится когда-либо этот алгоритм P или нет? Это формулировка задачи останова, которая по сути означает: существует ли универсальный способ (алгоритм) решения математических задач? Можно ли их решать "не думая", на компьютере? Доказано, что нет, так не получится, и это доказательство довольно простое. Обычно при его доказательстве используют диагональный метод, но можно обойтись и без него. Если бы существовал такой алгоритм U, который бы, скажем, возвращал "yes", если алгоритм P останавливается за конечное время, и "no", если не останавливается, то мы могли бы без труда сделать алгоритм U', который бы возвращал "no", если алгоритм P(P) не останавливается, и зацикливался бы, если алгоритм P(P) останавливается. А теперь скажем алгоритму U' исследовать самого себя. Он должен остановиться, если он зацикливается, и зациклиться, если он останавливается. Но так не бывает, значит, такого алгоритма не существует.
Это очень напоминает парадокс лжеца ("это утверждение ложно"), парадокс Рассела ("множество всех множеств, не содержащих себя в качестве подмножества") и другие парадоксы самореференции. Только тут мы имеем дело с конечными объектами в формальной системе, поэтому это не просто "игра словами", а корректное математическое доказательство от противного. Подобно, например, доказательству того, что простых чисел бесконечно много: если бы их было конечное количество, мы бы могли их все перемножить и прибавить единицу. Полученное число не делится ни на одно из нашего набора простых чисел (потому что даёт в остатке один) и не совпадает ни с одним из них (потому что больше любого из них). Этого одного контрпримера достаточно для того, чтобы утверждать, что наше предположение неверно, а значит, простых чисел бесконечно много.
Аналогично и здесь: предполагаем, что существует такой универсальный алгоритм, приходим к противоречию - значит, такого алгоритма не существует. Никакие варианты вроде "он может существовать, но работать на всех алгоритмах, кроме себя самого" не действуют: во-первых, и в этом случае можно прийти к противоречию, а во-вторых, это уже не очень интересные утверждения. Для каких-то алгоритмов это определить можно, для каких-то нельзя, как узнать, для каких можно, для каких нельзя - непонятно... Важно, что для всех - точно нельзя.
Как это связано с теоремой Гёделя? Довольно прямо.
Математическое доказательство в формальной теории - это последовательность математических символов, разбитых на отдельные утверждения, где каждое следующее утверждение следует из предыдущего. Эта цепочка начинается с аксиом и заканчивается утверждением, которое требуется доказать. Корректность доказательства можно проверить формально, алгоритмически.
Возьмём алгоритм F, который, получая на вход алгоритм P, начинает последовательно перебирать все возможные доказательства, пока не найдёт доказательство либо утверждения "P(P) остановится и выдаст 0", либо "P(P) остановится и выдаст не 0", либо "P(P) не остановится". Если находит доказательство первого утверждения, пишет 1, если второго или третьего - 0. Запустим F(F), т.е. дадим этому алгоритму его самого как входные данные. Он не может завершиться и выдать 0, потому что тогда ему нужно было бы выдать 1. Он не может и выдать 1, потому что тогда ему нужно было бы выдать 0. Поэтому он неминуемо зависнет, будет вечно перебирать доказательства всё большей длины, но так никогда и не найдёт подходящего, а это значит, что для утверждения "F(F) остановится и выдаст 0" не существует ни доказательства, ни опровержения. Причём тут алгоритм F - это не какой-то абстрактный "предположим, что существует некий алгоритм F", а вполне конкретный и реальный. То есть мы не просто доказали, что существует утверждение, которое нельзя ни доказать, ни опровергнуть, но и привели конкретный пример такого утверждения.
Теперь про Пенроуза и его доказательство неалгоритмизуемости сознания.
Пусть у нас есть не универсальный, а какой-то алгоритм W, который, получая на вход алгоритм P, в некоторых случаях может сказать "алгоритм P зациклится", а в других ничего не сказать, зациклиться сам. Например, если видит алгоритм с явным бесконечным циклом - говорит "цикл". Или если видит поиск нечётного числа, кратного шести - тоже скажет "цикл", потому что что таких чисел не существует. А если видит перебор с поиском контрпримера к гипотезе Била (если xn+ym=zk для целых x, y, z, n, m, k больше двух, то x, y и z имеют общий делитель) - ничего не скажет, зависнет. Или если видит алгоритм, который сразу выводит 0 и останавливается - тоже зацикливается. Останавливается только в тех случаях, когда он точно может сказать, что переданный ему на вход алгоритм зацикливается. Предположим, что он действует, как наше сознание: говорит "цикл" в тех, и только в тех случаях, когда и мы понимаем, что алгоритм зацикливается, и зависает, если мы видим, что алгоритм не зацикливается, или не знаем, зацикливается он или нет.
Запустим W(W) (на самом деле диагональным методом найдём такой V, для которого V() это W(V), но не суть). Он не может остановиться, потому что тогда он сказал бы неправду. Значит, он не сможет ответить, что алгоритм V зависнет, он зависнет. И мы знаем, что он зависнет, и можем сказать "W(V) зависнет". Значит, наше сознание действует не так, как алгоритм W, а это противоречит нашему предположению. Значит, не существует алгоритма, который действует, как наше сознание.
Теперь мои размышления на эти темы.
Пенроуз довольно много пишет про алгоритмическую неразрешимость некоторых задач.
Одна из известных - 10-я проблема Гильберта, про существование общего алгоритма для решения диофантовых уравнений (т.е. уравнений в целых числах). В 1970-м году она была решена - доказано, что такого алгоритма не существует. Другой пример (непосредственно связанный с некоторыми результатами, полученными Пенроузом) - задача замощения плоскости. Как ответить на вопрос, возможно ли замостить плоскость определёнными фигурками полиомино (состоящими из квадратиков, как в тетрисе, только из большего количества)? Про неё тоже доказана алгоритмическая неразрешимость, т.е. не существует алгоритма, способного ответить на этот вопрос, получив на вход конкретную фигурку полиомино.
Также из неалгоритмизуемости человеческого сознания Пенроуз делает вывод о том, что в физическом мире существуют какие-то неалгоритмизуемые законы (пока неизвестные), которые принципиально недоступны для моделирования на компьютере, ведь иначе можно было бы промоделировать работу человеческого мозга как физического объекта (квантовые эффекты тут не спасут). И приводит пример такой искусственной вселенной: перенумеруем фигурки полиомино, разобьём время на кванты (скажем, на секунды), и постановим, что частица в N-ную секунду летит влево, если N-ной фигуркой можно замостить плоскость, и вправо - если нельзя. Это вполне детерминированный "физический" закон, в каждую секунду движение частицы однозначно определено, но просчитать движение такой частицы на компьютере невозможно.
Мне это кажется странным. В формальной математической системе, если решение (доказательство) есть, то есть и алгоритм для его нахождения за конечное время. Как минимум, можно последовательно перебирать все возможные математические фразы, и для каждой проверять, не является ли она искомым доказательством. Пусть это долго и неэффективно, но это вполне корректный алгоритм, который наверняка рано или поздно найдёт доказательство, если оно существует. И поэтому отсутствие алгоритма для поиска решения означает отсутствие решения. Считать, что для каждой конкретной фигурки или для каждого конкретного диофантова уравнения доказательство (и, соответственно, алгоритм) существует, но не существует универсального алгоритма, тоже не получится: переборный алгоритм универсален, он подходит для любых входных данных. И то, что он не работает, означает лишь, что для каких-то входных данных решения нет.
А тут мы переходим к вопросу конструктивности в математике.
Утверждения, которые нельзя ни доказать, ни опровергнуть в рамках формальной математической теории, называют гёделевскими утверждениями.
Давно известны примеры гёделевских утверждений для теории множеств, позже привели примеры таких утверждений и для теории чисел.
Некоторые из таких утверждений можно сформулировать в виде "существует ли ...". Например, континуум-гипотеза: существует ли множество, мощность которого больше счётного, но меньше чем континуум? То есть более грубо, множество, в котором элементов больше, чем натуральных чисел, но меньше, чем действительных? Исходя из аксиоматики теории множеств (Цермело-Френкеля, ZF) это утверждение нельзя ни доказать, ни опровергнуть, и это доказано. Казалось бы: если доказано, что невозможно привести пример такого множества - разве это не доказывает его отсутствие? Но нет: если постулировать, что такое множество есть, и назвать его каким-то символом, то получается вполне стройная и непротиворечивая теория.
Если присмотреться, то все упомянутые выше утверждения, связанные с теоремой Гёделя или задачей останова или алгоритмической разрешимостью, опираются на смысл терминов, а не на их формальное определение, и затрагивают конструктивизм. Мы доказываем, что невозможно привести пример, и из этого делаем вывод о его отсутствии. Алгоритм не может найти доказательство - значит, доказательства не существует. Мы не можем найти число N, после которого алгоритм остановится - значит, он зациклится. Не существует примера замощения плоскости - значит, замостить невозможно. Это именно тот переход, который не получится сделать формально, его не сделает машина. Поэтому наше (приведённое выше) доказательство того, что F(F) зависнет, не сможет найти сам алгоритм F. Для него существование доказательства не противоречит отсутствию возможности найти это доказательство, равно как существование множества мощностью между счётным и континуумом не противоречит невозможности привести пример такого множества в рамках ZF.
Мы понимаем, что любой алгоритм на самом деле либо остановится, либо не остановится.
А что такое вот это "на самом деле"? Алгоритм - это математическая абстракция, для него "на самом деле" - это то, что можно доказать. И если возможно доказать, что алгоритм P не остановится, то это доказательство можно найти алгоритмически (хоть простым перебором разных доказательств). А если алгоритм U никак не может определить, остановится алгоритм P или нет, то это не просто значит, что он не может найти доказательство (а мы, возможно, сможем, т.к. мы умнее машины) - нет, это означает, что доказательства не существует. То есть, утверждение "алгоритм P остановится" - гёделевское.
Ok, но если это гёделевское утверждение, то алгоритм не остановится за первые N шагов для сколь угодно большого N (иначе это было бы доказательством того, что он остановится). А это значит, что он не остановится никогда. Давайте введём дополнительную аксиому: "если утверждение о том, остановится ли алгоритм, является гёделевским, то будем считать, что он не остановится". Увы - в этом случае окажется, что сам факт того, что это гёделевское утверждение, тоже невозможно доказать! И эта косвенность уходит в бесконечность, а доказательства бесконечной длины, как и бесконечные алгоритмы, мы не рассматриваем.
В частности, алгоритм, который ищет доказательство математической теоремы: мы не можем сказать, найдёт ли он его когда-либо или нет. Любой лимит на количество действий может оказаться недостаточным, и решив, что алгоритм завис, мы рискуем ошибиться.
Если алгоритм проверки существования чего-то (например, чётного числа больше двух, не являющегося суммой двух простых) будет искать либо контрпример, либо доказательство, он может зависнуть, если это окажется гёделевским утверждением. Но ведь в теории чисел отсутствие примера (т.е. если мы докажем, что такой алгоритм зависнет и никогда не найдёт пример) является доказательством отсутствия? Мы это понимаем исходя из смысла, а компьютер этого не понимает, для него это не является доказательством.
Вычислимость.
Число S называется вычислимым, если существует алгоритм, который, получив на вход N, на выходе выдаст N-ную цифру числа S.
Множество вычислимых чисел, как и множество алгоритмов, счётно.
Все рациональные числа являются вычислимыми. Все алгебраические числа вычислимы. Числа e, пи и всякие другие вычислимы.
Все известные нам из математики числа вычислимы. Но при этом невычислимых чисел намного (в бесконечность раз) больше, чем вычислимых.
Что это за невидимая "тёмная материя" на числовой прямой? Возможно ли привести пример невычислимого числа?
Пенроуз утверждает, что да, возможно. Например, диагональным методом (который Кантор применил для доказательства несчётности множества действительных чисел, а потом этот же метод использовался и в доказательстве теоремы Гёделя о неполноте, и в доказательстве задачи останова).
Для этого выпишем последовательно все алгоритмы, которые останавливаются и возвращают какое-то число, и выпишем рядом числа, которые они возвращают. Если точнее, то выпишем алгоритмы, которые останавливаются на любом входе, и будем считать, что алгоритм, которому даётся на вход число N, возвращает N-ную цифру числа. Теперь построим число, у которого P-я цифра отличается от P-ой цифры числа, выданного P-ым алгоритмом, т.е. от P(P). Такое число будет хотя бы одной цифрой отличаться от всех чисел, выданных какими-либо алгоритмами, а значит, будет невычислимым.
Но можно ли последовательно выписать все алгоритмы, которые останавливаются, и как это сделать? В принципе такая возможность не следует напрямую из того, что множество алгоритмов счётно. Последовательно перебирая алгоритмы, нам встретится такой, о котором мы не сможем сказать, остановится ли он. Но "мы не сможем сказать" - это алгоритм не сможет сказать, это утверждение будет гёделевским. Но раз это гёделевское утверждение, то алгоритм не остановится, и мы его выкинем из списка. Получается, что мы построили пример невычислимого числа, а алгоритм повторить этот трюк не сможет, как и должно быть (ведь иначе алгоритм бы привёл пример невычислимого числа, а это противоречит определению вычислимости).
У меня вызывает некоторый дискомфорт вот это "на самом деле", которое невозможно доказать. То, что формально ни из чего не следует, но нам ясно, потому что мы понимаем "смысл". Несмотря на то, что это математическая теория, построенная на аксиомах, и из аксиом это не следует. К чему относится это "на самом деле", если и не к формальной математике, и не к физическому миру? Неужели это действительно пример того, что принципиально отличает наше сознание от компьютерных алгоритмов, как считает Пенроуз?
Интересно, что мы можем при помощи алгоритма последовательно выписать все алгоритмы, которые останавливаются на пустых входных данных. Для этого нужно последовательно брать следующий алгоритм и делать один шаг у всех имеющихся, а когда какой-то алгоритм остановился - записывать его в таблицу. Тогда любой алгоритм, который на каком-то шаге остановится, рано или поздно окажется в результирующей таблице. Но это не даст возможность выписать все вычислимые числа, т.к. для этого нужно выписать алгоритмы, останавливающийся на любых входных данных, а для них такой трюк уже не проходит.
Возникает вопрос: а действительно ли существование невычислимых чисел нам зачем-то нужно? Они появились, когда рациональных чисел оказалось недостаточно - тогда определили действительное число как бесконечную десятичную дробь (или как сечение множества рациональных чисел, что эквивалентно), и потом доказали, что такие объекты невозможно перенумеровать, их оказалось "больше, чем бесконечность", и такую "сверх-бесконечность" назвали "континуум". Но что если всё это произошло лишь потому что не придумали понятие "вычислимое число", и вместо этого взяли более простое, но и более проблематичное определение "бесконечная десятичная дробь"? Вычислимых чисел достаточно для всех применений, и при этом их не "больше чем бесконечность".
Сейчас кажется интуитивно понятным, что на числовой прямой точек континуум. Но что если это лишь привычный предрассудок? Никакими геометрическими построениями мы не сможем на числовой прямой построить невычислимую точку. И никакими алгебраическими построениями не сможем получить невычислимое число. И если отказаться от недоказуемого "смысла", то у нас не получится и построить невычислимое число, т.к. мы не сможем решить, оставлять ли очередной алгоритм в списке или нет, столкнувшись с гёделевским утверждением о его завершимости. Так, может, их нет? Бесконечность - она одна, и понятие "континуум" - та ошибка, которая привела к кризису теории множеств и вообще оснований математики.
Если мы опираемся на конструктивность в доказательстве теоремы Гёделя и других утверждений мат.логики и теории чисел (невозможность привести пример принимаем как доказательство отсутствия) то почему мы ей не следуем в теории множеств?
Любопытный факт.
Можем ли мы для произвольного действительного числа R привести алгоритм, который, получая на вход число A, возвращает на выходе A+R?
На первый взгляд кажется, что конечно да, это очень простой алгоритм.
Но чисел R континуум, а алгоритмов всего лишь счётное множество. Не существует способа задать произвольное действительное число R конечной последовательностью символов. Так можно задать только вычислимые числа. Поэтому правильный ответ "нет", если, конечно, мы допускаем существование невычислимых чисел.
UPD Уважаемый
dbg привёл пример построения монотонной ограниченной последовательности рациональных чисел, пределом которой является невычислимое число. Причём эту последовательность можно генерировать алгоритмом (и даже вполне реально написать такую программу). Так что отказаться от невычислимых чисел не получится. Но сдаваться рано, есть пути к отступлению. Существуют definable numbers (не уверен, какой для них термин в русском языке). Они включают в себя вычислимые числа, их тоже счётное множество, и вот тут привести пример undefinable number уж точно не получится.
Пример невычислимого числа строится таким способом.
Берём число 0, записываем его как 0,000...
Последовательно перебираем машины Тьюринга, начиная с первой, и поступаем так, как мы выше нумеровали машины, останавливающиеся на пустом входе. То есть, делаем один шаг первой машины, потом добавляем вторую машину, делаем один шаг для обеих, добавляем третью, делаем один шаг всем трём, добавляем четвёртую и т.д. Когда какая-либо из машин на очередном шаге останавливается - меняем в нашем числе нолик на единичку в позиции, соответствующей номеру остановившейся машины, и считаем это очередным членом последовательности. Все члены этой последовательности - конечные десятичные (ну или двоичные - это неважно) дроби, т.е. рациональные числа. Эта последовательность строго возрастающая, т.к. на каждом шаге какой-то из ноликов в записи меняется на единичку. И эта последовательность ограничена сверху единицей. Предел этой последовательности - число, у которого единицами помечены все останавливающиеся машины Тьюринга, а ноликами - не останавливающиеся, т.к. для любой останавливающейся машины Тьюринга мы непременно дойдём до шага, на котором она остановится, и на её месте в нашей последовательности появится единичка, эта же единичка будет там и в пределе этой последовательности, а для всех неостанавливающихся машин там (в пределе) останутся нули. Это число (предел последовательности) невычислимо, это следует из задачи останова.
This entry was originally posted at https://gul-kiev.dreamwidth.org/69745.html.
Почему это интересно?
С одной стороны это одна из наиболее удивительных и неожиданных теорем математики - о том, что (если опустить детали) в любой математической системе найдутся утверждения, которые невозможно ни доказать, ни опровергнуть на основании аксиом этой системы.
С другой - потому что Роджер Пенроуз использовал этот факт и немного модифицированный метод доказательства Гёделя для того чтобы доказать, что человеческое сознание неалгоритмизуемо, т.е. принципиально немоделируемо на обычном компьютере (причём квантовый компьютер тоже "обычный").
Для начала повторю некоторые базовые положения.
Алгоритм - это описание какой-то последовательности действий, описание всегда конечное, а последовательность может быть и бесконечной (бывают алгоритмы, которые работают вечно и никогда не останавливаются). Понятие алгоритма возникло задолго до компьютеров. Например, есть алгоритм Евклида для нахождения наибольшего общего делителя двух чисел.
Алгоритм - формальное математическое понятие, примерно как "функция". Его формализовали Тьюринг, Пост и Чёрч (и не только), причём они дали разные определения алгоритма, но эти определения оказались эквивалентными. Математика может изучать свойства алгоритмов, доказывать про них теоремы и т.д. Есть разные способы описания алгоритмов, математики часто обращаются к машине Тьюринга - она достаточно проста, поэтому её свойства проще изучать, но при этом на ней можно реализовать произвольный алгоритм. Можно описывать алгоритм и на любом привычном языке программирования. Важное свойство алгоритма - он (в отличие от функции) выполняется пошагово.
Алгоритмов счётное количество (корректнее говорить "счётное множество"), т.е. каждому алгоритму можно поставить в соответствие натуральное число. Это следует из того, что любой алгоритм можно записать конечной фразой на языке с конечным набором символов (алфавитом) - например, в виде машины Тьюринга.
А вот действительных чисел или функций больше, их перенумеровать не получится. В отличие, например, от формул или математических теорем - их тоже счётное количество, как и алгоритмов.
Алгоритму на вход можно давать какие-то данные, и он на выходе выдаст какие-то другие данные. Подобно функции, но функции с конечным описанием. Например, алгоритм Евклида получает на вход два числа, а на выходе возвращает их наибольший общий делитель.
Поскольку алгоритму можно поставить в соответствие число, на вход алгоритму можно передать другой алгоритм. Существует алгоритм, который, получив на вход другой алгоритм P и входные данные D, на выход выдаёт то же, что дал бы алгоритм P на входных данных D. Такой алгоритм называют "интерпретатор" (иногда "универсальная машина Тьюринга"). Причём интерпретатор в некоторых случаях может выдать результат даже быстрее, чем выдал бы интерпретируемый алгоритм, проходить по шагам - не единственный вариант. Например, если интерпретатор обнаружит и распознает цикл, в котором к переменной миллион раз прибавляется единичка, то он может вместо этого сразу прибавить к переменной миллион и пойти дальше.
Пару чисел всегда можно объединить в одно число (набор данных). И для любого алгоритма P, запущенного на входных данных D, существует (можно написать) некий алгоритм Q, который выдаст такой же результат, но на пустых входных данных.
Важное значение имеет так называемая "задача останова". Алгоритм может через какое-то количество шагов выдать результат и завершиться, а может никогда не завершиться, "зациклиться". Для простых алгоритмов может быть очевидно, остановится он или зациклится. Но если взять, например, алгоритм последовательного перебора чётных чисел, начиная с четырёх, который остановится, когда найдёт число, которое нельзя представить в виде суммы двух простых чисел, то мы не сможем сказать, остановится он когда-либо или нет. Существование таких чисел - нерешённая математическая задача, проблема Гольбаха.
Существует ли алгоритм U, которому можно было бы на вход дать произвольный другой алгоритм P, а на выходе он выдал бы ответ: завершится когда-либо этот алгоритм P или нет? Это формулировка задачи останова, которая по сути означает: существует ли универсальный способ (алгоритм) решения математических задач? Можно ли их решать "не думая", на компьютере? Доказано, что нет, так не получится, и это доказательство довольно простое. Обычно при его доказательстве используют диагональный метод, но можно обойтись и без него. Если бы существовал такой алгоритм U, который бы, скажем, возвращал "yes", если алгоритм P останавливается за конечное время, и "no", если не останавливается, то мы могли бы без труда сделать алгоритм U', который бы возвращал "no", если алгоритм P(P) не останавливается, и зацикливался бы, если алгоритм P(P) останавливается. А теперь скажем алгоритму U' исследовать самого себя. Он должен остановиться, если он зацикливается, и зациклиться, если он останавливается. Но так не бывает, значит, такого алгоритма не существует.
Это очень напоминает парадокс лжеца ("это утверждение ложно"), парадокс Рассела ("множество всех множеств, не содержащих себя в качестве подмножества") и другие парадоксы самореференции. Только тут мы имеем дело с конечными объектами в формальной системе, поэтому это не просто "игра словами", а корректное математическое доказательство от противного. Подобно, например, доказательству того, что простых чисел бесконечно много: если бы их было конечное количество, мы бы могли их все перемножить и прибавить единицу. Полученное число не делится ни на одно из нашего набора простых чисел (потому что даёт в остатке один) и не совпадает ни с одним из них (потому что больше любого из них). Этого одного контрпримера достаточно для того, чтобы утверждать, что наше предположение неверно, а значит, простых чисел бесконечно много.
Аналогично и здесь: предполагаем, что существует такой универсальный алгоритм, приходим к противоречию - значит, такого алгоритма не существует. Никакие варианты вроде "он может существовать, но работать на всех алгоритмах, кроме себя самого" не действуют: во-первых, и в этом случае можно прийти к противоречию, а во-вторых, это уже не очень интересные утверждения. Для каких-то алгоритмов это определить можно, для каких-то нельзя, как узнать, для каких можно, для каких нельзя - непонятно... Важно, что для всех - точно нельзя.
Как это связано с теоремой Гёделя? Довольно прямо.
Математическое доказательство в формальной теории - это последовательность математических символов, разбитых на отдельные утверждения, где каждое следующее утверждение следует из предыдущего. Эта цепочка начинается с аксиом и заканчивается утверждением, которое требуется доказать. Корректность доказательства можно проверить формально, алгоритмически.
Возьмём алгоритм F, который, получая на вход алгоритм P, начинает последовательно перебирать все возможные доказательства, пока не найдёт доказательство либо утверждения "P(P) остановится и выдаст 0", либо "P(P) остановится и выдаст не 0", либо "P(P) не остановится". Если находит доказательство первого утверждения, пишет 1, если второго или третьего - 0. Запустим F(F), т.е. дадим этому алгоритму его самого как входные данные. Он не может завершиться и выдать 0, потому что тогда ему нужно было бы выдать 1. Он не может и выдать 1, потому что тогда ему нужно было бы выдать 0. Поэтому он неминуемо зависнет, будет вечно перебирать доказательства всё большей длины, но так никогда и не найдёт подходящего, а это значит, что для утверждения "F(F) остановится и выдаст 0" не существует ни доказательства, ни опровержения. Причём тут алгоритм F - это не какой-то абстрактный "предположим, что существует некий алгоритм F", а вполне конкретный и реальный. То есть мы не просто доказали, что существует утверждение, которое нельзя ни доказать, ни опровергнуть, но и привели конкретный пример такого утверждения.
Теперь про Пенроуза и его доказательство неалгоритмизуемости сознания.
Пусть у нас есть не универсальный, а какой-то алгоритм W, который, получая на вход алгоритм P, в некоторых случаях может сказать "алгоритм P зациклится", а в других ничего не сказать, зациклиться сам. Например, если видит алгоритм с явным бесконечным циклом - говорит "цикл". Или если видит поиск нечётного числа, кратного шести - тоже скажет "цикл", потому что что таких чисел не существует. А если видит перебор с поиском контрпримера к гипотезе Била (если xn+ym=zk для целых x, y, z, n, m, k больше двух, то x, y и z имеют общий делитель) - ничего не скажет, зависнет. Или если видит алгоритм, который сразу выводит 0 и останавливается - тоже зацикливается. Останавливается только в тех случаях, когда он точно может сказать, что переданный ему на вход алгоритм зацикливается. Предположим, что он действует, как наше сознание: говорит "цикл" в тех, и только в тех случаях, когда и мы понимаем, что алгоритм зацикливается, и зависает, если мы видим, что алгоритм не зацикливается, или не знаем, зацикливается он или нет.
Запустим W(W) (на самом деле диагональным методом найдём такой V, для которого V() это W(V), но не суть). Он не может остановиться, потому что тогда он сказал бы неправду. Значит, он не сможет ответить, что алгоритм V зависнет, он зависнет. И мы знаем, что он зависнет, и можем сказать "W(V) зависнет". Значит, наше сознание действует не так, как алгоритм W, а это противоречит нашему предположению. Значит, не существует алгоритма, который действует, как наше сознание.
Теперь мои размышления на эти темы.
Пенроуз довольно много пишет про алгоритмическую неразрешимость некоторых задач.
Одна из известных - 10-я проблема Гильберта, про существование общего алгоритма для решения диофантовых уравнений (т.е. уравнений в целых числах). В 1970-м году она была решена - доказано, что такого алгоритма не существует. Другой пример (непосредственно связанный с некоторыми результатами, полученными Пенроузом) - задача замощения плоскости. Как ответить на вопрос, возможно ли замостить плоскость определёнными фигурками полиомино (состоящими из квадратиков, как в тетрисе, только из большего количества)? Про неё тоже доказана алгоритмическая неразрешимость, т.е. не существует алгоритма, способного ответить на этот вопрос, получив на вход конкретную фигурку полиомино.
Также из неалгоритмизуемости человеческого сознания Пенроуз делает вывод о том, что в физическом мире существуют какие-то неалгоритмизуемые законы (пока неизвестные), которые принципиально недоступны для моделирования на компьютере, ведь иначе можно было бы промоделировать работу человеческого мозга как физического объекта (квантовые эффекты тут не спасут). И приводит пример такой искусственной вселенной: перенумеруем фигурки полиомино, разобьём время на кванты (скажем, на секунды), и постановим, что частица в N-ную секунду летит влево, если N-ной фигуркой можно замостить плоскость, и вправо - если нельзя. Это вполне детерминированный "физический" закон, в каждую секунду движение частицы однозначно определено, но просчитать движение такой частицы на компьютере невозможно.
Мне это кажется странным. В формальной математической системе, если решение (доказательство) есть, то есть и алгоритм для его нахождения за конечное время. Как минимум, можно последовательно перебирать все возможные математические фразы, и для каждой проверять, не является ли она искомым доказательством. Пусть это долго и неэффективно, но это вполне корректный алгоритм, который наверняка рано или поздно найдёт доказательство, если оно существует. И поэтому отсутствие алгоритма для поиска решения означает отсутствие решения. Считать, что для каждой конкретной фигурки или для каждого конкретного диофантова уравнения доказательство (и, соответственно, алгоритм) существует, но не существует универсального алгоритма, тоже не получится: переборный алгоритм универсален, он подходит для любых входных данных. И то, что он не работает, означает лишь, что для каких-то входных данных решения нет.
А тут мы переходим к вопросу конструктивности в математике.
Утверждения, которые нельзя ни доказать, ни опровергнуть в рамках формальной математической теории, называют гёделевскими утверждениями.
Давно известны примеры гёделевских утверждений для теории множеств, позже привели примеры таких утверждений и для теории чисел.
Некоторые из таких утверждений можно сформулировать в виде "существует ли ...". Например, континуум-гипотеза: существует ли множество, мощность которого больше счётного, но меньше чем континуум? То есть более грубо, множество, в котором элементов больше, чем натуральных чисел, но меньше, чем действительных? Исходя из аксиоматики теории множеств (Цермело-Френкеля, ZF) это утверждение нельзя ни доказать, ни опровергнуть, и это доказано. Казалось бы: если доказано, что невозможно привести пример такого множества - разве это не доказывает его отсутствие? Но нет: если постулировать, что такое множество есть, и назвать его каким-то символом, то получается вполне стройная и непротиворечивая теория.
Если присмотреться, то все упомянутые выше утверждения, связанные с теоремой Гёделя или задачей останова или алгоритмической разрешимостью, опираются на смысл терминов, а не на их формальное определение, и затрагивают конструктивизм. Мы доказываем, что невозможно привести пример, и из этого делаем вывод о его отсутствии. Алгоритм не может найти доказательство - значит, доказательства не существует. Мы не можем найти число N, после которого алгоритм остановится - значит, он зациклится. Не существует примера замощения плоскости - значит, замостить невозможно. Это именно тот переход, который не получится сделать формально, его не сделает машина. Поэтому наше (приведённое выше) доказательство того, что F(F) зависнет, не сможет найти сам алгоритм F. Для него существование доказательства не противоречит отсутствию возможности найти это доказательство, равно как существование множества мощностью между счётным и континуумом не противоречит невозможности привести пример такого множества в рамках ZF.
Мы понимаем, что любой алгоритм на самом деле либо остановится, либо не остановится.
А что такое вот это "на самом деле"? Алгоритм - это математическая абстракция, для него "на самом деле" - это то, что можно доказать. И если возможно доказать, что алгоритм P не остановится, то это доказательство можно найти алгоритмически (хоть простым перебором разных доказательств). А если алгоритм U никак не может определить, остановится алгоритм P или нет, то это не просто значит, что он не может найти доказательство (а мы, возможно, сможем, т.к. мы умнее машины) - нет, это означает, что доказательства не существует. То есть, утверждение "алгоритм P остановится" - гёделевское.
Ok, но если это гёделевское утверждение, то алгоритм не остановится за первые N шагов для сколь угодно большого N (иначе это было бы доказательством того, что он остановится). А это значит, что он не остановится никогда. Давайте введём дополнительную аксиому: "если утверждение о том, остановится ли алгоритм, является гёделевским, то будем считать, что он не остановится". Увы - в этом случае окажется, что сам факт того, что это гёделевское утверждение, тоже невозможно доказать! И эта косвенность уходит в бесконечность, а доказательства бесконечной длины, как и бесконечные алгоритмы, мы не рассматриваем.
В частности, алгоритм, который ищет доказательство математической теоремы: мы не можем сказать, найдёт ли он его когда-либо или нет. Любой лимит на количество действий может оказаться недостаточным, и решив, что алгоритм завис, мы рискуем ошибиться.
Если алгоритм проверки существования чего-то (например, чётного числа больше двух, не являющегося суммой двух простых) будет искать либо контрпример, либо доказательство, он может зависнуть, если это окажется гёделевским утверждением. Но ведь в теории чисел отсутствие примера (т.е. если мы докажем, что такой алгоритм зависнет и никогда не найдёт пример) является доказательством отсутствия? Мы это понимаем исходя из смысла, а компьютер этого не понимает, для него это не является доказательством.
Вычислимость.
Число S называется вычислимым, если существует алгоритм, который, получив на вход N, на выходе выдаст N-ную цифру числа S.
Множество вычислимых чисел, как и множество алгоритмов, счётно.
Все рациональные числа являются вычислимыми. Все алгебраические числа вычислимы. Числа e, пи и всякие другие вычислимы.
Все известные нам из математики числа вычислимы. Но при этом невычислимых чисел намного (в бесконечность раз) больше, чем вычислимых.
Что это за невидимая "тёмная материя" на числовой прямой? Возможно ли привести пример невычислимого числа?
Пенроуз утверждает, что да, возможно. Например, диагональным методом (который Кантор применил для доказательства несчётности множества действительных чисел, а потом этот же метод использовался и в доказательстве теоремы Гёделя о неполноте, и в доказательстве задачи останова).
Для этого выпишем последовательно все алгоритмы, которые останавливаются и возвращают какое-то число, и выпишем рядом числа, которые они возвращают. Если точнее, то выпишем алгоритмы, которые останавливаются на любом входе, и будем считать, что алгоритм, которому даётся на вход число N, возвращает N-ную цифру числа. Теперь построим число, у которого P-я цифра отличается от P-ой цифры числа, выданного P-ым алгоритмом, т.е. от P(P). Такое число будет хотя бы одной цифрой отличаться от всех чисел, выданных какими-либо алгоритмами, а значит, будет невычислимым.
Но можно ли последовательно выписать все алгоритмы, которые останавливаются, и как это сделать? В принципе такая возможность не следует напрямую из того, что множество алгоритмов счётно. Последовательно перебирая алгоритмы, нам встретится такой, о котором мы не сможем сказать, остановится ли он. Но "мы не сможем сказать" - это алгоритм не сможет сказать, это утверждение будет гёделевским. Но раз это гёделевское утверждение, то алгоритм не остановится, и мы его выкинем из списка. Получается, что мы построили пример невычислимого числа, а алгоритм повторить этот трюк не сможет, как и должно быть (ведь иначе алгоритм бы привёл пример невычислимого числа, а это противоречит определению вычислимости).
У меня вызывает некоторый дискомфорт вот это "на самом деле", которое невозможно доказать. То, что формально ни из чего не следует, но нам ясно, потому что мы понимаем "смысл". Несмотря на то, что это математическая теория, построенная на аксиомах, и из аксиом это не следует. К чему относится это "на самом деле", если и не к формальной математике, и не к физическому миру? Неужели это действительно пример того, что принципиально отличает наше сознание от компьютерных алгоритмов, как считает Пенроуз?
Интересно, что мы можем при помощи алгоритма последовательно выписать все алгоритмы, которые останавливаются на пустых входных данных. Для этого нужно последовательно брать следующий алгоритм и делать один шаг у всех имеющихся, а когда какой-то алгоритм остановился - записывать его в таблицу. Тогда любой алгоритм, который на каком-то шаге остановится, рано или поздно окажется в результирующей таблице. Но это не даст возможность выписать все вычислимые числа, т.к. для этого нужно выписать алгоритмы, останавливающийся на любых входных данных, а для них такой трюк уже не проходит.
Возникает вопрос: а действительно ли существование невычислимых чисел нам зачем-то нужно? Они появились, когда рациональных чисел оказалось недостаточно - тогда определили действительное число как бесконечную десятичную дробь (или как сечение множества рациональных чисел, что эквивалентно), и потом доказали, что такие объекты невозможно перенумеровать, их оказалось "больше, чем бесконечность", и такую "сверх-бесконечность" назвали "континуум". Но что если всё это произошло лишь потому что не придумали понятие "вычислимое число", и вместо этого взяли более простое, но и более проблематичное определение "бесконечная десятичная дробь"? Вычислимых чисел достаточно для всех применений, и при этом их не "больше чем бесконечность".
Сейчас кажется интуитивно понятным, что на числовой прямой точек континуум. Но что если это лишь привычный предрассудок? Никакими геометрическими построениями мы не сможем на числовой прямой построить невычислимую точку. И никакими алгебраическими построениями не сможем получить невычислимое число. И если отказаться от недоказуемого "смысла", то у нас не получится и построить невычислимое число, т.к. мы не сможем решить, оставлять ли очередной алгоритм в списке или нет, столкнувшись с гёделевским утверждением о его завершимости. Так, может, их нет? Бесконечность - она одна, и понятие "континуум" - та ошибка, которая привела к кризису теории множеств и вообще оснований математики.
Если мы опираемся на конструктивность в доказательстве теоремы Гёделя и других утверждений мат.логики и теории чисел (невозможность привести пример принимаем как доказательство отсутствия) то почему мы ей не следуем в теории множеств?
Любопытный факт.
Можем ли мы для произвольного действительного числа R привести алгоритм, который, получая на вход число A, возвращает на выходе A+R?
На первый взгляд кажется, что конечно да, это очень простой алгоритм.
Но чисел R континуум, а алгоритмов всего лишь счётное множество. Не существует способа задать произвольное действительное число R конечной последовательностью символов. Так можно задать только вычислимые числа. Поэтому правильный ответ "нет", если, конечно, мы допускаем существование невычислимых чисел.
UPD Уважаемый
dbg привёл пример построения монотонной ограниченной последовательности рациональных чисел, пределом которой является невычислимое число. Причём эту последовательность можно генерировать алгоритмом (и даже вполне реально написать такую программу). Так что отказаться от невычислимых чисел не получится. Но сдаваться рано, есть пути к отступлению. Существуют definable numbers (не уверен, какой для них термин в русском языке). Они включают в себя вычислимые числа, их тоже счётное множество, и вот тут привести пример undefinable number уж точно не получится.
Пример невычислимого числа строится таким способом.
Берём число 0, записываем его как 0,000...
Последовательно перебираем машины Тьюринга, начиная с первой, и поступаем так, как мы выше нумеровали машины, останавливающиеся на пустом входе. То есть, делаем один шаг первой машины, потом добавляем вторую машину, делаем один шаг для обеих, добавляем третью, делаем один шаг всем трём, добавляем четвёртую и т.д. Когда какая-либо из машин на очередном шаге останавливается - меняем в нашем числе нолик на единичку в позиции, соответствующей номеру остановившейся машины, и считаем это очередным членом последовательности. Все члены этой последовательности - конечные десятичные (ну или двоичные - это неважно) дроби, т.е. рациональные числа. Эта последовательность строго возрастающая, т.к. на каждом шаге какой-то из ноликов в записи меняется на единичку. И эта последовательность ограничена сверху единицей. Предел этой последовательности - число, у которого единицами помечены все останавливающиеся машины Тьюринга, а ноликами - не останавливающиеся, т.к. для любой останавливающейся машины Тьюринга мы непременно дойдём до шага, на котором она остановится, и на её месте в нашей последовательности появится единичка, эта же единичка будет там и в пределе этой последовательности, а для всех неостанавливающихся машин там (в пределе) останутся нули. Это число (предел последовательности) невычислимо, это следует из задачи останова.
This entry was originally posted at https://gul-kiev.dreamwidth.org/69745.html.