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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая InternetArchiveBot (обсуждение | вклад) в 11:18, 29 марта 2018 (Спасено источников — 1, отмечено мёртвыми — 0. #IABot (v1.6.5)). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску
Отпатрулированная версия этой страницы, проверенная 29 марта 2018, была основана на этой версии.

Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах, а также некоторые другие типы вычислений — например, интерактивные вычисления[источник не указан 3302 дня]. Термин гипервычисления (англ. 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" (PDF). Theor. Comput. Sci. 317, 1-3. 317: 105—114. doi:10.1016/j.tcs.2003.12.007. Архивировано (PDF) 21 июля 2011. {{cite journal}}: Неизвестный параметр |deadlink= игнорируется (|url-status= предлагается) (справка)
  4. ↑ Джоэл Девид Хемкинс и Энди Льюис, Infinite time Turing machines Архивировано 5 октября 2011 года., 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 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

Ссылки

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Сверхтьюринговые_вычисления&oldid=91782185