Сверхтьюринговые вычисления: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м оформление
Строка 17: Строка 17:


* '''Вечная машина Тьюринга''' это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными [[Порядковое число|ординальными числами]]. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения [[Предельный ординал|предельного ординала]], и для которой доступны результаты всех предыдущих бесконечных вычислений.<ref>Джоэл Девид Хемкинс и Энди Льюис, [http://jdh.hamkins.org/Publications/2000e Infinite time Turing machines], ''Journal of Symbolic Logic'', 65(2):567-604, 2000.</ref>
* '''Вечная машина Тьюринга''' это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными [[Порядковое число|ординальными числами]]. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения [[Предельный ординал|предельного ординала]], и для которой доступны результаты всех предыдущих бесконечных вычислений.<ref>Джоэл Девид Хемкинс и Энди Льюис, [http://jdh.hamkins.org/Publications/2000e Infinite time Turing machines], ''Journal of Symbolic Logic'', 65(2):567-604, 2000.</ref>
* [[Действительный компьютер]] (подвид идеализированного [[аналоговый компьютер|аналогового компьютера]]) может быть способен осуществлять гипервычисления<ref>Арнольд Шёнхаге, «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, [http://www.scottaaronson.com/papers/npcomplete.pdf «NP-complete Problems and Physical Reality»] p. 12</ref> при условии, что физика допускает существование настоящих [[Вещественное число|действительных чисел]]. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, [[константа Чайтина]]) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на [[тепловой шум]] и [[Квантовая механика|квантовомеханические эффекты]].
* [[Действительный компьютер]] (подвид идеализированного [[аналоговый компьютер|аналогового компьютера]]) может быть способен осуществлять гипервычисления<ref>Арнольд Шёнхаге, «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, [http://www.scottaaronson.com/papers/npcomplete.pdf «NP-complete Problems and Physical Reality»] p. 12</ref> при условии, что физика допускает существование настоящих [[Вещественное число|действительных чисел]]. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, [[константа Хайтина]]) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на [[тепловой шум]] и [[Квантовая механика|квантовомеханические эффекты]].
* [[Квантовая механика|Квантовомеханические системы]], которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций.<ref>Существуют утверждения в пользу этого; смотри например {{cite journal | author = Tien Kieu | title = Quantum Algorithm for the Hilbert's Tenth Problem | journal = Int. J. Theor. Phys. | year = 2003 | volume = 42 | url = http://www.arxiv.org/pdf/quant-ph/0110136 | pages = 1461–1478 | doi = 10.1023/A:1025780028846}} и процитированную там литературу. Ошибки подхода Kieu были указаны Warren D. Smith в [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TY8-4JD0GX5-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=a63612cc7522010ee340e8ddada13779 Three counterexamples refuting Kieu’s plan for «quantum adiabatic hypercomputation»; and some uncomputable quantum mechanical tasks]
* [[Квантовая механика|Квантовомеханические системы]], которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций.<ref>Существуют утверждения в пользу этого; смотри например {{cite journal | author = Tien Kieu | title = Quantum Algorithm for the Hilbert's Tenth Problem | journal = Int. J. Theor. Phys. | year = 2003 | volume = 42 | url = http://www.arxiv.org/pdf/quant-ph/0110136 | pages = 1461–1478 | doi = 10.1023/A:1025780028846}} и процитированную там литературу. Ошибки подхода Kieu были указаны Warren D. Smith в [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TY8-4JD0GX5-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=a63612cc7522010ee340e8ddada13779 Three counterexamples refuting Kieu’s plan for «quantum adiabatic hypercomputation»; and some uncomputable quantum mechanical tasks]
</ref> Это невозможно при использовании стандартного [[квантовый компьютер|квантового компьютера]], поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем [[Класс PSPACE|полиномиальное пространство]]).<ref>Bernstein and Vazirani, [http://www.cs.berkeley.edu/~vazirani/bv.ps Quantum complexity theory], SIAM Journal on Computing, 26(5):1411-1473, 1997.</ref>
</ref> Это невозможно при использовании стандартного [[квантовый компьютер|квантового компьютера]], поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем [[Класс PSPACE|полиномиальное пространство]]).<ref>Bernstein and Vazirani, [http://www.cs.berkeley.edu/~vazirani/bv.ps Quantum complexity theory], SIAM Journal on Computing, 26(5):1411-1473, 1997.</ref>

Версия от 00:01, 12 января 2010

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

История

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

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

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

Смотри также

Примечания

  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.
  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. ↑ Verifying Properties of Neural Networks p.6

Литература

Ссылки

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