Доказательство как вычисление

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

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

Доказательство как вычисление

Еще в ХVII в. Г. В. Лейбниц высказал идею представить логическое доказательство как «игру со знаками». Эта «игра» должна осуществляться по простым правилам, напоминающим правила вычисления в математике и принимающим во внимание только внешний вид знаков. Лейбниц верил, что если это удастся, наступит золотой век, когда с помощью новой логики самые сложные и отвлеченные проблемы будут «вычисляться» так же легко, как в математике вычисляется сумма чисел. Эта программа формализовать доказательство и тем самым перестроить логику по образцу математики намного опережала свое время и начала реализовываться только двести лет спустя.

Строя доказательства, мы опираемся на интуитивную логику и постоянно обращаемся к содержательному значению используемых понятий, их смыслу. Но смысл — трудноуловимая вещь. Нередко он расплывчат и неопределенен, может истолковываться по­разному и меняться в ходе рассуждения. Чтобы сделать доказательство предельно строгим, нужно свести оперирование смыслами, недоступными наблюдению, к действиям над вещественными, хорошо обозримыми объектами. Для этого требуется выявить все используемые нами принципы интуитивной логики и представить их в виде простых правил преобразования последовательностей знаков, записанных на бумаге. Рассуждение превратится при этом в предметные действия над цепочками знаков.

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

Некоторое время на формализованные доказательства возлагались большие надежды. Предполагалось, что удастся формализовать математические доказательства и затем доказать непротиворечивость математики. Эта программа называлась «формализмом» и противопоставлялась как попыткам свести математику к логике (логицизм), так и намерению сориентировать математику на особую наглядно­содержательную интуицию (интуиционизм). Предложенная формализмом программа обоснования математики оказалась, однако, утопией. Достаточно богатая содержательная теория (охватывающая хотя бы арифметику натуральных чисел) не может быть полностью отображена в ее формализованной версии: как бы ни пополнялась последняя дополнительными утверждениями (новыми аксиомами), в теории всегда останется не выявленный, неформализованный остаток. Но об этом речь пойдет далее.

Как мыслит машина

Когда стали появляться все более совершенные вычислительные машины, производящие миллионы операций в секунду, очень популярным был вопрос: может ли машина мыслить? Не окажется ли в недалеком будущем так, что существенно усовершенствованная вычислительная машина начнет мыслить, как человек, а потом и превзойдет его в сфере мышления? В сфере, считающейся отличительной особенностью человека. Ведь человек, согласно его определению, восходящему еще к античности, — всего лишь разумное животное.

Проблема «машинного мышления» вызывала какое­то время бурные дискуссии, преимущественно в околонаучных кругах. Теперь споры совершенно затихли, хотя иногда люди, далекие от математики и логики, задумываются над вопросом о том, не станет ли с течением времени бурно прогрессирующая вычислительная техника «лучшим мыслителем», чем ее создатель — человек. Во всяком случае в шахматах вычислительные

Как мыслит машина

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

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

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

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

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

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

Алгоритм представляет собой систему правил (предписаний) для эффективного решения некоторого класса однотипных задач.

Предполагается, что алгоритм обладает свойствами массовости, детерминированности и результативности. Массовость означает, что данные задач могут в определенных пределах изменяться. Алгоритм связан с решением общей проблемы, в условия которой входят варьирующиеся параметры. Ответ «да» или «нет» на проблему дается не прямо, а косвенно, в зависимости от значений параметров, в общем случае допускающих счетно­бесконечное множество значений. Точное описание алгоритма предполагает указание на множество возможных значений параметров проблемы, т. е. тех частных вопросов, на которые она распадается. Детерминированность алгоритма выражается в том, что, когда заданы алгоритм и значения параметров, или, иначе говоря, выбран частный случай проблемы, процесс решения идет чисто формально (механически) и во всех деталях известны последовательность и содержание конкретных шагов работы алгоритма. Алгоритмический процесс изолирован от воздействия извне, так что детерминированность исключает возможность произвольных решений. Именно эта особенность алгоритма делает его синонимом автоматически работающей машины. Результативность алгоритма означает, что на каждом шаге процесса применения правила известно, что считать его результатом.

Проблему, рассматриваемую в свете поиска алгоритма ее решения, называют алгоритмической. Когда алгоритм предложен, возникает вопрос: всегда ли ответы по данному алгоритму будут ответами на частные вопросы рассматриваемой алгоритмической проблемы? Если удается доказать соответствие алгоритма данной проблеме, алгоритмическую проблему считают разрешимой посредством алгоритма, или алгоритмически разрешимой.

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

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

Однако в первой половине ХХ в. было доказано, что далеко не каждая из даже собственно математических или логических проблем является алгоритмически разрешимой. Тем самым надеждам на универсальную замену человеческого мышления «машинным мышлением» был положен конец. Этому предшествовало уточнение понятия алгоритма в рамках строгой математической теории алгоритмов, уяснение принципиальной завершенности поиска средств, привлекаемых для решения алгоритмических проблем, и одновременно признание существования алгоритмически «абсолютно неразрешимых» проблем. Уточнение понятия алгоритма и границ области алгоритмически разрешимых проблем явилось мощным стимулом для дальнейшего развития теории алгоритмов.

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

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

Как мыслит машина

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

Формализованное доказательство — это доказательство, записанное на специальном искусственном — формализованном — языке. Он имеет точно установленную структуру и простые правила, благодаря чему процесс доказательства сводится к элементарным операциям со знаками.

Формализованное доказательство — это идеальное и неоспоримое доказательство. Но насколько реалистичен этот идеал, не слишком ли формализованные рассуждения отходят от обычных научных рассуждений? Можно ли полностью формализовать любую научную теорию?

Ответы на эти вопросы были получены в 30­е годы, когда был установлен ряд теорем, принципиально ограничивающих формализацию. Наиболее важная из них принадлежит австрийскому математику и логику К. Гёделю. В 1931 г. он показал, что любая достаточно богатая по содержанию и являющаяся непротиворечивой теория неизбежно неполна: она не охватывает все истинные утверждения, относящиеся к ее области. Теорема Гёделя непосредственно относилась к арифметике и утверждала, что существует имеющее смысл утверждение арифметики целых чисел (обозначим это утверждение буквой С), которое в рамках данной теории нельзя ни доказать, ни опровергнуть. Но либо утверждение С, либо утверждение не­С истинно. Следовательно, в арифметике существует истинное утверждение, которое недоказуемо, а значит, и неразрешимо.

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

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

Теорема Гёделя иногда истолковывается как свидетельство какойто внутренней, непреодолимой ограниченности человеческого мышления. Такая пессимистическая интерпретация безосновательна. Теорема устанавливает границы только «машиноподобного», «вычисляющего» разума. Вместе с тем она косвенно говорит о могуществе творческого разума, способного создавать новые понятия и методы для решения принципиально новых проблем.