Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Гіперобчислення

Гіперобчислення

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

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

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

Історія

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

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

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

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

Надтюрінгові обчислення мають багато пропозицій альтернативних способів, щоб прочитати оракул або [en] вбудовані в іншому випадку класичної машині. Інші надають доступ до деяких вищих рівнів [en]. Наприклад, багатофунуціональна машина Тюрінга, при звичайних припущеннях, зможе обчислити будь-який предикат, який містить image або image. За допомогою обмеження рекурсії, навпаки, можна обчислити будь-який предикат або функцію у відповідному тюрінговому степені, який, як відомо, дорівнює image. Далі [en] показав, що обмеження часткової рекурсії дозволить обчислювати саме предикати image

Модель Обчислювані предикати Примітки Посилання
Баготофункціональність tt(image) Залежно від зовнішнього спостерігача
Обмеження / проб і помилок image
Повторне обмеження ( K разів) image
[en] [en] Залежно від просторово-часової структури
Аналоговорецидивуюча нейронна мережа image
Недетермінована машина Тюрінга image
Підвищення функції оракула image Для моделі з однією послідовності; image

Критика

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

Див. також

Примітки

  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. . Архів оригіналу за 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.
  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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Giperobchislennyami abo nadtyuringovimi obchislennyami angl hypercomputation nazivayut taki obchislennya yaki ne mozhut buti vikonani na mashini Tyuringa Voni vklyuchayut v sebe riznomanitni gipotetichni metodi zasnovani na en a takozh deyaki inshi tipi obchislen napriklad interaktivni obchislennya Termin giperobchislennya buv vpershe vvedenij en ta Dianoyu Praudfut Termini ne mozhna nazvati sinonimami nadtyuringove obchislennya na vidminu vid giperobchislennya yak pravilo oznachaye sho zaproponovana model povinna buti fizichno realizovanoyu Mozhlivist fizichnoyi realizaciyi takih obchislen aktivno obgovoryuyetsya IstoriyaModeli bilsh potuzhni nizh mashina Tyuringa buli vvedeni Alanom Tyuringom v jogo roboti 1939 roku en Cya robota doslidzhuvala matematichni sistemi v yakih isnuvav orakul yakij mig virahuvati odnu dovilnu nerekursivnu funkciyu na mnozhini naturalnih chisel Vin vikoristav cyu model dlya togo shob pokazati sho navit u takij bilsh potuzhnij sistemi vse odno prisutni neobchislyuvani funkciyi U svoyij roboti Tyuring yasno dav zrozumiti sho taka model ye ne bilsh nizh matematichnoyu abstrakciyeyu i ne mozhe buti realizovana v realnomu sviti Peredbachuvani sposobi giperobchilennyaMashina Tyuringa yaka mozhe vikonati neskinchennu kilkist krokiv za skinchennij chas prosto mozhlivist roboti mashini Tyuringa protyagom neskinchennogo chasu tobto potencijna neskinchennist nedostatnya Odin z peredbachuvanih sposobiv dosyagti takogo rezultatu vikoristovuvati upovilnennya chasu dlya togo shob dozvoliti komp yuteru zrobiti neskinchennu kilkist cikliv za skinchennij po godinah dlya zovnishnogo sposterigacha chas take obchislennya potrebuyut neskinchennoyi energiyi div prostir chas Malameta Hogarta She odnim chisto matematichnim sposobom ye tak zvana mashina Zenona zasnovana na paradoksi Zenona Mashina Zenona vikonuye svij pershij krok obchislen za chas napriklad 1 hvilinu drugij za hvilini tretij za hvilini i t d Pidsumovuyuchi cyu neskinchennu geometrichnu progresiyu mi otrimayemo sho mashina vikonuye neskinchennu kilkist krokiv protyagom 2 hvilin Odnak deyaki stverdzhuyut sho vidpovidno do mirkuvann v paradoksi Zenona taka mashina ne lishe fizichno a j logichno nemozhliva Originalni orakul mashini Tyuringa sho buli nim vinajdeni u 1939 Dijsnij komp yuter pidvid idealizovanogo analogovogo komp yutera zdatnij zdijsnyuvati giperobchislennya za umovi sho fizika pripuskaye isnuvannya spravzhnih dijsnih chisel Ce jmovirno vimagaye isnuvannya yakihos duzhe divnih zakoniv fiziki napriklad nayavnosti vimirnoyi fizichnoyi konstanti yaka mozhe buti vikoristana yak orakul div napriklad en ta povinno yak minimum vimagati mozhlivosti vimiryuvannya fizichnih konstant z dovilnoyu tochnistyu nezvazhayuchi na teplovij shum i kvantovomehanichni efekti Vichna mashina Tyuringa ce uzagalnennya mashini Zenona yaka mozhe vikonati neviznacheno trivale obchislennya kroki v yakomu perenumerovani potencijno transfinitno ordinalnimi chislami Vona modelyuye zvichajnu u vsih inshih sensah mashinu Tyuringa dlya yakoyi nezupinni obchislennya zavershuyutsya shlyahom dosyagnennya specialnogo stanu zarezervovanogo dlya dosyagnennya en i dlya yakoyi dostupni rezultati vsih poperednih neskinchennih obchislen Kvantovomehanichni sistemi yaki yakimos chinom vikoristovuyut napriklad neskinchennu superpoziciyu staniv dlya obchislennya neobchislyuvanih funkcij Ce nemozhlivo pri vikoristanni standartnogo kvantovogo komp yutera oskilki dovedeno sho zvichajnij kvantovij komp yuter PSPACE zvodimij kvantovij komp yuter sho pracyuye polinomialnij chas mozhe buti zmodelovanij na klasichnomu komp yuteri sho vikoristovuye polinomialnij prostir Tehnika vidoma yak neobmezhenij determinizm mozhe dozvolyati obchislennya neobchislyuvanih funkcij Ce pitannya ye predmetom obgovorennya v literaturi Vikoristannya zamknenih chasopodibnih krivih vsuperech poshirenij dumci ne dozvolyaye vikonuvati nadtyuringove obchislennya oskilki vidsutnij neskinchennij ob yem pam yati Na pochatku 1990 h Hava Sigelmann zaproponuvala model zasnovanu na neskinchennij evolyuciyi nejronnih merezh zdatnu provoditi giperobchislennya Analiz mozhlivostejNadtyuringovi obchislennya mayut bagato propozicij alternativnih sposobiv shob prochitati orakul abo en vbudovani v inshomu vipadku klasichnoyi mashini Inshi nadayut dostup do deyakih vishih rivniv en Napriklad bagatofunucionalna mashina Tyuringa pri zvichajnih pripushennyah zmozhe obchisliti bud yakij predikat yakij mistit S 1 0 displaystyle Sigma 1 0 abo P 1 0 displaystyle Pi 1 0 Za dopomogoyu obmezhennya rekursiyi navpaki mozhna obchisliti bud yakij predikat abo funkciyu u vidpovidnomu tyuringovomu stepeni yakij yak vidomo dorivnyuye D 2 0 displaystyle Delta 2 0 Dali en pokazav sho obmezhennya chastkovoyi rekursiyi dozvolit obchislyuvati same predikati S 2 0 displaystyle Sigma 2 0 Model Obchislyuvani predikati Primitki Posilannya Bagotofunkcionalnist tt S 1 0 P 1 0 displaystyle Sigma 1 0 Pi 1 0 Zalezhno vid zovnishnogo sposterigacha Obmezhennya prob i pomilok D 2 0 displaystyle Delta 2 0 Povtorne obmezhennya K raziv D k 1 0 displaystyle Delta k 1 0 en en Zalezhno vid prostorovo chasovoyi strukturi Analogovorecidivuyucha nejronna merezha D 1 0 f displaystyle Delta 1 0 f Nedeterminovana mashina Tyuringa T S 1 1 displaystyle geq T Sigma 1 1 Pidvishennya funkciyi orakula D 1 1 displaystyle Delta 1 1 Dlya modeli z odniyeyu poslidovnosti P 1 1 displaystyle Pi 1 1 KritikaMartin Devis u svoyih pracyah iz nadtyuringovih obchislen stavitsya do ciyeyi temi yak do mifu ta proponuye kontrargumenti do fizichnoyi realizovanosti nadtyuringovih obchislen Sho stosuyetsya jogo teoriyi vin polemizuye j stverdzhuye sho ce nove pole zasnovane v 1990 h Cya tochka zoru gruntuyetsya na istoriyi teoriyi obchislyuvanosti stupenya nerozv yaznosti obchislyuvanosti nad funkciyami dijsnih chisel ta ordinaliv Div takozhTeza Chercha Prorocha mashina Mashina Zenona Obchislennya Aporiyi ZenonaPrimitkiKouplend ta Praudfut Alan Turing s forgotten ideas in computer science 11 listopada 2013 u Wayback Machine Scientific American Kviten 1999 Alan Tyuring 1939 Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2 45 Issue 1 pp 161 228 1 19 listopada 2014 u Wayback Machine Pripustimo sho mi otrimali yakijs sposib virishennya problem teoriyi chisel orakul yakij daye virishennya takih zavdan Mi ne povinni dali zagliblyuvatisya v pitannya prirodi orakula za vinyatkom togo sho vin ne mozhe buti mashinoyu Nerozv yazana 167 str perevidannya praci Tyuringa Systems of Logic Based On Ordinals Div napriklad Shagrir O Super tasks accelerating Turing machines and uncomputability Theor Comput Sci 317 1 3 2004 T 317 1 chervnya S 105 114 DOI 10 1016 j tcs 2003 12 007 z dzherela 21 lipnya 2011 Procitovano 31 bereznya 2015 Arnold Shenhage 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 sichnya 2010 u Wayback Machine p 12 Dzhoel Devid Hemkins ta Endi Lyuis Infinite time Turing machines 5 zhovtnya 2011 u Wayback Machine Journal of Symbolic Logic 65 2 567 604 2000 Isnuyut tverdzhennya na korist cogo divis napriklad Tien Kieu Quantum Algorithm for the Hilbert s Tenth Problem Int J Theor Phys 2003 T 42 S 1461 1478 DOI 10 1023 A 1025780028846 ta procitovanu tam literaturu Pomilki pidhodu Kieu buli vkazani Warren D Smith u Three counterexamples refuting Kieu s plan for quantum adiabatic hypercomputation and some uncomputable quantum mechanical tasks 6 bereznya 2010 u Wayback Machine Bernstein and Vazirani Quantum complexity theory 11 bereznya 2016 u Wayback Machine SIAM Journal on Computing 26 5 1411 1473 1997 Arhiv originalu za 4 zhovtnya 2011 Procitovano 31 bereznya 2015 Verifying Properties of Neural Networks 4 bereznya 2016 u Wayback Machine p 6 P D Welch The extent of computation in Malament Hogarth spacetimes British J for Philosophy of Science 2009 T 59 10 veresnya S 659 674 arXiv gr qc 0609035 Hava Siegelmann Computation Beyond the Turing Limit Science 1995 T 268 vip 5210 1 kvitnya S 545 548 DOI 10 1126 science 268 5210 545 PMID 17756722 Hava Siegelmann Analog Computation via Neural Networks Theoretical Computer Science 1994 T 131 vip 2 S 331 360 DOI 10 1016 0304 3975 94 90178 3 Joel David Hamkins Infinite Time Turing machines Journal of Symbolic Logic 2000 T 65 vip 2 S 567 604 DOI 10 2307 2586556 z dzherela 5 zhovtnya 2011 Procitovano 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

Дата публікації:
Топ