Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
(Am) n = m + n ,
(Mm) n = m x n ,
(Pm) n = n m ,
где m и n — функции Черча для двух натуральных чисел, m + n — функция, выражающая их сумму, и т. д. Последняя из этих функций поражает больше всего. Посмотрим, например, что она дает в случае m = 2, n = 3 :
Операции вычитания и деления определяются не так легко (на самом деле нам потребуется соглашение о том, что делать с ( m — n ),
Это воистину замечательный факт, который подчеркивает глубоко объективный и математичный характер понятия вычислимости. На первый взгляд, понятие вычислимости по Черчу не связано с вычислительными машинами. И тем не менее, оно имеет непосредственное отношение к практическим аспектам вычислений. В частности, мощный и гибкий язык программирования LISP включает в себя как существенный элемент основные структуры исчисления Черча.
Как я отмечал ранее, существуют и другие способы определения понятия вычислимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной машины. Тогда же благодаря работам Дж. Хербранда и Геделя появилось и более практичное определение вычислимости (рекурсивности). X. Б. Карри в 1929 году, и ранее, в 1924, М. Шенфинкель, предложили иной подход, который был отчасти использован Черчем при создании своего исчисления (см. Ганди [1988]). Современные подходы к проблеме вычислимости (такие как машина с неограниченным регистром, описанная Катлендом [1980]) в деталях значительно отличаются от разработанного Тьюрингом и более пригодны для практического использования. Однако понятие вычислимости во всех этих подходах остается неизменным.
Как и многие другие математические идеи, особенно наиболее фундаментальные и красивые, идея вычислимости кажется овеществленнойи объективно существующей в платоновскомсмысле. Именно к этому мистическому вопросу о платоновской реальности математических понятий мы и обратимся в следующих двух главах.
Глава 3
Математика и действительность
Страна Тор'Блед-Нам
Представим себе, что мы совершаем большое путешествие в некий далекий мир. Назовем его Тор'Блед-Нам. Наша телеметрическая система зарегистрировала сигнал, вывела его на монитор и, отфокусировав изображение, мы увидели следующую картину (рис. 3.1):
рис. 3.1. Первый взгляд на новый мир
Что бы это могло быть? Странного вида насекомое? А может быть, темное озеро с многочисленными втекающими в него ручьями? Или огромный причудливой формы внеземной город, с исходящими в разных направлениях дорогами, которые ведут в расположенные поблизости городки и деревушки? Возможно, это остров — и если это так, то давайте поищем поблизости континент, с которым он связан. Для этого «отойдем назад», т. е. уменьшим увеличение наших приборов раз в 15. И вот — посмотрите-ка — этот новый мир предстал перед нашим взором во всей своей полноте (рис. 3.2):
Рис. 3.2. Общий вид Тор'Блед-Нам. Стрелками
отмечены области, увеличенные изображения которых
даны на рис. 3.1, 3.3 и 3.4
На рис. 3.2 наш «островок» выглядит как маленькая точка под стрелкой «рис. 3.1». Все волокна (ручьи, дороги, мосты?), исходящие из первоначального островка, обрываются, за исключением одного — того, что выходит из внутренней части расположенной справа расщелины, и который, в свою очередь, соединен с объектом гораздо большего размера (он изображен на рис. 3.2). Последний, как нетрудно заметить, подобен первоначальному островку, хотя их формы несколько отличаются. При более подробном рассмотрении «береговой линии» выявляются бесчисленные округлые выступы, края которых, в свою очередь, густо усеяны выступами такой же формы. Каждый маленький выступ соединен в каком-нибудь месте с более крупным, и все вместе они образуют бородавчатую структуру, где более крупные выступы покрыты наростами помельче, те — еще более мелкими и т. д. По мере того, как картина становится все более отчетливой, мы видим мириады мельчайших волокон, исходящих из рассматриваемой структуры. Сами волоконца ветвятся в разных местах,
Давайте исследуем один из наростов у нашего насекомого, для чего увеличим разрешение примерно в десять раз (см. рис. 3.3 — соответствующая область на рис. 3.2. отмечена как «рис. 3.3»).
Рис. 3.3. Бородавка
с «пятеричностью» своих волоконцев
Своим видом нарост сильно напоминает все существо целиком, за исключением места соединения. Обратите внимание, что на рис. 3.3 имеется множество точек, в которых сходятся пять волокон. По-видимому, этому конкретному наросту свойственна некая «пятеричность» (точно также как для самой верхней «бородавки» на рис. 3.2 характерна определенная «троичность»). На самом деле, если исследовать (на рис. 3.2) расположенный чуть ниже и левее следующий разумного размера нарост, то мы обнаружим у него «семеричность», а у следующего — характерную «девятеричность» и т. д. При углублении во впадину между двумя самыми крупными областями на рис. 3.2, справа будут встречаться наросты с постоянно нарастающим нечетным числом лучей. Давайте всмотримся внимательно вниз вглубь заостренной впадины, повысив увеличение еще в десять раз по сравнению с рис. 3.2 (рис. 3.4).
Рис. 3.4. Главная впадина. «Долина морских
коньков» едва различима справа внизу
Мы обнаружим множество других мельчайших наростиков на фоне общего беспорядочного завихрения. Справа видны едва различимые спиралевидные структуры, напоминающие «хвосты морских коньков», расположенные в области, которую мы так и назовем — «долина морских коньков». Здесь нам встретятся — если смотреть на это место при достаточно большом увеличении — разнообразные «морские анемоны» или области с богатой флорой. В конце концов, перед нами действительно может быть какой-то экзотический берег — возможно, коралловый риф, изобилующий всевозможными формами жизни. Объект, принятый нами за цветок, при более сильном увеличении может оказаться состоящим из мириада мельчайших и при этом невероятно сложных структур, с многочисленными волокнами и вихреобразными спиралевидными хвостами. Давайте рассмотрим подробнее один из более крупных хвостов морских коньков, а именно — едва различимое образование, обозначенное на рис. 3.4 как «рис. 3.5» (и соединенное с 29-ричным наростом!). Повысив увеличение в 250 раз, мы увидим изображенную на рис. 3.5 спираль.
Рис. 3.5. Хвост «морского конька» крупным планом
При этом окажется, что это не обычный хвост: и он тоже состоит из сложнейших вихреобразных структур с многочисленными мельчайшими спиралями и областями в форме осьминогов и морских коньков!
Рис. 3.6. Дальнейшее увеличение места соединения
спиралей. В центре едва различим маленький детеныш
Во многих местах видно, что исследуемые нами структуры расположены точно в том месте, где сходятся две спирали. Рассмотрим одно такое место (обозначенное как «рис. 3.6» на рис. 3.5) с дополнительным 30-кратным увеличением. Посмотрите-ка: в самой середине теперь виднеется странный объект, в котором, однако, есть что-то знакомое. Увеличим изображение еще в шесть раз (рис. 3.7) — появляется крохотный дочерний объект, практически идентичный всей структуре!
Рис. 3.7. При увеличении детеныш обнаруживает
сходство с целым миром
При более внимательном рассмотрении обнаруживаются некоторые отличия присоединенных к этой субструктуре волокон от тех, что выходят из основной структуры, — новые волокна, закручиваясь, уходят на значительно большие относительные расстояния. И при этом маленькое существо выглядит почти неотличимым от своего родителя, — у него даже есть аналогично расположенные собственные детеныши. Можно было бы исследовать и их, если вновь повысить увеличение приборов. «Внуки» тоже будут напоминать своего общего предка — и нетрудно увидеть, что так может продолжаться до бесконечности. Этот странный мир Тор'Блед-Нам можно исследовать как угодно долго, постоянно увеличивая разрешающую способность нашей системы наблюдения. И тогда перед нами предстанет бесконечное разнообразие: никакие две области не являются в точности одинаковыми, но всем им свойственны общие черты, которые очень быстро становятся узнаваемыми. Знакомые нам уже жукообразные существа появляются на все меньших и меньших масштабах. Каждый раз при этом расположенные рядом волокнистые структуры отличаются от предыдущих, демонстрируя новые фантастические сцены невероятной сложности.