Новый ум короля: О компьютерах, мышлении и законах физики

Рис. 5.9.«Переключатель» (конструкции А. Ресслера) в компьютере Фредкина — Тоффоли на бильярдных шарах. Если шар попадает в переключатель через вход В, то в дальнейшем он покидает переключатель через выход D или Е в зависимости от того, попадает ли другой шар в переключатель через вход А(предполагается, что шары попадают в переключатель через входы А и В одновременно)

В модели Фредкина — Тоффоли все основные логические операции компьютера могут выполняться с помощью шариков. Модель позволяет имитировать вычисления, производимые любой машиной Тьюринга: конкретный выбор машины Тьюринга Т_u определяет конфигурацию «стенок» и т. д. в машине Фредкина — Тоффоли; начальное состояние движущихся шариков соответствует информации на входной ленте машины Тьюринга; а содержимое на выходной ленте соответствует конечному состоянию шариков. Таким образом, можно, в частности, спросить: останавливается ли когда-нибудь такая-то и такая-то машина Тьюринга? «Остановка» может быть сформулирована как состояние при котором шарик А сталкивается, в конце концов, с шариком В. То, что на этот вопрос невозможно ответить алгоритмически (см. гл.2 «Неразрешимость проблемы Гильберта»), по крайней мере наводит на мысль о том, что ньютоновский вопрос «сталкивается ли когда-нибудь шарик А с шариком В?», который был поставлен мной первоначально, тоже не может быть разрешен алгоритмически.

В действительности, ньютоновская задача является гораздо более каверзной, чем задача, поставленная Фредкином и Тоффоли. Эти авторы могли задавать состояние своей модели с помощью дискретных параметров (т. е. при помощи утверждений «да или нет» типа «шарик либо находится в данном туннеле, либо не находится»). Но в полной ньютоновской задаче начальные положения и скорости шариков необходимо задавать с бесконечной точностью в терминах координат, которые являются действительными числами, а не принимают дискретные значения. Таким образом, мы снова сталкиваемся со всеми проблемами, которые нам уже приходилось рассматривать, когда в главе 4 мы пытались ответить на вопрос, рекурсивно ли множество Мандельброта. Что означает«вычислимость», когда в качестве входных и выходных данных допускаются непрерывно изменяющиеся параметры? [111]Проблему можно слегка облегчить, предположив, что все начальные положения и скорости заданы рациональными числами (хотя нельзя ожидать, что координаты и компоненты скорости останутся рациональными в более поздние рациональные моменты времени t). Напомним, что рациональное число представимо в виде отношения двух целых чисел и, следовательно, определяется в дискретных конечных терминах. Используя рациональные числа, мы можем сколь угодно точно аппроксимировать любые наборы начальных данных, которые собираемся использовать в своих вычислениях. И предположение о том, что при рациональных начальных данных может не существовать алгоритма, позволяющего определить, столкнутся в конце концов или нет шарики А и В, — отнюдь не лишено смысла.

Однако на самом деле, когда говорят: «Ньютонианский бильярдный мир не вычислим», имеют в виду совсем другое. Та модель, которую я сравниваю с ньютонианским бильярдным миром — а именно, «бильярдный компьютер» Фредкина — Тоффоли — действует как вычислительный алгоритм. В конечном счете, это и было квинтэссенцией идеи Фредкина и Тоффоли — что их модель должна вести себя как (универсальный) компьютер! Вопрос, который я пытаюсь сейчас прояснить, сводится к следующему: можно ли представить себе, что человеческий мозг, используя некоторые подходящие «невычислимые» физические законы, работает в определенном смысле «лучше», чем машина Тьюринга? Бесполезно пытаться использовать что-нибудь вроде следующего утверждения:

«Если шарик А никогда не сталкивается с шариком В, то ответ на Ваш вопрос будет: „нет“».

Чтобы окончательно удостовериться в том, что шарик А действительно никогда не сталкивается с шариком В, пришлось бы прождать вечность! Разумеется, машины Тьюринга ведут себя именно так.