Pavel Gulchouck (gul_kiev) wrote,
Pavel Gulchouck
gul_kiev

Category:

Про Гёделя, Пенроуза и вычислимость (3)

Продолжаю ту же тему, предыдущие посты: 1, 2.

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

Итак, теорема Гёделя о неполноте утверждает, что для описания математических объектов (например, объекта "число") никакого конечного набора аксиом не будет достаточно - всегда найдутся какие-то свойства чисел, которые из этих аксиом не следуют.

Повторю обоснование этого одним абзацем, более подробно здесь.
Можно составить алгоритм, который на основании заложенных в него правил (набора аксиом и правил вывода из них теорем) автоматически ищет доказательство (или опровержение) данного ему на вход утверждения. Проблема останова, как и теорема Гёделя, сводится к тому, что всегда найдётся такой алгоритм P, что для утверждения "алгоритм P остановится" не найдётся ни доказательства, ни опровержения: это одновременно демонстрирует и проблему останова (не существует алгоритма, который про любой данный ему на вход алгоритм сможет сказать, остановится ли он), и теорему Гёделя о неполноте (в любой непротиворечивой аксиоматической системе найдётся такое утверждение A, что из аксиом не следует ни A, ни !A, "гёделевское утверждение").

Мы можем придумать число, которое в выбранной нами аксиоматической системе будет неопределено. Для этого достаточно взять любое утверждение, не определённое в этой системе аксиом, и сказать, что это число равно 1, если утверждение истинно, или 0, если ложно. Но любое гёделевское утверждение про числа "на самом деле" либо истинно, либо ложно, мы не можем выбрать его значение произвольно. Поэтому такое число будет всё-таки вполне определено, хотя для этого может быть необходимо расширить систему аксиом.

Существуют классы задач, для которых доказано, что для любой системы аксиом найдётся "неразрешимая" задача из этого класса, т.е. ответ на которую не выводится из этих аксиом. Проблема останова (остановится ли выбранный алгоритм?) - один из примеров. Другие примеры: решение диофантовых уравнений (10-я проблема Гильберта) или проблема замощения плоскости заданными многоугольниками. Какую бы систему аксиом мы ни выбрали, всегда найдётся такое диофантово уравнение, неразрешимость которого невозможно доказать, и такой многоугольник, для которого невозможно доказать невозможность замощения. Но при этом мы понимаем, что решения уравнения нет, и замостить нельзя, иначе это решение и это замощение были бы доказательством их существования.

Теперь можно поступить интереснее: построить такое число, которое не определено ни в одной конечной системе аксиом, а не просто в какой-то одной конкретной. Например, взять число, у которого N-ная цифра после запятой 1, если N-ная машина Тьюринга на пустом входе останавливается, и 0 - если не останавливается. Или 1, если N-е диофантово уравнение имеет решение, и 0, если не имеет. Или 1, если замостить поскость N-ным многоугольником можно, и 0, если нельзя (можно рассматривать только некоторые многоугольники, которые можно перенумеровать). Какую бы систему аксиом мы ни выбрали, в таком числе непременно найдётся цифра, которая в этой системе не определена. Поэтому и не существует алгоритма, который мог бы вычислить это число (при запуске с параметром N на выходе дать N-ную цифру этого числа) - алгоритм конечен, он может содержать в себе лишь конечное число аксиом, а потому для него будут гёделевские утверждения и, соответственно, он не сможет найти соответствующую цифру. Но "для нас" (оперирующих математическими объектами "число", "плоскость", "алгоритм", т.е. не ограниченных конечным набором аксиом) такое число вполне определено. Именно такие числа, неопределённые в любой конечной аксиоматической системе, и называются невычислимыми.

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

Итак, ещё раз: ни в одной формальной системе, т.е. в ни в какой конечной системе аксиом, невычислимых чисел не существует. Существуют неопределённые ("гёделевские") числа. Невычислимыми мы называем числа, которые являются гёделевскими в любой системе аксиом, описывающей числа, какую бы мы ни выбрали.
Соответственно, невычислимых чисел не существует и "с точки зрения" любого алгоритма. И вот это может взорвать мозг тем, кто привык считать, что мозг работает как компьютер, и искусственный интелект может полностью промоделировать работу мозга. Как так получается, что для любого алгоритма невычислимых чисел не существует, а мы ими оперируем и приводим примеры таких чисел? Иногда выход ищут в том, что невычислимых чисел не существует вообще, а в примерах этих чисел есть какая-то ошибка. Роджер Пенроуз видит ответ в неалгоритмизуемости сознания и каких-то физических законов, в соответствии с которыми работает наш мозг.

Но возникает следующий вопрос. Как же в формальной системе может не быть невычислимых чисел, если множество вычислимых чисел счётно, а действительных континуум, т.е. кардинально больше? (Здесь "кардинально" можно считать математическим термином).

Ответ может быть в том, что вся концепция действительных чисел необоснована (тут "обоснована" тоже можно считать математическим термином). Если определять числа как бесконечные десятичные дроби, то большинство таких чисел окажутся гёделевскими (неопределёнными) в любой аксиоматике. Определёнными, не гёделевскими, будут только вычислимые числа.

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

Обоснованность

Аксиоматическая система называется обоснованной, если аксиомы описывают свойства каких-то "понятных" математических объектов. Например, аксиомы Пеано соответствуют свойствам натуральных чисел, поэтому эта аксиоматика считается обоснованной. Аналогично, аксиомы Евклида соответствуют свойствам точек и прямых на плоскости, поэтому они обоснованы. Обоснованность аксиоматической системы важна, потому что даёт основания предполагать её непротиворечивость, несмотря на то, что это не формальный термин, т.к. невозможно формально определить, что такое "понятные" математические объекты.
Действительные числа, как они формализованы в математике (бесконечная десятичная дробь), считаются обоснованной системой, т.к. действительное число соответствует точке на прямой. Поэтому мы предполагаем непротиворечивость этой системы и начинаем изучать её свойства - например, оказывается, что мощность множества действительных чисел больше счётного, их "больше чем бесконечность". Что ж - раз это следует из аксиом, принимаем, множество точек на прямой - какая-то другая бесконечность, "континуум".

Но что если это ошибочная интерпретация, и множество точек на прямой задаёт лишь множество вычислимых чисел? Мы никаким образом не можем на числовой прямой построить точку с невычислимой координатой. Бесконечная десятичная дробь - мы тоже можем привести лишь примеры вычислимых чисел, либо же число оказывается неопределено в рамках выбранной формальной системы (или даже в любой формальной системе). Тогда аксиоматика, определяющая действительное число как бесконечную десятичную дробь, перестаёт быть обоснованной. Континуум превращается в абстрактный термин, не соответствующый никакому математическому объекту, а тогда и изучать его математически незачем. Бесконечность остаётся лишь одна - мощность счётного множества. Количество действительных чисел, алгоритмов, функций - тоже счётно. Мы, конечно, можем придумывать аксиомы, в которых существуют и другие множества, но такие теории переходят из сферы изучения свойств математических объектов в область изучения необоснованных формальных систем, нечто вроде составления бессмысленных предложений из несуществующих слов с соблюдением правил грамматики - занятие гораздо менее интересное, чем построение предложений, обладающих смыслом.

This entry was originally posted at https://gul-kiev.dreamwidth.org/70225.html.
Tags: математика
Subscribe

  • Фейковые криптовалюты

    В многочисленных популярных роликах и текстах, объясняющих принципы работы криптовалют, это объяснение делается на примере Bitcoin - первой из…

  • Взаимодействие между людьми

    Разговаривая про квалиа, вернулся к фантазии про поатомное копирование человека, но посмотрел на неё немного под другим углом, со стороны психологии.…

  • Про Гёделя и Пенроуза (2)

    Второй, но не последний пост на эту тему (чего-то зацепила). В комментариях к предыдущему посту об этом родилась краткая и более изящная версия…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments

  • Фейковые криптовалюты

    В многочисленных популярных роликах и текстах, объясняющих принципы работы криптовалют, это объяснение делается на примере Bitcoin - первой из…

  • Взаимодействие между людьми

    Разговаривая про квалиа, вернулся к фантазии про поатомное копирование человека, но посмотрел на неё немного под другим углом, со стороны психологии.…

  • Про Гёделя и Пенроуза (2)

    Второй, но не последний пост на эту тему (чего-то зацепила). В комментариях к предыдущему посту об этом родилась краткая и более изящная версия…