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

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

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

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

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

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

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

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

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

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

Эта версия утверждает, что коллективные методы подвержены «Флупификации», но обходит молчанием индивидуальные методы. Она не говорит, что их невозможно «Флупифицировать», но, по крайней мере, оставляет эту возможность открытой.

Как доказательство против более сильных версий Тезиса Чёрча-Тюринга давайте рассмотрим случай знаменитого индийского математика первой четверти двадцатого века, Шринивасы Рамануяна 1887-1920). Рамануян (рис. 105) родился на юге Индии, в Тамилнаду; он немного изучал математику в старших классах школы. Однажды кто-то, заметив способности мальчика к математике, подарил ему слегка устаревший учебник по математическому анализу, который Шриниваса немедленно проглотил (разумеется, не в буквальном смысле!). После этого Рамануян начал собственные исследования в этой области, и к тому времени, когда ему исполнилось двадцать три года, у него на счету было несколько открытий, которые казались ему важными. Он не знал, к кому обратиться, но однажды он услышал о некоем профессоре математики по имени Г. X. Харди, живущем в далекой Англии. Рамануян записал свои лучшие результаты и послал эту пачку листков ничего не подозревавшему Харди вместе с письмом, которое друзья помогли ему написать по-английски.

Ниже следуют некоторые отрывки, описывающие реакцию Харди, когда он получил эту «посылку»:

Вскоре мне стало ясно, что Рамануян знал гораздо более общие теоремы, но держал их в рукаве… [Некоторые формулы] меня совершенно поразили — я никогда не видел ничего подобного. Одного взгляда на них достаточно, чтобы понять, что они написаны математиком высшего класса. Они, скорее всего, истинны, поскольку никто не может обладать достаточным воображением, чтобы высосать из пальца нечто подобное. Наконец,… автор письма был, по-видимому, абсолютно честен, поскольку гениальные математики встречаются чаще, чем шарлатаны, обладающие таким невероятным талантом. [49] James R. Newman «Srinivasa Ramanujan» В сборнике James R. Newman, ed «The World of Mathematics» (New York Simon and Schuster, 1956) Toм I, стр. 372-3

Результатом этой переписки был приезд Рамануяна в Англию в 1913 году по приглашению Харди и начало тесного сотрудничества между ними, которое было прервано преждевременной смертью Рамануяна от туберкулеза в возрасте тридцати трех лет.

Среди прочего, Рамануян отличался от большинства математиков тем, что его доказательствам не хватало строгости. Иногда он просто называл результат, полученный, по его словам, чисто интуитивно, без какого бы то ни было сознательного поиска. Часто Рамануян говорил, что богиня Намагири сообщила ему ответ во сне. Это повторялось снова и снова, и самое удивительное — даже мистическое — заключалось в том, что многие из его «интуитивных теорем» оказывались ложными ! В связи с этим интересен парадокс, заключающийся в том, что иногда событие, которое, как кажется, должно было бы добавить доверчивым людям немного скептицизма, в действительности вызывает обратный эффект. Оно затрагивает эти доверчивые души, соблазняя их намеками на некие удивительные, иррациональные свойства человеческой природы. Именно это произошло с ошибками Рамануяна; многие образованные люди, жаждущие поверить в чудеса, увидели в интуитивных способностях Рамануяна доказательство его мистического прозрения и знания Истины — и его ошибки только усилили их веру.