Хиперрачунање — разлика између измена

Термин " супер-Тјурингово рачунање" појавио се почетком 1990-их, са најмање два независна извора наведена у литератури. Појавио се у разговорима, PhD тезе,<ref name="Siegelmann.1993"><cite class="citation thesis">Hava Siegelmann (Oct 1993). </cite></ref> па чак и ранији технички извештаји [[Хава Сигелман|Хаве Сигелмана]] од раних 1990-их за веома посебну теорију (описану у наставку) и постао је подобласт израчунавања од њеног [[Сајенс (магазин)|научног]] папира 1995.<ref name="Siegelmann.1995">{{<cite class="citation journal|author=">H.T. Siegelmann |title= |journal= |date=(Apr 1995|volume= |issue= |pages= |doi=). }}</cite></ref> Такође се појавио 1990. у разговору <ref name="Sta90">Mike Stannett, ''[https://www.researchgate.net/publication/258848388_1990_Super-Turing_Computation Super-Turing Computation]''.</ref> и 1991. у техничком извештају<ref name="Sta91">Mike Stannett, ''[https://www.researchgate.net/publication/236852111_An_Introduction_to_post-Newtonian_and_super-Turing_computation An Introduction to post-Newtonian and super-Turing computation]''.</ref>  [[Мајк Стенет|Мајка Стенета]], који је такође објавио теоријску дискусију једне [[X-машина|X-машине]] базиране на "супер-Тјуринговој машини" у марту 1990.<ref>{{citeMike journal|doi=Stannett, 1990, ''[http://link.springer.com/article/10.1007/BF01888233%2FBF01888233 |title=X-machines and the halting problem: Building a super-turingTuring machine]'' |date=1990 |last1=Stannett |first1=Mike |journal=Formal Aspects of Computing, Volume |volume=2, |pages=331–341Issue |s2cid=74069831. }}стр. 331-441. http://link.springer.com/article/10.1007%2FBF01888233</ref>

У раним 1990-им [[Хава Сигелман]] и [[Едуардо Сонтаг]] су доказали да је њихов нови компјутерски модел, Вештачка Рекурентна Природна Мрежа (''ARNN''), могла да обавља изван Тјурингове границе (хиперрачунање)<ref>{{<cite journal|authorclass="citation journal">H.T. Siegelmann and E.D. Sontag |title= |journal= |date=(1995). |volume= |issue= |pages= |doi= }}</cite></ref><ref>{{<cite class="citation journal|author=">H.T. Siegelmann and E.D. Sontag |title= |journal= |date=(1994). |volume= |issue= |pages= |doi= }}</cite></ref>

Сигелман и њене колеге су открили хијерархију добро утврђених рачунарских класа које почињу од Тјурингове машине и уздижу се до пуне супер Тјурингове снаге <ref>{{<cite journal|authorclass="citation journal">J.L. Balcázar and R. Gavaldà and H.T. Siegelmann |title= |journal= |date=(Jul 1997|volume=). |issue= |pages= |doi= }}</cite></ref> Сигелман је описала у разним публикацијама које постоје много начини да се дође до супер-Тјуринговог рачунања. Док је прво показала постојање супер-Тјуринговог рачунања преко аналогне неуронске мреже са фиксном (не за учење) и неограниченом тежином, отишла је да доказује супер-Тјурингову снагу у многим различитим остваривим машинама укључујући и мале прецизне тежине неуронске мреже које примају своју моћ од: учења у аналогном домену, или користећи стокастику,<ref name="Siegelmann.1998" /> или развијање током времена,<ref>{{<cite class="citation journal|author=">J. Cabessa and H. T. Siegelmann |title= |journal= |date=(2014). |volume= |issue= |pages= |doi= }}</cite></ref> или коришћење података из окружења, или система који су Тјурингови у било којим израчунљивим корацима и између промена на једну од наведених метода. Види још рад у [[Верификација својстава неуронских мрежа|Верификацији својстава неуронских мрежа]].

Сигелманин научни рад показује први корак ослобађања овог рачунања<ref name="Siegelmann.1995" /> док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања <math>2^{\aleph_0}</math> а простор Тјурингових машина само [[Алеф број|<math>\aleph_0</math>]], што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина. <ref>{{<cite class="citation journal|author=">J. Cabessa and H.T. Siegelmann |title= |journal= |date=(Apr 2012|volume=). |issue= |pages= |doi= }}</cite></ref>

<ref>J.P. Neto, H.T. Siegelmann, and J.F. Costa, "Implementation“Implementation of Programming Languages with Neural Nets",” International Journal of Computing Anticipatory Systems 1, 1997: 201-208</ref>

<ref>J. Kilian and H.T. Siegelmann, "The“The Dynamic Universality of Sigmoidal Neural Networks",” Information and Computation 128(1), 1996: 45-56.</ref>

<ref>H.T. Siegelmann, B.G. Horne, and C.L.Giles, "Computational“Computational Capabilities of Recurrent NARX Neural Networks",” IEEE Transaction on Systems, Man and Cybernetics – part B: Cybernetics 27(2), 1997: 208-215.</ref>

Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе.<ref>H.T. Siegelmann, A. Ben-Hur and S. Fishman, "Computational“Computational Complexity for Continuous Time Dynamics",” Physical Review Letters, 83(7), 1999: 1463-1466.</ref><ref>H.T. Siegelmann and S. Fishman, "Computation“Computation by Dynamical Systems",” Physica D 120, 1998 (1-2): 214-235.</ref> Као конкретан пример Сигелманова група је анализирала линеарно програмирање и друге компјутерско научне проблеме који показују да аналогни рачунари могу да реше брже од дискретних временских рачунара. <ref>A. Ben-Hur, J. Feinberg, S. Fishman and H. T. Siegelmann, "Random“Random matrix theory for the analysis of the performance of an analog computer: a scaling theory",” Physics Letters A. 323(3-4), March 2004: 204-209.</ref>

<ref>A. Ben-Hur, J. Feinberg, S. Fishman and H. T. Siegelmann, "Probabilistic“Probabilistic analysis of a differential equation for linear programming",” Journal of Complexity 19(4), August 2003: 474-510.</ref>

<ref>H. T. Siegelmann, "Turing“Turing on Super-Turing and Adaptivity"Adaptivity”.</ref> Сигелман и Сонтаг су предложили нову рачунарску хипотезу - док аналогно, учење, и еволуирајући системи су били ограничени супер-Тјуринговом рачунском снагом.

* Средином 1960-их, [[Е Марк Голд]] и [[Хилари Патнам]] независно су предложили моделе [[Индукција (логика)|индуктивног закључивања]] (на "ограничавање рекурзивних функционалности"<ref name="LimRecurs">{{<cite class="citation journal|author=">E. M. Gold |title= |journal= |date=(1965). |volume= |issue= |pages= |doi= }}</cite></ref> и "суђење и грешке предиката",<ref name="TrialError">{{<cite class="citation journal|author=">Hilary Putnam |title= |journal= |date=(1965). |volume= |issue= |pages= |doi= }}</cite></ref> ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све [[Рекурзивно бројиви скупови|рекурзивно бројиве скупове]] језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)"<ref name="TrialError" /> [[Л. К. Шуберт]]ов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања" <ref name="IterLimRec">{{<cite class="citation journal|author=">L. K. Schubert |title= |journal= |date=(July 1974|volume=). |issue= |pages= |doi= }}</cite></ref> проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком [[Аритметичка хијерархија|аритметичком]] предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина."

* Предложена техника позната као [[Неограничена недетерминисана|фер недетерминисана]] или [[неограничена недетерминисана]] може дозволити израчунавања неизрачунљивих функција.<ref>{{<cite journal|authorclass="citation journal">Edith Spaan, Leen Torenvliet and Peter van Emde Boas |title= |journal= |date=(1989). |volume= |issue= |pages= |doi= }}</cite></ref> Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве".

* '''Бесконачно време Тјурингове машине''' је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним [[Редни број|редним бројевима]]. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање [[Лимит редног броја|лимита редног броја]] и којима су резултати претходно бесконачног израчунавања доступни.<ref>{{cite journal |author=Joel David Hamkins and Andy Lewis, |title=Infinite time Turing machines, |url=http://jdh.hamkins.org/Publications/2000e |journal=''Journal of Symbolic Logic'', |date=2000 |volume=65 |issue=(2 |pages=567–604 |doi=10.2307/2586556 |jstor=2586556 |arxiv=math/9808093 |access):567-date=15.604, 012000. 2016 |archive-date=05. 10. 2011 |archive-url=https[http://webjdh.archivehamkins.org/web/20111005150801Publications/2000e] {{Wayback|url=http://jdh.hamkins.org/Publications/2000e |url-statusdate=20111005150801 }}</ref>

* Симбол секвенце је ''израчунљив у року'' ако постоји коначан, вероватно незаустављив програм на [[Универзална Тјурингова машина|универзалној Тјуринговој машини]] која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други [[Израчунљив број|израчунљив реалан број]], али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао [[Јирген Шмидхубер]], може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио [[Курт Гедел]] (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе [[Халтинг проблем|заустављање проблема]] би могло бити решено. Шмидхубер (<ref name="genTuring2000">{{<cite class="citation journal|author=">Jürgen Schmidhuber |title= |journal= |date=(2000). |volume= |issue= |pages= |doi= }}</cite></ref><ref name="GenKolm">{{<cite class="citation journal|author=">J. Schmidhuber |title= |journal= |date=(2002). |volume= |issue= |pages= |doi= }}</cite></ref>) користи овај приступ да дефинише скуп формално описивих или конструктивно израчунљивих универзума или конструктивне [[Теорија свега|теорије свега]]. Генерализоване Тјурингове машине могу да реше проблем обуставе проценом [[Спикер секвенца|Спикер секвенце]].

* [[Квантна механика|Квантномеханички]] систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-[[Израчунљива функција|израчунљиву функцију]].<ref>There have been some claims to this effect; see <cite class="citation journal">Tien Kieu (2003). </cite></ref> То није могуће користећи стандардни [[кјубит]]-модел [[Квантни рачунар|квантног компјутера]], јер је доказано да редовни квантни компјутер [[PSPACE-умањен]] (квантни компјутер који ради у [[Субекспоненцијално време|полиномијалном времену]] може да симулира класични компјутер који ради у [[Простор полинома|простору полинома]]).<ref>{{citeBernstein & Vazirani, journal|title=Quantum complexity theory, |url=journal=SIAM Journal on Computing, |date=1997 |volume=26|issue=(5|pages=1411–1473|doi=10):1411-1473, 1997.1137 [http:/S0097539796300921 |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |journal=SIAM Journal on Computing }}/www.cs.berkeley.edu/~vazirani/bv.ps]</ref>

* 1970, Е. С. Сантос дефинисао је класу [[Расплинута логика|расплинуте логике]] засноване на "нејасном алгоритму" и "фази Тјурингове машине".<ref>{{<cite class="citation journal|author=">Santos, Eugene S. |title= |journal= |date=(1970). |volume= |issue= |pages= |doi= }}</cite></ref> Након тога, Л. Биаћино и Г. Герла су показали да би таква дефиниција омогућавала прорачун нерекурзивних језика; они су предложили алтернативни скуп дефиниција без ове тешкоће.<ref>{{<cite journal|authorclass="citation journal">Biacino, L.; Gerla, G. |title= |journal= |date=(2002). |volume= |issue= |pages= |doi= }}</cite></ref> Јири Видерман је анализирао могућности Сантосовог првобитног предлога 2004. године. <ref name="ClassicalFuzzy">{{<cite class="citation journal|author=">Wiedermann, Jiří |title= |journal= |date=(2004). |volume= |issue= |pages= |doi= }}</cite></ref>

| <ref>{{Cite book|author=Lenore Blum |author-link=Lenore Blum |last2=Cucker|first2=Felipe| last3 = Shub | first3 = Michael |last4=Smale|first4=Stephen|author4-link= Stephen Smale |title=Complexity and Real Computation|year=1998 |isbn=978-0-387-98281-6|pages=|publisher=Springer }}</ref>

* '''еволуционарне Тјурингове машине''' (Еуген Ебербах <ref>{{<cite class="citation journal|author=">Eugene Eberbach |title= |journal= |date=(2002). |volume= |issue= |pages= |doi= }}</cite></ref>)

* '''трансрекурзивни оператори''' (Бородиански и Бургин <ref>{{<cite class="citation journal|author=">Borodyanskii, Yu M; Burgin, M. S. |title= |journal= |date=(1994). |volume= |issue= |pages= |doi= }}</cite></ref>)

[[Мартин Дејвис]], у својим списима о хиперрачунању <ref name="Davis95">{{<cite class="citation journal|author=">Davis, Martin |title= |journal= |date=(2006). |volume= |issue= |pages= |doi= }}</cite></ref>{{sfn|Davis|2004|pp=}} односи се на овој теми као "мит" и нуди контра-аргументе за физички остваривостима хиперрачунања. Што се тиче његове теорије, тврди да је ово ново поље основано 1990. године. Ова тачка гледишта се ослања на историју теорије израчунљивости (степени нерешивости, израчунљивост над функцијама, реалних бројева и редних бројева), као и горе наведено. У свом аргументу он прави примедбу да је све тривијално као: "''Ако је неизрачунљивим улазима дозвољено онда су неизрачунљиви резултати достижни".'' Широко је прихваћено да се ова критика односи на најраније математичке и филозофске сугестије и игнорише многе од новијих предлога који нису предмет критике.

* {{citeToby journalOrd. [[arxiv:math/0209332|date= 2002|title=''Hypercomputation: Computing more than the Turing machine can compute'']]: |url=A |journal=survey |volume=|issue=article |pages=on |doi=various |arxiv=math/0209332|last1=forms Ord|first1=of Toby}}hypercomputation.

* {{citeVolkmar journalPutz |date=and 2010Karl Svozil, ''[[arxiv:1003.1238|title=Can a computer be "pushed" to perform faster-than-light?]]'', |url= |journal= |volume=|issue= |pages= |doi= |arxiv=1003.1238|last1= Putz|first1= Volkmar|last2= Svozil|first2= Karl}}(2010)

* {{cite journal |date= 2002[[arxiv:math/0209332|title=Toby Ord, ''Hypercomputation: computing more than the Turing machine'' |url= |journal= |volume=|issue= |pages= |doi= |arxiv=math/0209332|last1= Ord|first1= Toby}}]]