ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Здесь необходимо понимание того, что важно и что неважно; с этим связано чувство простоты и красоты. Откуда берутся эти интуитивные понятия? Каким образом они могут родиться из формальной системы мозга? В Диалоге «Магнификраб» мы встречаемся с некими необычными свойствами Крабьего мозга. По его словам, он просто слушает музыку и отличает красивые мелодии от некрасивых. (По-видимому, для него существует четкая граница.) Ахилл, однако, находит другой способ описания Крабьих способностей: Краб подразделяет суждения теории чисел на истинные и ложные. Но Краб утверждает, что если он это и делает, то только случайно, поскольку он в математике профан. Ахилл более всего удивлен тем, что Краб, как кажется, прямо нарушает знаменитую теорему метаматематики:

ТЕОРЕМА ЧЁРЧА: Не существует универсального метода, позволяющего отличать теоремы ТТЧ от не-теорем.

Это утверждение было доказано в 1936 году американским логиком Алонзо Чёрчем, оно находится в тесной связи с тем, что я называю:

ТЕОРЕМОЙ ТАРСКОГО-ЧЁРЧА-ТЮРИНГА: Не существует универсального метода, позволяющего отличать истинные суждения теории чисел от ложных.

Тезис Чёрча-Тюринга

Чтобы лучше понять Теорему Чёрча и Теорему Тарского-Чёрча-Тюринга, рассмотрим сначала одну из идей, на которых они основаны, — Тезис Чёрча-Тюринга (часто называемый «Тезисом Черча») Это, безусловно, одно из важнейших понятий в философии математики, мозга и мышления.

Этот Тезис напоминает чай тем, что его можно сделать разных степеней крепости. Я изложу здесь различные версии и мы увидим, что из них вытекает.

Первая версия звучит весьма невинно и, пожалуй, даже бессмысленно:

ТЕЗИС ЧЁРЧА-ТЮРИНГА, ТАВТОЛОГИЧЕСКАЯ ВЕРСИЯ: Математические задачи можно решать только математическими методами.

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

ТЕЗИС ЧЁРЧА-ТЮРИНГА, СТАНДАРТНАЯ ВЕРСИЯ: Предположим, что существует метод при помощи которого разумное существо может разделять числа на два класса. Предположим также, что этот метод всегда приводит к ответу за конечный отрезок времени, и что этот ответ — всегда один и тот же для одного и того же числа. В таком случае существует некая конечная программа на Флупе (то есть, некая общерекурсивная функция), которая будет давать точно такие же ответы, как и разумное существо.

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

Версия Коллективных Процессов

Некоторые люди могут подумать, что предыдущая версия утверждает слишком много. Такие люди могли бы сформулировать свои возражения следующим образом: «Может существовать некто, подобный Крабу, — некто с почти мистической математической интуицией, кто при этом не умеет объяснить своих удивительных способностей. Возможно, что в мозгу такого человека происходят процессы, непредставимые на Флупе.» Идея заключается в том, что, возможно в нас заложен подсознательный потенциал для совершения вещей, превосходящих сознательные процессы — и это невозможно выразить с помощью элементарных операций Флупа. Для тех, кто выдвигает подобные возражения, мы сформулируем более слабую версию Тезиса, различающую индивидуальные и коллективные мыслительные процессы: