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

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

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

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

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

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

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

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

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

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