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

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

История

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

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

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

• Вечная машина Тьюринга это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными ординальными числами. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения предельного ординала, и для которой доступны результаты всех предыдущих бесконечных вычислений.
• Действительный компьютер (подвид идеализированного аналогового компьютера) может быть способен осуществлять гипервычисления при условии, что физика допускает существование настоящих действительных чисел. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, константа Хайтина) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на тепловой шум и квантовомеханические эффекты.
• Квантовомеханические системы, которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций. Это невозможно при использовании стандартного квантового компьютера, поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство).
• Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
• Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
• В начале 1990-х годов Хава Сигельманн предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.

См. также

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

Литература

• 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  (англ.)