Алан Тьюринг показал, что число вычисляемых функций счетно; поскольку число всех функций несчетно, то подавляющее большинство функций нельзя вычислить на машине Тьюринга. Среди них находится так называемая функция остановки — по описанию программы определить произойдет ли ее нормальное завершение или нет.
Далее Тьюринг работал вместе с Алонзо Чёрчем. В диссертационной работе ‘Логические системы, основанные на ординальных числах‘ были введены гипотетические машины Тьюринга с оракулом:
‘Давайте представим, что мы обладаем некими неведомыми средствами решения [неразрешимых] теоретико-числовых задач; своего рода оракулом, как бывало прежде. Не вдаваясь в природу этого оракула, скажем только, что он не может быть машиной. С помощью оракула мы могли бы создать новый вид машины (назовем их o-машинами), одной из основных операций которой является решение данной теоретико-числовой задачи.’
Использование оракула для разрешения проблемы остановки позволило создать новый класс математических структур; вопрос соответствия этих структур реальным вычислениям не ставился. Это является хорошим примером чистой математики и исследования возможностей машины Тьюринга с оракулом продолжаются до настоящего времени.
В то же время это вдохновило более практически настроенных граждан на поиск возможности создания физического устройства, которое будет способно вычислять функции, невычислимые машиной Тьюринга. Таким образом в ход вошли представления о гипервычислениях. Следует отметить, что до настоящего времени работа в этом направлении не увенчалась практическим успехом; злые языки даже характеризуют ее как поиск вечного двигателя. Тем не менее, были предложены устройства, способные к гипервычислениям, которые формально нельзя отвергнуть. Ниже я рассмотрю так называемую бесконечно ускоряющуюся машину Тьюринга.
Общая идея гипервычислений основана на предполагаемой связи физических процессов с несчетными множествами. Поскольку машина Тьюринга ограничена счетными множествами, предполагаемый переход к несчетным множествам в рамках физического процесса на первый взгляд позволяет выйти за границы машины Тьюринга.
Слоган звучит таким образом: физический процесс позволяет выполнить бесконечное количество счетных шагов за конечное время. Любой отрезок содержит в себе количество точек, существенно превышающее мощность множества натуральный чисел. С этой точки зрения бесконечное количество шагов вполне умещается в конечном интервале времени.
Рассмотрим хорошо известный парадокс Зенона с черепахой и Ахиллесом. Для выполнения задачи Ахиллесу необходимо сделать бесконечное количество шагов. Несмотря на это задача выполнима, поскольку ряд сходится. Таким образом, это является примером, когда конечный интервал времени позволяет включить в себя бесконечное количество шагов.
Попробуем применить такую логику для физической реализации гипервычислений. Возьмем физическое устройство, которое моделирует машину Тьюринга, и предположим, что возможно бесконечное ускорение выполнения шага вычислений — время для последующего шага будет равно половине времени для предыдущего. Пусть первый шаг будет выполнен за полсекунды, второй за четверть, третий за одну восьмую и т.д. Поскольку этот ряд сходится, то мы тем самым получаем то, что требуется — выполнение бесконечного количества шагов за одну секунду.
Такое предложение может показаться на первый взгляд бессмысленным, но, как оказывается, в современной физике есть лазейки, которые можно использовать для организации такого процесса. Для начала рассмотрим каким образом такая возможность позволяет нам решить проблему остановки. Идея крайне простая — мы запускаем на такой машине алгоритм, для которого требуется выяснить завершится ли он надлежащим образом или нет. Предполагается, что в такой машине Тьюринга есть лампочка, которая сигнализирует, остановился ли алгоритм или нет. Поэтому если после завершения работы (бесконечное количество счетных шагов исполнено), лампочка горит, значит этот алгоритм останавливается. Если лампочка не горит, знает не останавливается.
Конечно, бесконечное ускорение выполнения шага физической машины кажется противоестественным. В конечном итоге в физике есть самые разные ограничения на увеличение скорости физических процессов. Выход из ситуации оказывается можно найти в рамках общей теории относительности, в которой время является разным в разных системах координат.
Умные люди нашли такое решение уравнений общей теории относительности (время-пространство Маламента-Хогарт, Malament–Hogarth spacetime), в котором есть две мировые линии с подходящими свойствами. Время одной из мировых линий от заданного до бесконечности соответствует конечному времени на другой мировой линии. Таким образом, запуск машины Тьюринга вдоль первой мировой линии и наблюдение за ее поведением со второй мировой линии является решением исходной задачи. Можно за конечное время наблюдать за вычислением бесконечного количества счетных шагов и тем самым решить проблему остановки алгоритма в рамках предполагаемого физического эксперимента.
Конечно, возможность практического осуществления задуманного остается открытым. Все, что можно сказать, сводится к заявлению сторонников гипервычислений, что предложенная процедура не противоречит общей теории относительности. Приведу выводы из статьи Самохвалова:
‘В самом конце предыдущего параграфа мы присоединились к мнению Шаргира и Питовского о том, что проект Хогарта является единственным известным ныне примером физически состоятельного проекта гиперкомпьютера. Однако мы хотели бы подчеркнуть пределы значимости этого достижения. Ведь физическая состоятельность в данном случае означает не больше (правда, и не меньше), чем просто то, что описание определенного мысленного эксперимента совместимо с уравнениями Эйнштейна. Конечно, мысленные эксперименты в физике подчас играли и играют большую роль, но, заметим, эта роль всегда побудительная и разъяснительная, т.е. всегда всего лишь эвристическая.’
‘Второе наше замечание связано с тем, что по поводу гипервычислений бытует мнение, что их анализ ведет якобы к пересмотру некоторых доктрин, проблем и понятий в математике. Например, доктрин интуиционизма или конструктивизма, проблем разрешимости, понятий доказательства и т.п. Не вдаваясь в глубокие дискуссии на эту тему, заметим: вера в то, что мысленные эксперименты в физике, которые сами описываются математически, якобы влияют на математику, не очень далеко отстоит от доверия к рассказу Мюнхгаузена, как он сам себя вытащил из болота.’
В заключение приведу физический тезис Чёрча-Тьюринга, поскольку исследования в области гипервычислений косвенным образом свидетельствуют о его правильности:
‘Числовая функция f физически вычислима (т.е. вычислима с помощью какой-либо физической системы) <=> функция f вычислима с помощью машины Тьюринга.’
Информация
Самохвалов, Климентий Федорович, Физический тезис Чёрча, Философия науки 2 (2010): 34-61.