См. [267].

[369]; см. также НРК, с. 5-14.

См. [340], [341].

Вопрос осложняется тем, что современная физика рассматривает, по большей части, непрерывные, а не дискретные (цифровые) процессы. Самый смысл термина «вычислимость» в данном контексте можно трактовать по-разному. С некоторыми рассуждениями на данную тему можно ознакомиться в [312], [346], [313], [314], [315], [316], [29], [327], [328]. К этому вопросу я еще вернусь в §1.8.

Этой замечательной фразой я обязан диктору ВВС Radio 4, ведущему программу «Мысль дня».

Исследования в области создания ИИ начались в 1950-е годы с весьма успешного применения сравнительно элементарных нисходящих процедур (например, Грей Уолтер, 1953). Распознающий образы «перцептрон» Фрэнка Розенблатта [323] стал в 1959 году первым удачным «связным» устройством (искусственной нейронной сетью), вызвав тем самым значительный интерес к схемам восходящего типа. В 1969 году Марвин Мински и Сеймур Пейперт указали на некоторые существенные ограничения, присущие данному типу восходящей организации (см. [264]). Способ обойти эти ограничения предложил некоторое время спустя Хопфилд [207], и в настоящий момент искусственными устройствами, функционирующими по типу нейронной сети, активно занимаются ученые всего мира. (О применении таких устройств, например, в физике высоких энергий см. [19] и [142].) Что касается ИИ нисходящего типа, то здесь важными вехами стали работы Джона Маккарти [248] и Алана Ньюэлла в сотрудничестве с Гербертом Саймоном [272]. Впечатляющее изложение истории исследований проблемы ИИ можно найти в [124]. Из прочей литературы порекомендую [175], [15] (относительно недавние размышления о процедурах и перспективах ИИ); [98] (классическая критика идеи ИИ); [140] (свежий взгляд на проблему от пионера ИИ); также см. статьи в сборниках [40] и [221].

Описание λ-исчисления см. в [52] и [223].

Из различных публикаций, посвященных данной проблематике, могу порекомендовать, например, [312], [346], [316], [29]. Вопрос о функционировании мозга в связи с упомянутыми проблемами рассмотрен, в частности, в [326].

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

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