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

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 12:10, 20 апреля 2024

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

История

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

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

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

Вечная машина Тьюринга это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными ординальными числами. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения предельного ординала, и для которой доступны результаты всех предыдущих бесконечных вычислений.^[4]
Действительный компьютер (подвид идеализированного аналогового компьютера) может быть способен осуществлять гипервычисления^[5] при условии, что физика допускает существование настоящих действительных чисел. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, константа Хайтина) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на тепловой шум и квантовомеханические эффекты.
Квантовомеханические системы, которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций.^[6] Это невозможно при использовании стандартного квантового компьютера, поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство).^[7]
Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
В начале 1990-х годов Хава Сигельманн^[8] предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.^[9]
В предположениях непрерывной Ньютоновой вселенной (когда время и пространство бесконечно делимы), существует возможность построить цепочку вычислительных модулей $M_{n}$ , каждый из которых в 2 раза меньше и в 2 раза быстрее предыдущего^[10]. При этом нет нужды прибегать к неограниченным массам, силам, скоростям, поскольку меньший размер очевидно предполагает более быструю вычислительную способность при фиксированной физической скорости процесса, $V_{\rm {phys}}=L/t=(L/2^{n})/(t/2^{n})$ . Машина $M=\cup M_{n}$ обладает бесконечной памятью даже если каждый модуль обладает только конечной памятью, так как модулей бесконечно много. Кроме того, машина способна совершить бесконечное число операций за конечное время, подобно машине Зенона, так как операции следующего модуля выполняются за в 2 раза меньшее время, чем предыдущего, и мы получаем сходящуюся геометрическую прогрессию временных интервалов. Существенное отличие машины Зенона и машины $M$ в том, что $M$ не может оперировать с выделенной конечной ячейкой памяти бесконечное число раз за конечное время. Это освобождает $M$ от так называемого парадокса Томсона^[11], суть которого в непредсказуемости финального результата выполнения бесконечной последовательности записи поочередно 0,1,0,1,... в фиксированную ячейку памяти. Тем не менее, даже если классический парадокс Томсона в такой машине не допускается, его "инвертированная" версия гипотетически может быть реализована^[12].

См. также

Примечания

↑ Alan Turing’s forgotten ideas in computer science Архивная копия от 11 ноября 2013 на Wayback Machine. Scientific American, April 1999.
↑ «Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной.»(Undecidable p. 167, a reprint of Turing’s paper Systems of Logic Based On Ordinals)
↑ См. например Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability (англ.) // Theor. Comput. Sci. 317, 1-3 : journal. — 2004. — June (vol. 317). — P. 105—114. — doi:10.1016/j.tcs.2003.12.007. Архивировано 21 июля 2011 года.
↑ Джоэл Девид Хемкинс и Энди Льюис, Infinite time Turing machines Архивировано 5 октября 2011 года., Journal of Symbolic Logic, 65(2):567—604, 2000.
↑ Арнольд Шёнхаге, «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» Архивная копия от 15 января 2010 на Wayback Machine p. 12
↑ Существуют утверждения в пользу этого; смотри например Tien Kieu. Quantum Algorithm for the Hilbert's Tenth Problem (англ.) // Int. J. Theor. Phys.^[англ.] : journal. — 2003. — Vol. 42. — P. 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 Архивная копия от 6 марта 2010 на Wayback Machine
↑ Bernstein and Vazirani, Quantum complexity theory Архивная копия от 11 марта 2016 на Wayback Machine, SIAM Journal on Computing, 26(5):1411—1473, 1997.
↑ : BINDS lab : HAVA’S BIO : (неопр.) Дата обращения: 7 июня 2011. Архивировано 4 октября 2011 года.
↑ Verifying Properties of Neural Networks Архивная копия от 4 марта 2016 на Wayback Machine p.6
↑ E. B. Davies, Building infinite machines, The British Journal for the Philosophy of Science, 52:671-682, 2001.
↑ J. Thomson, Tasks and Super-Tasks, Analysis, 15:1-13, 1954.
↑ A. Kutsenko, Programming infinite machines, Erkenntnis, 87:181-189, 2022.

Литература

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 Архивная копия от 4 марта 2016 на Wayback Machine, 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 (англ.)

[first-1] Alan Turing’s forgotten ideas in computer science Архивная копия от 11 ноября 2013 на Wayback Machine. Scientific American, April 1999.

[2] «Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной.»(Undecidable p. 167, a reprint of Turing’s paper Systems of Logic Based On Ordinals)

[3] См. например Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability (англ.) // Theor. Comput. Sci. 317, 1-3 : journal. — 2004. — June (vol. 317). — P. 105—114. — doi:10.1016/j.tcs.2003.12.007. Архивировано 21 июля 2011 года.

[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» Архивная копия от 15 января 2010 на Wayback Machine p. 12

[6] Существуют утверждения в пользу этого; смотри например Tien Kieu. Quantum Algorithm for the Hilbert's Tenth Problem (англ.) // Int. J. Theor. Phys.^[англ.] : journal. — 2003. — Vol. 42. — P. 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 Архивная копия от 6 марта 2010 на Wayback Machine

[7] Bernstein and Vazirani, Quantum complexity theory Архивная копия от 11 марта 2016 на Wayback Machine, SIAM Journal on Computing, 26(5):1411—1473, 1997.

[8] : BINDS lab : HAVA’S BIO : (неопр.) Дата обращения: 7 июня 2011. Архивировано 4 октября 2011 года.

[9] Verifying Properties of Neural Networks Архивная копия от 4 марта 2016 на Wayback Machine p.6

[10] E. B. Davies, Building infinite machines, The British Journal for the Philosophy of Science, 52:671-682, 2001.

[11] J. Thomson, Tasks and Super-Tasks, Analysis, 15:1-13, 1954.

[12] A. Kutsenko, Programming infinite machines, Erkenntnis, 87:181-189, 2022.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Строка 1: / Строка 1: @@
-'''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' ({{lang-en|hypercomputation}})) называются такие вычисления, которые не могут быть проделаны на [[Машина Тьюринга|машине Тьюринга]]. Они включают в себя разнообразные гипотетические методы, основанные на [[Суперрекурсивные алгоритмы|суперрекурсивных алгоритмах]], а также некоторые другие типы вычислений — например, [[интерактивные вычисления]]. Термин ''гипервычисления'' ({{lang-en|hypercomputation}}) был впервые введён [[Коупленд, Джек|Джеком Коуплендом]] и [[Праудфут, Диана|Дианой Праудфут]].<ref name="first">''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science]''. [[Scientific American]], April 1999.</ref> Возможность физической реализации таких вычислений  активно обсуждается.
+'''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' ({{lang-en|hypercomputation}})) называются такие вычисления, которые не могут быть проделаны на [[Машина Тьюринга|машине Тьюринга]]. Они включают в себя разнообразные гипотетические методы, основанные на {{iw|Суперрекурсивные алгоритмы|суперрекурсивных алгоритмах|en|Super-recursive algorithm}}, а также некоторые другие типы вычислений — например, [[интерактивные вычисления]]{{Нет АИ|12|12|2015}}. Термин ''гипервычисления'' ({{lang-en|hypercomputation}}) был впервые введён [[Коупленд, Джек|Джеком Коуплендом]] и [[Праудфут, Диана|Дианой Праудфут]].<ref name="first">''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing’s forgotten ideas in computer science] {{Wayback|url=http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 |date=20131111194007 }}''. [[Scientific American]], April 1999.</ref> Возможность физической реализации таких вычислений активно обсуждается.
-==История==
+== История ==
-Модели, более мощные, чем машина Тьюринга, были введены [[Алан Тьюринг|Аланом Тьюрингом]] в его работе 1939 года ''«Системы логик, основанных на ординалах»''. Эта работа исследовала математические системы, в которых существовал [[Оракул (вычисления)|оракул]], который мог вычислить одну произвольную нерекурсивную функцию на множестве [[Натуральное число|натуральных чисел]]. Он использовал эту модель для того, чтобы показать, что даже в такой, более мощной системе, всё равно присутствуют невычислимые функции. В своей работе Тьюринг ясно дал понять, что такая модель является не более чем математической абстракцией и не может быть реализована в реальном мире.<ref> "Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной."(Undecidable p. 167, a reprint of Turing's paper ''Systems of Logic Based On Ordinals'')</ref>
+Модели, более мощные, чем машина Тьюринга, были введены [[Алан Тьюринг|Аланом Тьюрингом]] в его работе 1939 года ''«Системы логик, основанных на ординалах»''. Эта работа исследовала математические системы, в которых существовал [[Оракул (вычисления)|оракул]], который мог вычислить одну произвольную нерекурсивную функцию на множестве [[Натуральное число|натуральных чисел]]. Он использовал эту модель для того, чтобы показать, что даже в такой, более мощной системе, всё равно присутствуют невычислимые функции (например, [[проблема остановки]] машины с оракулом). В своей работе Тьюринг ясно дал понять, что такая модель является не более чем [[Математическая абстракция|математической абстракцией]] и не может быть реализована в реальном мире.<ref> «Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной.»(Undecidable p. 167, a reprint of Turing’s paper ''Systems of Logic Based On Ordinals'')</ref>
-==Предполагаемые способы сверхтьюринговых вычислений==
+== Предполагаемые способы сверхтьюринговых вычислений ==
-*Машина Тьюринга, которая может ''выполнить'' бесконечное количество шагов за конечное время (просто возможность работы машины Тьюринга в течение бесконечного времени (то есть потенциальная бесконечность) недостаточна). Один из предполагаемых способов достичь такого результата — использовать [[замедление времени]] для того, чтобы позволить компьютеру совершить бесконечное количество циклов за конечное по часам внешнего наблюдателя время (такое вычисление потребует бесконечной энергии — см. [[пространство-время Маламета — Хогарта]]). Ещё одним, чисто математическим, способом является так называемая [[машина Зенона]], основанная на [[Парадокс Зенона|парадоксе Зенона]]. Машина Зенона выполняет свой первый шаг вычислений за время, например, 1 минуту, следующий за ½ минуты, третий за ¼ минуты и т.д. Суммируя эту бесконечную [[Геометрическая прогрессия|геометрическую прогрессию]], мы получим, что машина выполняет бесконечное количество шагов в течение 2 минут. Однако, некоторые утверждают, что, в соответствии с рассуждениями в парадоксе Зенона, такая машина не только физически, но и логически невозможна.<ref>См. например {{cite journal
+* Машина Тьюринга, которая может ''выполнить'' бесконечное количество шагов за конечное время (просто возможность работы машины Тьюринга в течение бесконечного времени (то есть [[потенциальная бесконечность]]) недостаточна). Один из предполагаемых способов достичь такого результата — использовать [[замедление времени]] для того, чтобы позволить компьютеру совершить бесконечное количество циклов за конечное по часам внешнего наблюдателя время (такое вычисление потребует бесконечной энергии — см. [[пространство-время Маламета — Хогарта]]). Ещё одним, чисто математическим, способом является так называемая [[машина Зенона]], основанная на [[Парадокс Зенона|парадоксе Зенона]]. Машина Зенона выполняет свой первый шаг вычислений за время, например, 1 минуту, следующий за ½ минуты, третий за ¼ минуты и т. д. Суммируя эту бесконечную [[Геометрическая прогрессия|геометрическую прогрессию]], мы получим, что машина выполняет бесконечное количество шагов в течение 2 минут. Однако, в соответствии с рассуждениями аналогичными классическому парадоксу Зенона, такая машина невозможна не только физически, но и логически.<ref>См. например {{статья
+|заглавие=Super-tasks, accelerating Turing machines and uncomputability
-|author=Shagrir, O.
+|издание=Theor. Comput. Sci. 317, 1-3
-|title=Super-tasks, accelerating Turing machines and uncomputability
+|страницы=105—114
-|journal=Theor. Comput. Sci. 317, 1-3
+|doi=10.1016/j.tcs.2003.12.007
-|date=June 2004
+|ссылка=http://edelstein.huji.ac.il/staff/shagrir/papers/Supertasks_Accelerating_Turing_Machines_and_Uncomputability.pdf
-|pages=105–114
+|том=317
-|doi=10.1016/j.tcs.2003.12.007
-|url=http://edelstein.huji.ac.il/staff/shagrir/papers/Supertasks_Accelerating_Turing_Machines_and_Uncomputability.pdf
+|archiveurl=https://web.archive.org/web/20110721133626/http://edelstein.huji.ac.il/staff/shagrir/papers/Supertasks_Accelerating_Turing_Machines_and_Uncomputability.pdf
+|archivedate=2011-07-21
-|volume=317}}</ref>
+|deadlink=404
+|accessdate=2009-10-12
+|язык=en
+|тип=journal
+|автор=Shagrir, O.
+|месяц=6
+|год=2004}}</ref>
-*'''Вечная машина Тьюринга''' это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными [[Порядковое число|ординальными числами]]. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения [[Предельный ординал|предельного ординала]], и для которой доступны результаты всех предыдущих бесконечных вычислений.<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] {{webarchive|url=https://web.archive.org/web/20111005150801/http://jdh.hamkins.org/Publications/2000e |date=2011-10-05 }}, ''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»] {{Wayback|url=http://www.scottaaronson.com/papers/npcomplete.pdf |date=20100115083806 }} 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>Существуют утверждения в пользу этого; смотри например {{статья |заглавие=Quantum Algorithm for the Hilbert's Tenth Problem |издание={{Нп3|International Journal of Theoretical Physics|Int. J. Theor. Phys.||International Journal of Theoretical Physics}} |том=42 |ссылка=http://www.arxiv.org/pdf/quant-ph/0110136 |страницы=1461—1478 |doi=10.1023/A:1025780028846 |язык=en |автор=Tien Kieu |год=2003 |тип=journal }} и процитированную там литературу. Ошибки подхода 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] {{Wayback|url=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 |date=20100306171055 }}</ref> Это невозможно при использовании стандартного [[квантовый компьютер|квантового компьютера]], поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем [[Класс PSPACE|полиномиальное пространство]]).<ref>Bernstein and Vazirani, [http://www.cs.berkeley.edu/~vazirani/bv.ps Quantum complexity theory] {{Wayback|url=http://www.cs.berkeley.edu/~vazirani/bv.ps |date=20160311163436 }}, 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>
 * Техника, известная как [[неограниченный детерминизм]], может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
 * Использование [[Замкнутая времениподобная кривая|замкнутых времениподобных кривых]], вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
-* В начале 1990-х [[Хава Сигельманн]] предложил модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.<ref>[http://www.cs.math.ist.utl.pt/ftp/pub/CostaJF/01-RCS-iwann.pdf Verifying Properties of Neural Networks] p.6 </ref>
+* В начале 1990-х годов [[Хава Сигельманн]]<ref>{{Cite web |url=http://binds.cs.umass.edu/havaBio.html |title=: BINDS lab : HAVA’S BIO :<!-- Заголовок добавлен ботом --> |access-date=2011-06-07 |archive-date=2011-10-04 |archive-url=https://web.archive.org/web/20111004020154/http://binds.cs.umass.edu/havaBio.html |deadlink=no }}</ref> предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.<ref>[http://www.cs.math.ist.utl.pt/ftp/pub/CostaJF/01-RCS-iwann.pdf Verifying Properties of Neural Networks] {{Wayback|url=http://www.cs.math.ist.utl.pt/ftp/pub/CostaJF/01-RCS-iwann.pdf |date=20160304093136 }} p.6</ref>
+*В предположениях непрерывной Ньютоновой вселенной (когда время и пространство бесконечно делимы), существует возможность построить цепочку вычислительных модулей <math>M_n</math>, каждый из которых в 2 раза меньше и в 2 раза быстрее предыдущего<ref>E. B. Davies, [https://www.jstor.org/stable/3541913 Building infinite machines], ''The British Journal for the Philosophy of Science'', 52:671-682, 2001.</ref>. При этом нет нужды прибегать к неограниченным массам, силам, скоростям, поскольку меньший размер очевидно предполагает более быструю вычислительную способность при фиксированной физической скорости процесса, <math>V_{\rm phys}=L/t=(L/2^n)/(t/2^n)</math>. Машина <math>M=\cup M_n</math> обладает бесконечной памятью даже если каждый модуль обладает только конечной памятью, так как модулей бесконечно много. Кроме того, машина способна совершить бесконечное число операций за конечное время, подобно машине Зенона, так как операции следующего модуля выполняются за в 2 раза меньшее время, чем предыдущего, и мы получаем сходящуюся геометрическую прогрессию временных интервалов. Существенное отличие машины Зенона и машины <math>M</math> в том, что <math>M</math> не может оперировать с выделенной конечной ячейкой памяти бесконечное число раз за конечное время. Это освобождает <math>M</math> от так называемого парадокса Томсона<ref>J. Thomson, [https://academic.oup.com/analysis/article/15/1/1/170170 Tasks and Super-Tasks], ''Analysis'', 15:1-13, 1954.</ref>, суть которого в непредсказуемости финального результата выполнения бесконечной последовательности записи поочередно 0,1,0,1,... в фиксированную ячейку памяти. Тем не менее, даже если классический парадокс Томсона в такой машине не допускается, его "инвертированная" версия гипотетически может быть реализована<ref>A. Kutsenko, [https://doi.org/10.1007/s10670-019-00190-7 Programming infinite machines], ''Erkenntnis, 87:181-189, 2022.''</ref>.
+== См. также ==
-==Примечания==
-{{Примечания}}
-==Смотри также==
 * [[Тезис Чёрча — Тьюринга]]
 * [[Оракул (вычисления)]]
@@ Строка 33: / Строка 37: @@
 * [[Парадокс Зенона]]
+== Примечания ==
-==Дополнительное чтение==
+{{Примечания}}
-*Martin Davis, ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/davis%5B1%5D.pdf 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, ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/stannett%5b1%5d.pdf 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
+* Martin Davis, ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/davis%5B1%5D.pdf 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
-*Hava Siegelmann. ''Neural Networks and Analog Computation: Beyond the Turing Limit'' Boston: Birkhäuser.
+* Mike Stannett, ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/stannett%5b1%5d.pdf The case for hypercomputation] {{Wayback|url=http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/stannett%5b1%5d.pdf |date=20160304053941 }}'', Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8-24, Special Issue on Hypercomputation
-*Hava Siegelmann. [http://binds.cs.umass.edu/papers/1996_Siegelmann_TheorCompSci.pdf ''The simple dynamics of super Turing theories'']; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472.
+* Alan Turing, ''Systems of logic based on ordinals'', Proc. London math. soc., '''45''', 1939
-*Keith Douglas. ''[http://www.philosopher-animal.com/papers/take6c.PDF Super-Turing Computation: a Case Study Analysis]'' ([[Portable Document Format|PDF]]), M.S. Thesis, Carnegie Mellon University, 2003.
+* Hava Siegelmann. ''Neural Networks and Analog Computation: Beyond the Turing Limit'' Boston: Birkhäuser.
-*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.
+* Hava Siegelmann. [http://binds.cs.umass.edu/papers/1996_Siegelmann_TheorCompSci.pdf ''The simple dynamics of super Turing theories'']; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461—472.
-<!-- #http://www.nature.com/nsu/010329/010329-8.html A ''[[Nature (journal)|Nature]]'' article on the above. This link doesn't seem to go to the article anymore. -->
+* Keith Douglas. ''[http://www.philosopher-animal.com/papers/take6c.PDF Super-Turing Computation: a Case Study Analysis]'' ([[Portable Document Format|PDF]]), M.S. Thesis, Carnegie Mellon University, 2003.
-*[ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]
+* 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.
-*Toby Ord. [http://arxiv.org/abs/math/0209332 ''Hypercomputation: Computing more than the Turing machine can compute'']: A survey article on various forms of hypercomputation.
+<!-- #http://www.nature.com/nsu/010329/010329-8.html A ''[[Nature (journal)|Nature]]'' article on the above. This link doesn’t seem to go to the article anymore. -->
-*Apostolos Syropoulos (2008), ''Hypercomputation: Computing Beyond the Church-Turing Barrier'', Springer. ISBN 9780387308869
+* [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]{{Недоступная ссылка|date=Декабрь 2017 |bot=InternetArchiveBot }}
-* Burgin, M. S. (1983) Inductive Turing Machines, ''Notices of the Academy of Sciences of the USSR'', v. 270, No. 6, pp. 1289-1293
+* Toby Ord. [http://arxiv.org/abs/math/0209332 ''Hypercomputation: Computing more than the Turing machine can compute'']: A survey article on various forms of hypercomputation.
-* Mark Burgin (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. ISBN 0387955690
+* 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) ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_MINDS_AND_MACHINES/VOLUME_12_NO_4/NV6361035557Q678.pdf Hypercomputation]'', Minds and machines, v. 12, pp. 461-502
+* Copeland, J. (2002) ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_MINDS_AND_MACHINES/VOLUME_12_NO_4/NV6361035557Q678.pdf Hypercomputation]'', Minds and machines, v. 12, pp. 461—502
-* Martin Davis (2006), "[http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006.  Lecture notes in computer science, 3988 pp. 125–132
+* Martin Davis (2006), «[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf 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/
+* 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
+== Ссылки ==
-==Внешние ссылки==
-*[http://www.hypercomputation.net/ Hypercomputation Research Network] {{ref-en}}
+* [http://www.hypercomputation.net/ Hypercomputation Research Network] {{ref-en}}
-*[http://arxiv.org/abs/math/0209332 Toby Ord, ''Hypercomputation: computing more than the Turing machine''] {{ref-en}}
+* [http://arxiv.org/abs/math/0209332 Toby Ord, ''Hypercomputation: computing more than the Turing machine''] {{ref-en}}
-*[http://www.amirrorclear.net/academic/papers/many-forms.pdf Toby Ord, ''The many forms of hypercomputation''] {{ref-en}}
+* [http://www.amirrorclear.net/academic/papers/many-forms.pdf Toby Ord, ''The many forms of hypercomputation''] {{ref-en}}
-*[http://citeseer.ist.psu.edu/cotogno03hypercomputation.html Paolo Cotogno, ''Hypercomputation and the Physical Church-Turing thesis''] {{ref-en}}
+* [http://citeseer.ist.psu.edu/cotogno03hypercomputation.html Paolo Cotogno, ''Hypercomputation and the Physical Church-Turing thesis''] {{ref-en}}
-[[en:Hypercomputation]]
-[[fr:Hypercalcul]]
-[[ja:ハイパーコンピュータ]]
-[[pl:Hiperkomputer]]
 [[Категория:Нерешённые проблемы современной физики]]
+[[Категория:Теория алгоритмов]]
-{{изолированная статья}}
+[[Категория:Нерешённые проблемы информатики]]

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

Текущая версия от 12:10, 20 апреля 2024

Содержание

История

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

См. также

Примечания

Литература

Ссылки

Навигация

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

Текущая версия от 12:10, 20 апреля 2024

История

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

См. также

Примечания

Литература

Ссылки

Навигация

Поиск