Loading AI tools
Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах[англ.], а также некоторые другие типы вычислений — например, интерактивные вычисления[источник не указан 3250 дней]. Термин гипервычисления (англ. hypercomputation) был впервые введён Джеком Коуплендом и Дианой Праудфут.[1] Возможность физической реализации таких вычислений активно обсуждается.
Модели, более мощные, чем машина Тьюринга, были введены Аланом Тьюрингом в его работе 1939 года «Системы логик, основанных на ординалах». Эта работа исследовала математические системы, в которых существовал оракул, который мог вычислить одну произвольную нерекурсивную функцию на множестве натуральных чисел. Он использовал эту модель для того, чтобы показать, что даже в такой, более мощной системе, всё равно присутствуют невычислимые функции (например, проблема остановки машины с оракулом). В своей работе Тьюринг ясно дал понять, что такая модель является не более чем математической абстракцией и не может быть реализована в реальном мире.[2]
- Машина Тьюринга, которая может выполнить бесконечное количество шагов за конечное время (просто возможность работы машины Тьюринга в течение бесконечного времени (то есть потенциальная бесконечность) недостаточна). Один из предполагаемых способов достичь такого результата — использовать замедление времени для того, чтобы позволить компьютеру совершить бесконечное количество циклов за конечное по часам внешнего наблюдателя время (такое вычисление потребует бесконечной энергии — см. пространство-время Маламета — Хогарта). Ещё одним, чисто математическим, способом является так называемая машина Зенона, основанная на парадоксе Зенона. Машина Зенона выполняет свой первый шаг вычислений за время, например, 1 минуту, следующий за ½ минуты, третий за ¼ минуты и т. д. Суммируя эту бесконечную геометрическую прогрессию, мы получим, что машина выполняет бесконечное количество шагов в течение 2 минут. Однако, в соответствии с рассуждениями аналогичными классическому парадоксу Зенона, такая машина невозможна не только физически, но и логически.[3]
- Вечная машина Тьюринга это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными ординальными числами. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения предельного ординала, и для которой доступны результаты всех предыдущих бесконечных вычислений.[4]
- Действительный компьютер (подвид идеализированного аналогового компьютера) может быть способен осуществлять гипервычисления[5] при условии, что физика допускает существование настоящих действительных чисел. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, константа Хайтина) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на тепловой шум и квантовомеханические эффекты.
- Квантовомеханические системы, которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций.[6] Это невозможно при использовании стандартного квантового компьютера, поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство).[7]
- Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
- Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
- В начале 1990-х годов Хава Сигельманн[8] предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.[9]
- В предположениях непрерывной Ньютоновой вселенной (когда время и пространство бесконечно делимы), существует возможность построить цепочку вычислительных модулей , каждый из которых в 2 раза меньше и в 2 раза быстрее предыдущего[10]. При этом нет нужды прибегать к неограниченным массам, силам, скоростям, поскольку меньший размер очевидно предполагает более быструю вычислительную способность при фиксированной физической скорости процесса, . Машина обладает бесконечной памятью даже если каждый модуль обладает только конечной памятью, так как модулей бесконечно много. Кроме того, машина способна совершить бесконечное число операций за конечное время, подобно машине Зенона, так как операции следующего модуля выполняются за в 2 раза меньшее время, чем предыдущего, и мы получаем сходящуюся геометрическую прогрессию временных интервалов. Существенное отличие машины Зенона и машины в том, что не может оперировать с выделенной конечной ячейкой памяти бесконечное число раз за конечное время. Это освобождает от так называемого парадокса Томсона[11], суть которого в непредсказуемости финального результата выполнения бесконечной последовательности записи поочередно 0,1,0,1,... в фиксированную ячейку памяти. Тем не менее, даже если классический парадокс Томсона в такой машине не допускается, его "инвертированная" версия гипотетически может быть реализована[12].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
