Сверхтьюринговые вычисления

Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах, а также некоторые другие типы вычислений — например, интерактивные вычисления. Термин гипервычисления (англ. hypercomputation) был впервые введён Джеком Коуплендом и Дианой Праудфут. Возможность физической реализации таких вычислений активно обсуждается.

История

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

Предполагаемые способы сверхтьюринговых вычислений

• Машина Тьюринга, которая может выполнить бесконечное количество шагов за конечное время (просто возможность работы машины Тьюринга в течение бесконечного времени (то есть потенциальная бесконечность) недостаточна). Один из предполагаемых способов достичь такого результата — использовать замедление времени для того, чтобы позволить компьютеру совершить бесконечное количество циклов за конечное по часам внешнего наблюдателя время (такое вычисление потребует бесконечной энергии — см. пространство-время Маламета — Хогарта). Ещё одним, чисто математическим, способом является так называемая машина Зенона, основанная на парадоксе Зенона. Машина Зенона выполняет свой первый шаг вычислений за время, например, 1 минуту, следующий за ½ минуты, третий за ¼ минуты и т. д. Суммируя эту бесконечную геометрическую прогрессию, мы получим, что машина выполняет бесконечное количество шагов в течение 2 минут. Однако, некоторые утверждают, что, в соответствии с рассуждениями в парадоксе Зенона, такая машина не только физически, но и логически невозможна.

• Вечная машина Тьюринга это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными ординальными числами. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения предельного ординала, и для которой доступны результаты всех предыдущих бесконечных вычислений.
• Действительный компьютер (подвид идеализированного аналогового компьютера) может быть способен осуществлять гипервычисления при условии, что физика допускает существование настоящих действительных чисел. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, константа Хайтина) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на тепловой шум и квантовомеханические эффекты.
• Квантовомеханические системы, которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций. Это невозможно при использовании стандартного квантового компьютера, поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство).
• Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
• Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
• В начале 1990-х годов Хава Сигельманн предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.
• В предположениях непрерывной Ньютоновой вселенной (когда время и пространство бесконечно делимы), существует возможность построить цепочку вычислительных модулей $M_{n}$, каждый из которых в 2 раза меньше и в 2 раза быстрее предыдущего. При этом нет нужды прибегать к неограниченным массам, силам, скоростям, поскольку меньший размер очевидно предполагает более быструю вычислительную способность при фиксированной физической скорости процесса, $V_{\rm {phys}}=L/t=(L/2^{n})/(t/2^{n})$. Машина $M=\cup M_{n}$ обладает бесконечной памятью даже если каждый модуль обладает только конечной памятью, так как модулей бесконечно много. Кроме того, машина способна совершить бесконечное число операций за конечное время, подобно машине Зенона, так как операции следующего модуля выполняются за в 2 раза меньшее время, чем предыдущего, и мы получаем сходящуюся геометрическую прогрессию временных интервалов. Существенное отличие машины Зенона и машины $M$ в том, что $M$ не может оперировать с выделенной конечной ячейкой памяти бесконечное число раз за конечное время. Это освобождает $M$ от так называемого парадокса Томсона, суть которого в непредсказуемости финального результата выполнения бесконечной последовательности записи поочередно 0,1,0,1,... в фиксированную ячейку памяти.

См. также

• Тезис Чёрча — Тьюринга
• Оракул (вычисления)
• Машина Зенона
• Вычисления
• Парадокс Зенона

Литература

• Martin Davis, Why there is no such discipline as hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 4-7, Special Issue on Hypercomputation
• Mike Stannett, The case for hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8-24, Special Issue on Hypercomputation
• Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
• Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
• Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461—472.
• Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
• L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
• On the computational power of neural nets (недоступная ссылка)
• Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
• Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer. ISBN 978-0-387-30886-9
• Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289—1293
• Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
• Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
• Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461—502
• Martin Davis (2006), «The Church-Turing Thesis: Consensus and opposition». Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125—132
• Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation — Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
• Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

Ссылки

• Hypercomputation Research Network  (англ.)
• Toby Ord, Hypercomputation: computing more than the Turing machine  (англ.)
• Toby Ord, The many forms of hypercomputation  (англ.)
• Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis  (англ.)