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

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

История

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

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

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

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

Смотри также

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

Примечания

1. ↑ Alan Turing’s forgotten ideas in computer science. Scientific American, April 1999.
2. ↑ «Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной.»(Undecidable p. 167, a reprint of Turing’s paper Systems of Logic Based On Ordinals)
3. ↑ См. например Shagrir, O. (June 2004). «Super-tasks, accelerating Turing machines and uncomputability». Theor. Comput. Sci. 317, 1-3 317: 105–114. DOI:10.1016/j.tcs.2003.12.007.
4. ↑ Джоэл Девид Хемкинс и Энди Льюис, Infinite time Turing machines, Journal of Symbolic Logic, 65(2):567-604, 2000.
5. ↑ Арнольд Шёнхаге, «On the power of random access machines», in Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520—529, 1979. Source of citation: Scott Aaronson, «NP-complete Problems and Physical Reality» p. 12
6. ↑ Существуют утверждения в пользу этого; смотри например Tien Kieu (2003). «Quantum Algorithm for the Hilbert's Tenth Problem». Int. J. Theor. Phys. 42: 1461–1478. DOI:10.1023/A:1025780028846. и процитированную там литературу. Ошибки подхода Kieu были указаны Warren D. Smith в Three counterexamples refuting Kieu’s plan for «quantum adiabatic hypercomputation»; and some uncomputable quantum mechanical tasks
7. ↑ Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.
8. ↑ : BINDS lab : HAVA'S BIO :
9. ↑ Verifying Properties of Neural Networks p.6

Литература

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