Теорема Геделя о неполноте [Jacov A. Smorodinskiy] (fb2) читать постранично, страница - 3

Во-первых, "геделевские аргументы" требуют, чтобы алгоритм был, хотя бы в принципе, познаваем. А кто сказал, что встроенный в головы математиков алгоритм они (математики) могут познать? Может быть, выбор только в том, чтобы верить или не верить в это? Далее, в рассуждениях было нужно, чтобы алгоритм на самом деле был правильным. А если в наши головы встроен алгоритм, но он неправильный (то есть иногда делает ошибки)? (Между прочим, к этой точке зрения склонялся Тьюринг. Сам же Гедель считал, что математическая интуиция в принципе может быть сведена к некоей "теоремной машине", но доказать этот факт будет невозможно, даже случайно обнаружив эту "машину".) И так далее... Следующие 130 страниц посвящены анализу всех этих возражений, - причем рассматриваются не только "обычные", но и вероятностные алгоритмы, эволюционные вычисления, квантовые вычисления, вычисления с оракулом...

Пенроуз аргументирует очень развернуто и конкретно, что и дает прекрасные возможности для критики в его адрес. И критика сразу же начинается - жесткая и, я бы даже сказал, свирепая. Разбирать здесь аргументы и контраргументы невозможно, и не нужно. Ясно одно - Пенроуз играет честно. Он собрал всю известную ему критику его предыдущих работ, добавил к ней несколько возражений, придуманных им самим, и отвечает по пунктам и с формулами. Через два года после выхода книги, в 1996 году, в журнале "Psyche" (реферируемый онлайновый научный журнал: http://psyche.cs.monash.edu.au/index.html) прошла большая дискуссия по ней с участием крупнейших специалистов. Интересно, что вся критика касалась только первой части (отрицательной программы). Один из участников, очень известный специалист по математической логике С. Феферман (S. Feferman), нашел формальную ошибку в одном из рассуждений Пенроуза. В статье "Ни тени сомнения" (!) в "Psyche" (http://psyche.cs.monash.edu.au/v2/psyche-2-23-penrose.html) Пенроуз ответил на все возражения и показал, что найденную ошибку можно исправить, не жертвуя основными выводами.

Оставляя в стороне математические аргументы, я хочу упомянуть только о двух моментах. Первый связан с непознаваемостью алгоритма. Очень трудно логически аргументировать против того, что у нас в головах есть некий непознаваемый и несознаваемый алгоритм, который управляет "математическим мышлением". К непознаваемому алгоритму нельзя непосредственно применить теорему Геделя... Но, не отказываясь от виртуозной логической аргументации, Пенроуз спрашивает: почему мы должны всеми силами держаться за саму идею "алгоритмичности" нашего мышления? Что в ней такого уж естественного? Каким образом, например, мог "универсальный математический алгоритм" возникнуть в процессе эволюции? Зачем природа могла снабдить охотника на мамонтов сверхсложным аппаратом, уже содержащим, в определенном смысле, и неевклидову геометрию, и К-теорию?.. Не проще ли предположить, что в процессе естественного отбора совершенствовался некий универсальный механизм понимания?..

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

Итак, центральная тема первой части - невычислимое против вычислимого. В математике много невычислимого, но, главным образом, в весьма абстрактных ее разделах. Пример, который приводит Пенроуз для иллюстрации того, что такое невычислимость, показан на рис. 3. Он построен на совершенно элементарном материале - задаче о покрытии плоскости плитками полиомино. Сравнительно недавно было доказано, что эта задача алгоритмически неразрешима. То есть не существует алгоритма, который бы получал на вход набор плиток, а на выходе выдавал бы "да" или "нет", в зависимости от того, можно ли замостить плоскость плитками из этого набора без зазоров и перекрытий. На рис. 1 показано, как можно построить абсолютно детерминированную "эволюцию" наборов плиток, не описываемую никаким алгоритмом.

Невычислимая эволюция "игрушечной Вселенной", состоящей из наборов плиток полиомино. Все наборы занумерованы; эволюция происходит по закону: Sn-> Sn+1, если плитки из набора Sn покрывают плоскость без зазоров и перекрытий, и Sn-> Sn+2 в противном случае.

(Из книги R. Penrose, "Shadows of the Mind".)