Благодаря работам Тьюринга [1518] и Гёделя [566] широко известно, что на некоторые математические вопросы нельзя даже в принципе найти ответ в рамках конкретных формальных систем. При этом наибольшую известность получила теорема Гёделя о неполноте (см. раздел 9.5). Кратко эту теорему можно сформулировать таким образом: для любой формальной аксиоматической системы F, достаточно мощной для того, чтобы в ней можно было представить арифметику, возможно сконструировать так называемое "предложение Гёделя" G(F) с описанными ниже свойствами.

•    G(F) — это предложение системы F, но оно не может быть доказано в рамках F.

•    Если система F является непротиворечивой, то предложение G(F) — истинно.

Философы, в том числе Дж. Р. Лукас [960], утверждали, что эта теорема показывает, будто машины как мыслящие субъекты всегда будут стоять ниже людей, поскольку машины — это формальные системы, ограниченные в силу теоремы о неполноте (они не способны установить истинность относящегося к ним самим предложения Гёделя), а люди не имеют такого ограничения. Споры вокруг данного утверждения продолжались несколько десятилетий и породили огромное количество литературы, в том числе две книги математика сэра Роджера Пенроуза [1204], [1205], повторившего это утверждение с некоторыми новыми выкрутасами (такими как гипотеза, согласно которой человек отличается от машины, поскольку его мозг действует на основе квантовой гравитации). В этой главе мы рассмотрим только три из основных проблем, связанных с этим утверждением.

Во-первых, теорема Гёделя о неполноте распространяется только на формальные системы, достаточно мощные для того, чтобы в них можно было представить арифметику. К таким формальным системам относятся машины Тьюринга, поэтому утверждение Лукаса частично основано на том предположении, что компьютеры представляют собой машины Тьюринга. Это — хорошая аппроксимация, но не совсем оправданная. Машины Тьюринга являются бесконечными, а компьютеры конечны, поэтому любой компьютер может быть описан как (очень большая) система в пропозициональной логике, на которую не распространяется теорема Гёделя о неполноте.

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