•    Каковы формальные правила формирования правильных заключений?

•    Как определить пределы вычислимости?

•    Как проводить рассуждения с использованием недостоверной информации?

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

Истоки идей формальной логики можно найти в работах философов древней Греции (см. главу 7), но ее становление как математической дисциплины фактически началась с трудов Джорджа Буля (1815-1864), который детально разработал логику высказываний, или булеву логику [149]. В 1879 году Готтлоб Фреге (1848-1925) расширил булеву логику для включения в нее объектов и отношений, создав логику первого порядка, которая в настоящее время используется как наиболее фундаментальная система представления знаний. Альфред Тарский (1902—1983) впервые ввел в научный обиход теорию ссылок, которая показывает, как связать логические объекты с объектами реального мира. Следующий этап состоял в определении пределов того, что может быть сделано с помощью логики и вычислений.

Первым нетривиальным алгоритмом считается алгоритм вычисления наибольшего общего знаменателя, предложенный Евклидом. Исследование алгоритмов как самостоятельных объектов было начато аль-Хорезми, среднеазиатским математиком IX столетия, благодаря работам которого Европа познакомилась с арабскими цифрами и алгеброй. Буль и другие ученые широко обсуждали алгоритмы логического вывода, а к концу XIX столетия уже предпринимались усилия по формализации общих принципов проведения математических рассуждений как логического вывода. В 1900 году Давид Гильберт (1862—1943) представил список из 23 проблем и правильно предсказал, что эти проблемы будут занимать математиков почти до конца XX века. Последняя из этих проблем представляет собой вопрос о том, существует ли алгоритм для определения истинности любого логического высказывания, в состав которого входят натуральные числа. Это — так называемая знаменитая проблема поиска решения (Entscheidungsproblem). По сути, этот вопрос, заданный Гильбертом, сводился к определению того, есть ли фундаментальные пределы, ограничивающие мощь эффективных процедур доказательства. В 1930 году Курт Гёдель (1906—1978) показал, что существует эффективная процедура доказательства любого истинного высказывания в логике первого порядка Фреге и Рассела, но при этом логика первого порядка не позволяет выразить принцип математической индукции, необходимый для представления натуральных чисел. В 1931 году Гёдель показал, что действительно существуют реальные пределы вычислимости. Предложенная им теорема о неполноте показывает, что в любом языке, достаточно выразительном для описания свойств натуральных чисел, существуют истинные высказывания, которые являются недоказуемыми, в том смысле, что их истинность невозможно установить с помощью какого-либо алгоритма.