Computor и Computer

Несмотря на то, что на рубеже XIX и XX столетий научный авторитет механической парадигмы оставался на очень высоком уровне, идея вычисляемой дискретности постепенно и неотступно завоевывала своё место под солнцем.

Биологи «вдруг» обнаружили, что в описанных Грегором Менделем закономерностях есть полезный смысл, а образованная публика зачитывалась историями о приключениях Шерлока Холмса.

В физике, как мы обсуждали в предыдущей главе, одна за другой стали появляться корпускулярные модели атома; а Эйнштейн объяснил фотоэффект, исходя из дискретной природы света.

В математике у новой парадигмы была своя история.

Джордж Буль, попытавшись облечь законы мышления в математическую форму, указал на возможность вывода аксиом – общих истин, на которые впоследствии можно опереться при построении цепочки доказательств.

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

Например, требуется доказать, что 17 – нечётное число.

Допустим, что 17 – чётное число (отрицание). По определению чётных чисел, 17 должно делиться на 2 без остатка. Выполнив деление, получаем остаток. Значит, 17 не является чётным числом (отрицание отрицания) и является нечётным числом (снятие двойного отрицания = истина).

На самом деле, конечно, нечётность числа 17 следует из его определения: доказательство от противного кажется лишним. Но тут важно зафиксировать, как работают аксиомы в математике и в логике. Иногда, для более сложных случаев, удобнее идти в обход.

Математик Георг Кантор в 1891 году предложил первую версию теории множеств. Об этой теории мы поговорим подробнее в главе 6. А здесь укажем на некоторые её особенности в связи с бинарной логикой.

Вообще для бинарной логики существует простейшее множество {0; 1}, в котором всего два элемента: 0 и 1. Из этого множества можно построить четыре бинарные последовательности: 1,1; 0,1; 1,0; 0,0.

В теории множеств последовательность элементов и их значение не играет никакой роли. Например, множества {0; 1} и {1; 0} равны (эквивалентны).

В логике и в генетике, как мы убедились, это не так. Важно не только сочетание элементов, но и смысл, который мы им присваиваем (например, «1» может быть «истиной» или «рецессивным признаком»).

Однако важнейшее достоинство теории множеств состоит в её универсальности.

Множества могут быть любыми: конечными, как {0; 1}, и бесконечными – если, например, взять ряд натуральных чисел. Из этого, более мощного, множества можно построить те же четыре бинарные последовательности.

Следовательно, одни множества являются подмножествами других множеств: более мощных, конечных и бесконечных. Тогда, например, все возможные логические высказывания есть подмножество всех высказываний на данном языке, а все гены человека – подмножество всех генов человечества.

Некоторые математики были настолько очарованы теорией множеств, что посчитали возможным создать универсальную аксиоматическую математику (и логику заодно). Их назвали «формалистами».

К ним принадлежал, например, великий математик Давид Гильберт, попытавшийся обосновать тезис о существовании в математике абсолютных истин и/или аксиом. Если б замысел Гильберта удался, то вывод математических теорем в наши дни стал бы рутинным заданием в младшей школе.

С формальным подходом не согласились «интуиционисты», посчитавшие абстракции вроде бесконечных множеств бесполезными развлечениями и требовавшие конструирования цепочек непротиворечивых доказательств любых математических объектов.

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

Таким образом, у формалистов закон снятия двойного отрицания и доказательство от противного считались аксиомами, а у интуиционистов не считались таковыми.

Условно говоря: спорили о том, можно или нельзя при разборе классического силлогизма опровергнуть/вычислить высказывание «Все не люди не смертны». При том, что «Все люди смертны» – истина.

Или: число 17 – нечётное по определению (мы договорились считать его таковым), или оно нечётное, потому что это можно доказать от противного (принимаем закон снятия двойного отрицания как абсолютную истину).

Дискуссия заставила математиков задуматься над более серьёзной проблемой: говоря о вычислимой или невычислимой истине, что мы подразумеваем под вычислением?

Состоит ли математика в действительности из дискретных кусочков-высказываний, которые мы комбинируем в разнообразные аксиомы и теоремы?

Или, скажем, под законом снятия двойного отрицания есть более фундаментальный, логический или математический, закон?

В 1931 году математический вундеркинд Курт Гёдель обнародовал свою знаменитую «теорему о неполноте арифметики».

Её следствия, в общем и целом, дали ответы на сформулированные выше вопросы. А эти ответы, в свою очередь, обеспечили неизбежность создание главного символа цифровой парадигмы – компьютера.

Существует несколько формулировок теоремы Гёделя. Ещё больше – изложений её доказательства. И совсем много – её следствий.

Ограничимся кратким пересказом, основанным на анализе теоремы выдающимся математиком Юрием Маниным (подробности см. в его работах¹¹).

Формулируется теорема так: «Полного финитно описываемого набора аксиом в арифметике не существует».

Это утверждение можно выразить иначе, на более привычном языке.

Например:

Можно построить логически непротиворечивую теорию, но нельзя доказать её истинность.

Тогда такое следствие:

Какими бы логичными ни казались, скажем, концепция души или рефлекторная теория мозга, нельзя сформулировать аргументы в пользу того, что они неопровержимо верны.

Или такая формулировка теоремы:

Выразить полностью какую-либо сложную научную теорию при помощи средств любого естественного языка невозможно.

И её следствие:

Если вы не разбираетесь в математике и не собираетесь этого делать, то в случае создания новой научной теории (например, Теории Всего) вы её никогда не поймёте.

Чтобы пояснить, почему формулировка и следствия теоремы Гёделя, выходят так далеко за пределы арифметики, разберёмся с терминами.

Все высказывания (как в математике, так и в любом естественном языке) могут быть неопределёнными и определёнными. О первых сказать, ложны они или истинны, нельзя. О вторых – можно.

Некоторой аналогией тут служит различие между открытыми и закрытыми вопросами. Если вам задают открытый вопрос (начинается с «как», «что такое», «почему» и т.п.), вы не можете содержательно и определённо ответить, сказав «да» или «нет». Однако при ответе на закрытый вопрос («так ли это?», «это случилось там-то?» и т.д.) только эти два варианта имеют смысл.

Таким образом, Гёдель заключил, что все аксиомы в математике – это определённые истинные высказывания (мы назовём их «первичными истинами»). А все, следующие из них высказывания, выраженные на каком-либо естественном языке, – определённые и истинные тоже («вторичные истины»).

Тогда формируются два множества: все «первичные истины» (множество с числом элементов n) и все «вторичные истины» (множество с числом элементов m).

Сформулированный Гёделем вопрос заключается в следующем: можно ли – всегда и во всех случаях – из «вторичной истины» вывести «первичную истину»?

Или так: содержатся ли в наших естественных языках уже все аксиомы, которые мы ещё не успели описать на языке математики?

Короче: существует ли такая формула (способ, правило), которая всегда выводит n из m?

И совсем коротко: n = m?

Курт Гёдель использовал доказательство от обратного и начал с предположения, что n = m. Примерная схема рассуждений представлена на рисунке 10.

Получилось, что всегда и строго n> m.

Итак, Гёдель доказал, что абсолютных, сформулированных людьми, истин не существует: ни в математике, ни, тем более, в естественных языках (интуиционисты удовлетворенно кивнули).

Вместе с тем, он ясно показал, что существует некий, возможно, универсальный процесс создания аксиом – как в математике, так и в естественных языках (формалисты продолжили верить).

Этот универсальный процесс создания аксиом – не что иное, как вычисление. (Джордж Буль думал также, однако именно Гёдель в подтверждение тезиса привел весомые аргументы.)

При этом вычисление может производиться любым, имеющим к этому процессу подходящие инструменты, созданием. В том числе – искусственным устройством.

Через пять лет после появления теоремы о неполноте арифметики Алан Тьюринг опубликовал статью, в которой описал то, что сейчас мы называем компьютером.

Нужно иметь в виду, что представленная в этой работе математическая метафора, «машина Тьюринга», не только и не столько абстрактная модель механического вычислительного устройства.

Это, прежде всего, модель вычислений, производимых человеком. В самом начале статьи читаем: «Мы можем сравнить человека в процессе вычисления (in the process of computing) какого-либо действительного числа с машиной, которая ограничена конечным числом состояний…». ⁶³

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

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

Иными словами, он, как сказал бы Гёдель, переводит первоначальное неопределённое высказывание в определённое, затем – в другое определённое и т. д.

Если в качестве символьной системы для записи в клеточки выбрать бинарный код, а в качестве набора управляющих операций – бинарную логику, то получится общая схема вычислений. Получится механический computer, имитирующий язык и логику живого computor.

Как мы обсуждали в начале главы, Алан Тьюринг не считал, что computer может полностью заменить computor. Здесь поясним это утверждение более обстоятельно.

Дело в том, что механический вычислитель не способен имитировать произвольное построение порядка вычислений. Он не создаёт алгоритм сам. Ему всегда требуется образец.

В какой последовательности применять бинарную логику к бинарным символам решает тот, кто вписывает символы в клеточки. Или даёт указания, как это делать: составляет программу машинных действий, даёт искусственному вычислителю образцы алгоритмов.

Это человек.

Заметим, что это прямое следствие теоремы Гёделя.

Применяя строгие механические формулы, которые ссылаются только на себя, истинно-определённое не выводится (или, по Тьюрингу, не вычисляется). Индуктивная проверка есть не универсальный, а специальный инструмент. Не фундаментальный закон, а технология.

Припомним: следуя бинарной логике Буля, мы избежали сомнительного удовольствия ковыряться в противоречивых смыслах, спрятанных в высказывании «Все не люди не смертны». Как нам это удалось? Мы действовали по алгоритму: вычитание – умножение – сложение. Только такой порядок обеспечил определённый и осмысленный результат.

Если б мы нарушили последовательность или, не дай бог, принялись бы, подобно средневековым схоластам, резонерствовать на тему «кто такие „не люди“?», «что такое смерть?», «что такое жизнь?» и т.п., нам пришлось бы, чтобы прийти к согласию, провести бесконечное число наблюдений.

Но, даже если б мы сделали это, хотя бы в уме, и пришли к некой, абсолютной, истине, которая бы воспринималась нами как полный и окончательный ответ, разъясняющий суть этих понятий, то через некоторое время пришлось бы снова взяться за уточнение – ввязаться в новый диспут.

Ведь, как показал Гёдель, всегда остаётся вероятность, что такие сложные и многозначные понятия, как, например, «люди» и «жизнь», могут дополниться новыми фактами и смыслами. И определить/вычислить их до конца не удастся никогда.

Раз так, то и машина Тьюринга не может этого сделать.

Точнее: она будет это делать, т.к., хоть эти высказывания (числа, функции, задачи) и невычислимы, тем не менее, они вполне реальны. С ними можно производить арифметические операции.

Однако машина Тьюринга будет вычислить их неограниченное время – гораздо дольше, чем Думатель из романа Дугласа Адамса. А именно: вечность.

Вместе с тем, задачи, что машина Тьюринга за конечное время вычислить может, существуют тоже. Они – алгоритмически вычислимы.

Другое дело, что писать алгоритмы для их решения придётся человеку. Потому что и математика, и логика, и новые идеи, как показал Гёдель, суть творческая, бесконечная во времени и по глубине, деятельность.

Прояснение разницы между выводимостью аксиом и их невыводимостью, между вычислимым и невычислимым, между машинным алгоритмом и присущим человеку думанием – несомненная научная заслуга Гёделя и Тьюринга.

Их работы стали предпоследним звеном в длинной цепочке развития идеи вычисляемой дискретности в трудах Лейбница, Буля, Пирса, Кантора, Гильберта, Пуанкаре и других теоретиков.

Оставалось сделать последний шаг: попытаться создать computer (искусственный вычислитель) и computor (живой вычислитель) на практике.