Гіперобчислення
Гіперобчисленнями або надтюрінговими обчисленнями, (англ. hypercomputation) називають такі обчислення, які не можуть бути виконані на машині Тюрінга. Вони включають в себе різноманітні гіпотетичні методи, засновані на суперрекурсивних алгоритмах[en], а також деякі інші типи обчислень — наприклад, інтерактивні обчислення. Термін гіперобчислення був вперше введений Джеком Коуплендом[en] та Діаною Праудфут[1].
Терміни не можна назвати синонімами: «надтюрінгове обчислення» на відміну від «гіперобчислення», як правило, означає, що запропонована модель повинна бути фізично реалізованою.
Можливість фізичної реалізації таких обчислень активно обговорюється.
Історія[ред. | ред. код]
Моделі більш потужні, ніж машина Тюрінга, були введені Аланом Тюрінгом в його роботі 1939 року Системи логік, засновані на ординалах[en][2]. Ця робота досліджувала математичні системи, в яких існував оракул, який міг вирахувати одну довільну нерекурсивну функцію на множині натуральних чисел. Він використав цю модель для того, щоб показати, що навіть у такій, більш потужній системі, все одно присутні необчислювані функції. У своїй роботі Тюрінг ясно дав зрозуміти, що така модель є не більш ніж математичною абстракцією і не може бути реалізована в реальному світі[3].
Передбачувані способи гіперобчилення[ред. | ред. код]
- Машина Тюрінга, яка може виконати нескінченну кількість кроків за скінченний час (просто можливість роботи машини Тюрінга протягом нескінченного часу (тобто потенційна нескінченність) недостатня). Один з передбачуваних способів досягти такого результату — використовувати уповільнення часу для того, щоб дозволити комп'ютеру зробити нескінченну кількість циклів за скінченний по годинах для зовнішнього спостерігача час (таке обчислення потребують нескінченної енергії — див. простір-час Маламета — Хогарта). Ще одним, чисто математичним, способом є так звана машина Зенона, заснована на парадоксі Зенона. Машина Зенона виконує свій перший крок обчислень за час, наприклад, 1 хвилину, другий за ½ хвилини, третій за ¼ хвилини і т. д. Підсумовуючи цю нескінченну геометричну прогресію, ми отримаємо, що машина виконує нескінченну кількість кроків протягом 2 хвилин. Однак, деякі стверджують, що, відповідно до міркуваннь в парадоксі Зенона, така машина не лише фізично, а й логічно неможлива.[4]
- Оригінальні оракул-машини Тюрінга, що були ним винайдені у 1939.
- Дійсний комп'ютер (підвид ідеалізованого аналогового комп'ютера) здатний здійснювати гіперобчислення[5] за умови, що фізика припускає існування справжніх дійсних чисел. Це, ймовірно, вимагає існування якихось дуже дивних законів фізики (наприклад наявності вимірної фізичної константи, яка може бути використана як оракул — див., наприклад, константа Хайтина[en]) та повинно, як мінімум, вимагати можливості вимірювання фізичних констант з довільною точністю, незважаючи на тепловий шум і квантовомеханічні ефекти.
- Вічна машина Тюрінга — це узагальнення машини Зенона, яка може виконати невизначено тривале обчислення, кроки в якому перенумеровані потенційно трансфінітно ординальними числами. Вона моделює звичайну у всіх інших сенсах машину Тюрінга, для якої незупинні обчислення завершуються шляхом досягнення спеціального стану, зарезервованого для досягнення граничного ординалу[en], і для якої доступні результати всіх попередніх нескінченних обчислень.[6]
- Квантовомеханічні системи, які якимось чином використовують, наприклад, нескінченну суперпозицію станів для обчислення необчислюваних функцій.[7] Це неможливо при використанні стандартного квантового комп'ютера, оскільки доведено, що звичайний квантовий комп'ютер PSPACE-зводимий (квантовий комп'ютер, що працює поліноміальний час, може бути змодельований на класичному комп'ютері, що використовує поліноміальний простір).[8]
- Техніка, відома як необмежений детермінізм, може дозволяти обчислення необчислюваних функцій. Це питання є предметом обговорення в літературі.
- Використання замкнених часоподібних кривих, всупереч поширеній думці, не дозволяє виконувати надтюрінгове обчислення, оскільки відсутній нескінченний об'єм пам'яті.
- На початку 1990-х Хава Сігельманн[9] запропонувала модель, засновану на нескінченній еволюції нейронних мереж, здатну проводити гіперобчислення.[10]
Аналіз можливостей[ред. | ред. код]
Надтюрінгові обчислення мають багато пропозицій альтернативних способів, щоб прочитати оракул або консультативну функцію[en] вбудовані в іншому випадку класичної машині. Інші надають доступ до деяких вищих рівнів арифметичної ієрархії[en]. Наприклад, багатофунуціональна машина Тюрінга, при звичайних припущеннях, зможе обчислити будь-який предикат, який містить або . За допомогою обмеження рекурсії, навпаки, можна обчислити будь-який предикат або функцію у відповідному тюрінговому степені, який, як відомо, дорівнює . Далі Ґолд[en] показав, що обмеження часткової рекурсії дозволить обчислювати саме предикати
Модель | Обчислювані предикати | Примітки | Посилання |
---|---|---|---|
Баготофункціональність | tt() | Залежно від зовнішнього спостерігача | |
Обмеження / проб і помилок | |||
Повторне обмеження ( K разів) | |||
Простір Маламента-Хогарта[en] | HYP[en] | Залежно від просторово-часової структури | [11] |
Аналоговорецидивуюча нейронна мережа | [12][13] | ||
Недетермінована машина Тюрінга | [14] | ||
Підвищення функції оракула | Для моделі з однією послідовності; |
Критика[ред. | ред. код]
Мартін Девіс, у своїх працях із надтюрінгових обчислень[15][16] ставиться до цієї теми, як до «міфу» та пропонує контраргументи до фізичної реалізованості надтюрінгових обчислень. Що стосується його теорії, він полемізує й стверджує, що це нове поле, засноване в 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: . Архівовано з джерела 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: Scott Aaronson, «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: . та процитовану там літературу. Помилки підходу 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: . — PMID 17756722 .
- ↑ Hava Siegelmann. Analog Computation via Neural Networks // Theoretical Computer Science. — 1994. — Т. 131, вип. 2. — С. 331–360. — DOI: .
- ↑ Joel David Hamkins. Infinite Time Turing machines // Journal of Symbolic Logic. — 2000. — Т. 65, вип. 2. — С. 567-604. — DOI: . Архівовано з джерела 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.