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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая InternetArchiveBot (обсуждение | вклад) в 13:55, 4 декабря 2017 (Спасено источников — 1, отмечено мёртвыми — 2. #IABot (v1.6.1)). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску
Отпатрулированная версия этой страницы, проверенная 4 декабря 2017, была основана на этой версии.

Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах, а также некоторые другие типы вычислений — например, интерактивные вычисления[источник не указан 3303 дня]. Термин гипервычисления (англ. 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=89447347