Могут ли машины мыслить?

10.

Здесь речь идет о так называемых (в современной терминологии) алгоритмически неразрешимых проблемах. Вот пример неразрешимой проблемы, который я изложу здесь в терминах «повседневного» компьютера. Требуется составить программу U, которая бы по любому подаваемому ей на вход файлу X, содержащему текст программы (на каком-нибудь языке программирования, скажем, стандартном ANSI С), определяла бы, остановится ли когда-нибудь программа из файла Х в процессе своей работы, получив на вход известные данные, или «зациклится». Если программа Х зациклится, то программа U должна показать на экране фотографию юноши, иначе – девушки, после чего закончить свою работу. (Такого рода «проверяющая на зацикливаемость» программа U. была бы, очевидно, довольно полезна для проверки создаваемых компьютерных программ.) Оказывается, написать эту «проверяющую программу» U невозможно в принципе (даже если допустить, что компьютер, на котором выполняется U, имеет сколь угодно большую память и может работать неограниченно (астрономически) долгое время). Приведенный пример (так называемая «неразрешимость проблемы остановки») впервые был рассмотрен в цитированной выше работе Тьюринга 1936 г. – в то время, когда еще не было никаких компьютеров и программ для них!