Введение

Модели вычислений

Гипервычисления, или сверхтьюрингские вычисления, — это набор гипотетических моделей вычислений, способных выдавать результаты, невычислимые машиной Тьюринга. Например, машина, способная решить проблему останова, была бы гиперкомпьютером; то же самое относится и к машине, способной правильно оценить каждое утверждение в арифметике Пеано. Тезис Черча — Тьюринга утверждает, что любая "вычислимая" функция, которую может вычислить математик с помощью ручки и бумаги, используя конечное число простых алгоритмов, может быть вычислена машиной Тьюринга. Гиперкомпьютеры вычисляют функции, которые машина Тьюринга вычислить не может и которые, следовательно, не являются вычислимыми в смысле Черча — Тьюринга. Строго говоря, результат работы случайной машины Тьюринга невычислим; однако, большая часть литературы по гипервычислениям сосредоточена на вычислении детерминированных, а не случайных, невычислимых функций.

История

Вычислительная модель, превосходящая машины Тьюринга, была представлена Аланом Тьюрингом в его докторской диссертации 1938 года «Системы логики, основанные на ординалах». В этой работе исследовались математические системы, в которых был доступен оракул, способный вычислять произвольную (не рекурсивную) функцию из натуральных чисел в натуральные числа. Он использовал это средство, чтобы доказать, что даже в этих более мощных системах сохраняется неразрешимость. Машины Тьюринга с оракулом – это математические абстракции и не могут быть физически реализованы.

Государственное пространство

В некотором смысле, большинство функций невычислимы: существуют вычислимые функции, но существует несчётное количество возможных супер-Тьюринг функций.

Модели

Модели гиперкомпьютеров варьируются от полезных, но, вероятно, нереализуемых (например, оригинальные оракульные машины Тьюринга) до менее полезных генераторов случайных функций, которые более правдоподобно могут быть реализованы (например, случайная машина Тьюринга).

Невычислимые входы или компоненты черного ящика

Система, наделенная знанием о невычислимой, оракулярной константе Чейтина (число с бесконечной последовательностью цифр, кодирующей решение проблемы остановки) в качестве входных данных, может решить большое число полезных неразрешимых проблем; система, получившая невычислимый генератор случайных чисел в качестве входных данных, может создавать случайные невычислимые функции, но обычно не считается способной осмысленно решать "полезные" невычислимые функции, такие как проблема остановки. Существует неограниченное количество различных типов вообразимых гиперкомпьютеров, включая:

Оригинальные оракульные машины Тьюринга, определенные Тьюрингом в 1939 году. Реальный компьютер (своего рода идеализированный аналоговый компьютер) может выполнять гипервычисления, если физика допускает общие вещественные переменные (а не только вычислимые вещественные числа), и эти переменные каким-то образом могут быть "использованы" для полезных (а не случайных) вычислений. Это может потребовать весьма необычных законов физики (например, измеримой физической константы с оракулярным значением, такой как константа Чейтина), а также способности измерять вещественное физическое значение с произвольной точностью, хотя стандартная физика делает такие измерения с произвольной точностью теоретически невозможными. Аналогично, нейронная сеть, в которой константа Чейтина каким-то образом точно встроена в ее весовую функцию, сможет решить проблему остановки, но подвержена тем же физическим трудностям, что и другие модели гипервычислений, основанные на реальных вычислениях. Определенные "нечеткие машины Тьюринга", основанные на нечеткой логике, могут, по определению, случайно решить проблему остановки, но только потому, что их способность решать проблему остановки косвенно предполагается в спецификации машины; это обычно рассматривается как "ошибка" в исходной спецификации машин. Аналогично, предложенная модель, известная как справедливый недетерминизм, может случайно позволить оракулярное вычисление невычислимых функций, поскольку некоторые такие системы, по определению, обладают оракулярной способностью идентифицировать входные данные, которые будут "несправедливо" приводить к бесконечному выполнению подсистемы. Дмитрий Тарановский предложил финитистическую модель традиционно нефинитистических областей анализа, построенную вокруг машины Тьюринга, оснащенной быстрорастущей функцией в качестве оракула. С помощью этой и более сложных моделей ему удалось дать интерпретацию арифметики второго порядка. Эти модели требуют невычислимого входного сигнала, например, процесса генерации физических событий, в котором интервал между событиями растет с невычислимо большой скоростью. Аналогично, одна неортодоксальная интерпретация модели неограниченного недетерминизма постулирует, по определению, что время, необходимое "актору" для стабилизации, в принципе непознаваемо, и, следовательно, нельзя доказать в рамках модели, что это не занимает невычислимо долгого периода времени.

Модели "бесконечных вычислительных шагов"

Для того, чтобы работать правильно, некоторые вычисления машин, описанных ниже, буквально требуют бесконечного, а не просто неограниченного, но конечного, физического пространства и ресурсов; в отличие от этого, для машины Тьюринга любое завершающееся вычисление потребует только конечного физического пространства и ресурсов. Машина Тьюринга, способная выполнить бесконечно много шагов за конечное время, – это подвиг, известный как суперзадача. Просто возможность выполнения неограниченного числа шагов недостаточна. Одной из математических моделей является машина Зенона (вдохновлённая парадоксом Зенона). Машина Зенона выполняет свой первый шаг вычисления за (скажем) 1 минуту, второй – за ½ минуты, третий – за ¼ минуты и так далее. Суммируя 1 + ½ + ¼ +… (геометрический ряд), мы видим, что машина выполняет бесконечно много шагов в общей сложности за 2 минуты. Согласно Шагриру, машины Зенона порождают физические парадоксы, и их состояние логически неопределено вне полуоткрытого интервала [0, 2), то есть неопределено ровно через 2 минуты после начала вычисления. Естественно предположить, что возможность путешествия во времени (существование замкнутых времениподобных кривых (CTC)) сама по себе делает возможными гипервычисления. Однако это не так, поскольку CTC не предоставляет (сама по себе) неограниченный объём памяти, необходимый для бесконечного вычисления. Тем не менее, существуют пространства-времена, в которых область CTC может быть использована для релятивистских гипервычислений. Согласно статье 1992 года, компьютер, работающий в пространстве-времени Маламента — Хогарта или на орбите вокруг вращающейся чёрной дыры, теоретически может выполнять вычисления, не поддающиеся решению на машине Тьюринга, для наблюдателя внутри чёрной дыры. Доступ к CTC может позволить быстро решать PSPACE-полные задачи, класс сложности, который, хотя и разрешимый машиной Тьюринга, обычно считается вычислительно неразрешимым.

Квантовые модели

Некоторые ученые предполагают, что квантово-механическая система, использующая бесконечную суперпозицию состояний, может вычислить невычислимую функцию. Это невозможно с помощью стандартного квантового компьютера на кубитах, поскольку доказано, что обычный квантовый компьютер является PSPACE-сводимым (квантовый компьютер, работающий за полиномиальное время, может быть смоделирован классическим компьютером, использующим полиномиальное пространство).

"В конечном итоге корректируемые" системы

Некоторые физически реализуемые системы всегда в конечном итоге сходятся к правильному ответу, но имеют недостаток: они часто выдают неверный ответ и придерживаются его в течение невычислимо большого периода времени, прежде чем вернуться и исправить ошибку. В середине 1960-х годов Э. Марк Голд и Хилари Путнам независимо друг от друга предложили модели индуктивного вывода («ограничивающие рекурсивные функционалы» и «предикаты проб и ошибок» соответственно). Эти модели позволяют «обучать в пределе» некоторые нерекурсивные множества чисел или языков (включая все рекурсивно перечисляемые множества языков), в то время как по определению только рекурсивные множества чисел или языков могут быть идентифицированы машиной Тьюринга. В то время как машина стабилизируется к правильному ответу для любого обучаемого множества за конечное время, она может определить его как правильный только в том случае, если он рекурсивен; в противном случае правильность устанавливается только путем бесконечного выполнения машины и наблюдения за тем, что она никогда не пересматривает свой ответ. Путнам определил эту новую интерпретацию как класс «эмпирических» предикатов, заявив: «если мы всегда «предполагаем», что последний сгенерированный ответ верен, мы совершим конечное число ошибок, но в конечном итоге получим правильный ответ. (Однако следует отметить, что даже если мы достигли правильного ответа (конца конечной последовательности), мы никогда не уверены, что он верен)». Исследовались эффекты итерации ограничивающей процедуры; это позволяет вычислить любой арифметический предикат. Шуберт писал: «Интуитивно, итерированная ограничивающая идентификация может рассматриваться как индуктивный вывод высшего порядка, выполняемый коллективно постоянно растущим сообществом индуктивных машин низшего порядка». Символьная последовательность вычислима в пределе, если существует конечная, возможно, не останавливающаяся программа на универсальной машине Тьюринга, которая инкрементно выводит каждый символ последовательности. Это включает в себя диадическое разложение π и любого другого вычислимого действительного числа, но все же исключает все невычислимые действительные числа. «Монотонные машины Тьюринга», традиционно используемые в теории размера описания, не могут редактировать свои предыдущие выходы; обобщенные машины Тьюринга, как определено Юргеном Шмидхубером, могут. Он определяет конструктивно описываемые символьные последовательности как те, которые имеют конечную, не останавливающуюся программу, работающую на обобщенной машине Тьюринга, так что любой выходной символ в конечном итоге сходится; то есть он больше не изменяется после некоторого конечного начального интервала времени. Из-за ограничений, впервые продемонстрированных Куртом Гёделем (1931), может быть невозможно предсказать само время сходимости с помощью останавливающейся программы, иначе проблема останова могла бы быть решена. Шмидхубер использует этот подход для определения множества формально описываемых или конструктивно вычислимых вселенных, или конструктивных теорий всего. Обобщенные машины Тьюринга могут в конечном итоге сойтись к правильному решению проблемы останова путем вычисления последовательности Спекера.