Гіперобчисленнями або надтюрінговими обчисленнями англ hypercomputation називають такі обчислення які не можуть бути вик

Гіперобчисленнями або надтюрінговими обчисленнями, (англ. hypercomputation) називають такі обчислення, які не можуть бути виконані на машині Тюрінга. Вони включають в себе різноманітні гіпотетичні методи, засновані на ^[en], а також деякі інші типи обчислень — наприклад, інтерактивні обчислення. Термін гіперобчислення був вперше введений ^[en] та Діаною Праудфут.

Терміни не можна назвати синонімами: «надтюрінгове обчислення» на відміну від «гіперобчислення», як правило, означає, що запропонована модель повинна бути фізично реалізованою.

Можливість фізичної реалізації таких обчислень активно обговорюється.

Історія

Моделі більш потужні, ніж машина Тюрінга, були введені Аланом Тюрінгом в його роботі 1939 року ^[en]. Ця робота досліджувала математичні системи, в яких існував оракул, який міг вирахувати одну довільну нерекурсивну функцію на множині натуральних чисел. Він використав цю модель для того, щоб показати, що навіть у такій, більш потужній системі, все одно присутні необчислювані функції. У своїй роботі Тюрінг ясно дав зрозуміти, що така модель є не більш ніж математичною абстракцією і не може бути реалізована в реальному світі.

Передбачувані способи гіперобчилення

Машина Тюрінга, яка може виконати нескінченну кількість кроків за скінченний час (просто можливість роботи машини Тюрінга протягом нескінченного часу (тобто (потенційна нескінченність)) недостатня). Один з передбачуваних способів досягти такого результату — використовувати уповільнення часу для того, щоб дозволити комп'ютеру зробити нескінченну кількість циклів за скінченний по годинах для зовнішнього спостерігача час (таке обчислення потребують нескінченної енергії — див. простір-час Маламета — Хогарта). Ще одним, чисто математичним, способом є так звана машина Зенона, заснована на парадоксі Зенона. Машина Зенона виконує свій перший крок обчислень за час, наприклад, 1 хвилину, другий за ½ хвилини, третій за ¼ хвилини і т. д. Підсумовуючи цю нескінченну геометричну прогресію, ми отримаємо, що машина виконує нескінченну кількість кроків протягом 2 хвилин. Однак, деякі стверджують, що, відповідно до міркуваннь в парадоксі Зенона, така машина не лише фізично, а й логічно неможлива.
Оригінальні оракул-машини Тюрінга, що були ним винайдені у 1939.
Дійсний комп'ютер (підвид ідеалізованого аналогового комп'ютера) здатний здійснювати гіперобчислення за умови, що фізика припускає існування справжніх дійсних чисел. Це, ймовірно, вимагає існування якихось дуже дивних законів фізики (наприклад наявності вимірної фізичної константи, яка може бути використана як оракул — див., наприклад, ^[en]) та повинно, як мінімум, вимагати можливості вимірювання фізичних констант з довільною точністю, незважаючи на тепловий шум і квантовомеханічні ефекти.
Вічна машина Тюрінга — це узагальнення машини Зенона, яка може виконати невизначено тривале обчислення, кроки в якому перенумеровані потенційно трансфінітно ординальними числами. Вона моделює звичайну у всіх інших сенсах машину Тюрінга, для якої незупинні обчислення завершуються шляхом досягнення спеціального стану, зарезервованого для досягнення ^[en], і для якої доступні результати всіх попередніх нескінченних обчислень.
Квантовомеханічні системи, які якимось чином використовують, наприклад, нескінченну суперпозицію станів для обчислення необчислюваних функцій. Це неможливо при використанні стандартного квантового комп'ютера, оскільки доведено, що звичайний квантовий комп'ютер PSPACE-зводимий (квантовий комп'ютер, що працює поліноміальний час, може бути змодельований на класичному комп'ютері, що використовує поліноміальний простір).
Техніка, відома як необмежений детермінізм, може дозволяти обчислення необчислюваних функцій. Це питання є предметом обговорення в літературі.
Використання замкнених часоподібних кривих, всупереч поширеній думці, не дозволяє виконувати надтюрінгове обчислення, оскільки відсутній нескінченний об'єм пам'яті.
На початку 1990-х Хава Сігельманн запропонувала модель, засновану на нескінченній еволюції нейронних мереж, здатну проводити гіперобчислення.

Аналіз можливостей

Надтюрінгові обчислення мають багато пропозицій альтернативних способів, щоб прочитати оракул або ^[en] вбудовані в іншому випадку класичної машині. Інші надають доступ до деяких вищих рівнів ^[en]. Наприклад, багатофунуціональна машина Тюрінга, при звичайних припущеннях, зможе обчислити будь-який предикат, який містить $\Sigma _{1}^{0}$ або $\Pi _{1}^{0}$ . За допомогою обмеження рекурсії, навпаки, можна обчислити будь-який предикат або функцію у відповідному тюрінговому степені, який, як відомо, дорівнює $\Delta _{2}^{0}$ . Далі ^[en] показав, що обмеження часткової рекурсії дозволить обчислювати саме предикати $\Sigma _{2}^{0}$

Модель	Обчислювані предикати	Примітки
Баготофункціональність	tt( $\Sigma _{1}^{0},\Pi _{1}^{0}$ )	Залежно від зовнішнього спостерігача
Обмеження / проб і помилок	$\Delta _{2}^{0}$
Повторне обмеження ( K разів)	$\Delta _{k+1}^{0}$
^[en]	^[en]	Залежно від просторово-часової структури
Аналоговорецидивуюча нейронна мережа	$\Delta _{1}^{0}[f]$
Недетермінована машина Тюрінга	$\geq T(\Sigma _{1}^{1})$
Підвищення функції оракула	$\Delta _{1}^{1}$	Для моделі з однією послідовності; $\Pi _{1}^{1}$

Критика

Мартін Девіс, у своїх працях із надтюрінгових обчислень ставиться до цієї теми, як до «міфу» та пропонує контраргументи до фізичної реалізованості надтюрінгових обчислень. Що стосується його теорії, він полемізує й стверджує, що це нове поле, засноване в 1990-х. Ця точка зору ґрунтується на історії теорії обчислюваності (ступеня нерозв'язності, обчислюваності над функціями, дійсних чисел та ординалів).

Див. також

Примітки

Коупленд та Праудфут, Alan Turing's forgotten ideas in computer science [Архівовано 11 листопада 2013 у Wayback Machine.]. Scientific American, Квітень 1999
Алан Тюринг, 1939, Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2-45, Issue 1, pp. 161–228.[1] [Архівовано 19 листопада 2014 у Wayback Machine.]
«Припустимо, що ми отримали якийсь спосіб вирішення проблем теорії чисел, оракул, який дає вирішення таких завдань. Ми не повинні далі заглиблюватися в питання природи оракула, за винятком того, що він не може бути машиною» (Нерозв'язана 167 стр, перевидання праці Тюрінга Systems of Logic Based On Ordinals)
Див. наприклад Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability // Theor. Comput. Sci. 317, 1-3. — 2004. — Т. 317 (1 червня). — С. 105–114. — DOI:10.1016/j.tcs.2003.12.007. Архівовано з джерела 21 липня 2011. Процитовано 31 березня 2015.
Арнольд Шенхаге, «On the power of random access machines», in Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520–529, 1979. Source of citation: , «NP-complete Problems and Physical Reality» [Архівовано 15 січня 2010 у Wayback Machine.] p. 12
Джоел Девід Хемкінс та Енді Льюіс, Infinite time Turing machines [Архівовано 5 жовтня 2011 у Wayback Machine.], Journal of Symbolic Logic, 65(2):567—604, 2000.
Існують твердження на користь цього; дивись наприклад Tien Kieu. Quantum Algorithm for the Hilbert's Tenth Problem // Int. J. Theor. Phys.. — 2003. — Т. 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 [Архівовано 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 :. Архів оригіналу за 4 жовтня 2011. Процитовано 31 березня 2015.
Verifying Properties of Neural Networks [Архівовано 4 березня 2016 у Wayback Machine.] p.6
P.D. Welch. The extent of computation in Malament-Hogarth spacetimes // British J. for Philosophy of Science. — 2009. — Т. 59 (10 вересня). — С. 659–674. — arXiv:gr-qc/0609035.
Hava Siegelmann. Computation Beyond the Turing Limit // Science. — 1995. — Т. 268, вип. 5210 (1 квітня). — С. 545–548. — DOI:10.1126/science.268.5210.545. — PMID 17756722 .
Hava Siegelmann. Analog Computation via Neural Networks // Theoretical Computer Science. — 1994. — Т. 131, вип. 2. — С. 331–360. — DOI:10.1016/0304-3975(94)90178-3.
Joel David Hamkins. Infinite Time Turing machines // Journal of Symbolic Logic. — 2000. — Т. 65, вип. 2. — С. 567-604. — DOI:10.2307/2586556. Архівовано з джерела 5 жовтня 2011. Процитовано 2015-01-29.
Davis, Martin (2006). Why there is no such discipline as hypercomputation. Applied Mathematics and Computation. 178 (1): 4—7. doi:10.1016/j.amc.2005.09.066.
Davis, Martin (2004). The Myth of Hypercomputation. Alan Turing: Life and Legacy of a Great Thinker. Springer.

[CandP-1] Коупленд та Праудфут, Alan Turing's forgotten ideas in computer science [Архівовано 11 листопада 2013 у Wayback Machine.]. Scientific American, Квітень 1999

[2] Алан Тюринг, 1939, Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2-45, Issue 1, pp. 161–228.[1] [Архівовано 19 листопада 2014 у Wayback Machine.]

[3] «Припустимо, що ми отримали якийсь спосіб вирішення проблем теорії чисел, оракул, який дає вирішення таких завдань. Ми не повинні далі заглиблюватися в питання природи оракула, за винятком того, що він не може бути машиною» (Нерозв'язана 167 стр, перевидання праці Тюрінга Systems of Logic Based On Ordinals)

[4] Див. наприклад Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability // Theor. Comput. Sci. 317, 1-3. — 2004. — Т. 317 (1 червня). — С. 105–114. — DOI:10.1016/j.tcs.2003.12.007. Архівовано з джерела 21 липня 2011. Процитовано 31 березня 2015.

[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: , «NP-complete Problems and Physical Reality» [Архівовано 15 січня 2010 у Wayback Machine.] p. 12

[6] Джоел Девід Хемкінс та Енді Льюіс, Infinite time Turing machines [Архівовано 5 жовтня 2011 у Wayback Machine.], Journal of Symbolic Logic, 65(2):567—604, 2000.

[7] Існують твердження на користь цього; дивись наприклад Tien Kieu. Quantum Algorithm for the Hilbert's Tenth Problem // Int. J. Theor. Phys.. — 2003. — Т. 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 [Архівовано 6 березня 2010 у Wayback Machine.]

[8] Bernstein and Vazirani, Quantum complexity theory [Архівовано 11 березня 2016 у Wayback Machine.], SIAM Journal on Computing, 26(5):1411—1473, 1997.

[9] : BINDS lab: HAVA'S BIO :. Архів оригіналу за 4 жовтня 2011. Процитовано 31 березня 2015.

[10] Verifying Properties of Neural Networks [Архівовано 4 березня 2016 у Wayback Machine.] p.6

[11] P.D. Welch. The extent of computation in Malament-Hogarth spacetimes // British J. for Philosophy of Science. — 2009. — Т. 59 (10 вересня). — С. 659–674. — arXiv:gr-qc/0609035.

[12] Hava Siegelmann. Computation Beyond the Turing Limit // Science. — 1995. — Т. 268, вип. 5210 (1 квітня). — С. 545–548. — DOI:10.1126/science.268.5210.545. — PMID 17756722 .

[13] Hava Siegelmann. Analog Computation via Neural Networks // Theoretical Computer Science. — 1994. — Т. 131, вип. 2. — С. 331–360. — DOI:10.1016/0304-3975(94)90178-3.

[14] Joel David Hamkins. Infinite Time Turing machines // Journal of Symbolic Logic. — 2000. — Т. 65, вип. 2. — С. 567-604. — DOI:10.2307/2586556. Архівовано з джерела 5 жовтня 2011. Процитовано 2015-01-29.

[Davis95-15] Davis, Martin (2006). Why there is no such discipline as hypercomputation. Applied Mathematics and Computation. 178 (1): 4—7. doi:10.1016/j.amc.2005.09.066.

[16] Davis, Martin (2004). The Myth of Hypercomputation. Alan Turing: Life and Legacy of a Great Thinker. Springer.