: может ли алгоритм решить, что данная программа имеет «бесконечный цикл», который не позволит ей когда-либо закончиться?
[48]Предложенное Тьюрингом доказательство того, что никакой алгоритм не может решить проблему остановки[49], невероятно важно для основ математики, но, как представляется, никак не связано с вопросом о том, могут ли компьютеры быть интеллектуальными. Одна из причин этого утверждения заключается в том, что то же базовое ограничение, судя по всему, применимо и к мозгу человека. Предложив человеческому мозгу создать точную модель себя, моделирующего себя, моделирующего себя и т. д., вы загоняете себя в тупик. Лично меня никогда не беспокоило то, что я на это не способен.
Таким образом, сосредоточение на решаемых задачах вроде бы не налагает никаких ограничений на ИИ. Оказывается, однако, что решаемая — не значит простая. Специалисты в области компьютерных наук много размышляют о сложности задач, то есть о том, какой объем вычислений необходим, чтобы решить задачу самым эффективным методом. Вот простая задача: найдите в списке из 1000 чисел наибольшее. Если на проверку любого числа требуется одна секунда, то решение этой задачи очевидным методом — проверять каждое число по очереди, запоминая наибольшее, — потребует 1000 секунд. Возможен ли более быстрый метод? Нет, потому что, если метод не проверит какое-нибудь число из списка, это число может оказаться наибольшим и метод потерпит неудачу. Итак, время поиска самого большого элемента пропорционально длине списка. Специалист по компьютерам сказал бы, что эта задача имеет линейную сложность, что означает, что она очень проста; затем он попробовал бы найти что-нибудь более интересное.
Теоретиков-компьютерщиков восхищает факт, что многие задачи, как представляется[50], в худшем случае имеют экспоненциальную сложность. Из этого следует, что, во-первых, все алгоритмы решения этих задач, о которых нам известно, требуют экспоненциального времени — а именно, количество времени растет по экспоненте с размером входных данных; во-вторых, все теоретики в области компьютерных наук совершенно уверены, что более эффективных алгоритмов не существует.
Экспоненциальный рост трудности означает, что задачи могут быть решаемыми в теории (то есть они, безусловно, разрешимы), но иногда неразрешимыми на практике; мы называем такие задачи неразрешимыми. Примером служит задача принятия решения, можно ли раскрасить данную карту только тремя цветами так, чтобы никакие два соседних участка не были одного цвета. (Хорошо известно, что раскрашивание четырьмя цветами всегда возможно.) Если участков миллионы, может оказаться, что бывают случаи (не все, но некоторые), требующие порядка 2