Пређи на садржај

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

С Википедије, слободне енциклопедије
Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке
Нема описа измене
Ред 148: Ред 148:
* [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]
* [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]
* Toby Ord. [[arxiv:math/0209332|''Hypercomputation: Computing more than the Turing machine can compute'']]: A survey article on various forms of hypercomputation.
* Toby Ord. [[arxiv:math/0209332|''Hypercomputation: Computing more than the Turing machine can compute'']]: A survey article on various forms of hypercomputation.
* Apostolos Syropoulos . ''[http://www.springer.com/computer/foundations/book/978-0-387-30886-9 Hypercomputation: Computing Beyond the Church-Turing Barrier]'' ([http://books.google.com/books?id=5gVOf_OQa04C preview]), Springer. {{page|year=2008|isbn=978-0-387-30886-9|pages=}}
* {{cite book|last=Syropoulos|first=Apostolos|title=Hypercomputation: Computing Beyond the Church-Turing Barrier|url=http://books.google.com/books?id=5gVOf_OQa04C|date=10 December 2008|publisher=Springer Science & Business Media|isbn=978-0-387-49970-3}}
* Burgin, M. S. (1983) Inductive Turing Machines, ''Notices of the Academy of Sciences of the USSR'', v. 270, No. 6. pp. 1289–1293
* 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 . ''Super-recursive algorithms'', Monographs in computer science, Springer. {{page|year=2005|id=ISBN 0-387-95569-0|pages=}}
* Mark Burgin . ''Super-recursive algorithms'', Monographs in computer science, Springer. {{page|year=2005|id=ISBN 0-387-95569-0|pages=}}

Верзија на датум 31. јануар 2016. у 04:01

Хиперрачунање или супер-Тјурингово рачунање се односи на моделе рачунања који превазилазе Турингову израчунљивост. Ово укључује различите хипотетичке методе за израчунавање не-Тјурингове-израчунљиве функције.

Термин " супер-Тјурингово рачунање" појавио се почетком 1990-их, са најмање два независна извора наведена у литератури. Појавио се у разговорима, PhD тезе,[1] па чак и ранији технички извештаји Хаве Сигелмана од раних 1990-их за веома посебну теорију (описану у наставку) и постао је подобласт израчунавања од њеног научног папира 1995.[2] Такође се појавио 1990. у разговору [3] и 1991. у техничком извештају[4]  Мајка Стенета, који је такође објавио теоријску дискусију једне X-машине базиране на "супер-Тјуринговој машини" у марту 1990.[5]

Термин "хиперрачунање" уведен је у 1999. од стране Џека Копленда и Дајане Праудфут.[6]

Услови нису баш синоними: "супер-Тјурингово израчунавање" од Сигелмана обично подразумева да ће предложени модел вероватно постојати у природи (преко биологије и / или физике) и стога може да буде физички остварив, док "хиперрачунање" може бити општа математичка или филозофска идеја.

Историја

Математички модел који иде преко Тјурингових машина је увео Алан Тјуринг 1938. у својој докторској дисертацији Системи логике базирани на ординалима.[7] Овај рад је истраживао математичке системе у којима је пророчка машина била доступна, што би могло да израчуна једну произвољну (не) рекурзивну функцију из природних бројева у природне бројеве. Он је користио овај уређај да докаже да чак и у оним моћнијим системима, неодлучив задатак је и даље присутан. Тјурингове пророчке машине су математичке апстракције, а нису физички оствариве.[8]

Хиперрачунање и Черч–Тјурингова теза

Черч–Тјурингова теза наводи да се свака алгоритмички израчунљива функција може израчунати помоћу Турингове машине. Суперкомпјутери рачунају функције које Тјурингова машина не може и који су, стога, неизрачунљиви у Черч-Туринговом смислу.

Пример проблема који Тјурингова машина не може да реши јесте Халтинг проблем. Тјурингова машина не може да одлучи да ли се произвољан програм зауставља или ради заувек. Неки предлажу да би суперкомпјутери могли да симулирају програм са бесконачним бројем корака и да укажу кориснику да ли је програм заустављен. Посебно, Сигелман је показала у својој докторској дисертацији 1993,[1] и касније у својој књизи 1998,[9] да Халтинг проблем Тјурингових машина може да се реши са аналогним периодичним неуронским мрежама.

Супер-Тјурингово рачунање и супер-Тјурингова теза

У раним 1990-им Хава Сигелман и Едуардо Сонтаг су доказали да је њихов нови компјутерски модел, Вештачка Рекурентна Природна Мрежа (ARNN), могла да обавља изван Турингове границе (хиперрачунање)[10][11]

Сигелман и њене колеге су открили хијерархију добро утврђених рачунарских класа које почињу од Тјурингове машине и уздижу се до пуне супер Тјурингове снаге [12] Сигелман је описала у разним публикацијама које постоје много начини да се дође до супер-Тјуринговог рачунања. Док је прво показала постојање супер-Тјуринговог рачунања преко аналогне неуронске мреже са фиксном (не за учење) и неограниченом тежином, отишла је да доказује супер-Тјурингову снагу у многим различитим остваривим машинама укључујући и мале прецизне тежине неуронске мреже које примају своју моћ од: учења у аналогном домену, или користећи стокастику,[9] или развијање током времена,[13] или коришћење података из окружења, или система који су Тјурингови у било којим израчунљивим корацима и између промена на једну од наведених метода. Погледајте такође рад у Верификацији својстава неуронских мрежа.

Сигелманин научни рад показује први корак ослобађања овог рачунања[2] док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања  а простор Тјурингових машина само , што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина. [14]

Теорија је довела до бољег разумевања неуронске мреже (Фондација дубоког учења) и подржаних иновативних апликација у тако осетљивим областима као што су регистрације радара и контрола нуклеарних електрана. [15] [16] [17] [18] Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе.[19][20] Као конкретан пример Сигелманова група је анализирала линеарно програмирање и друге компјутерско научне проблеме који показују да аналогни рачунари могу да реше брже од дискретних временских рачунара. [21] [22]

Недавна публикација открива да је Алан Тјуринг био у потрази за супер-Тјуринговим израчунавањем заснованим на принципима мозга, и показао своје предложене правце како се траже да се савршено слажу са Сигелманим теоријама. [23] Сигелман и Сонтаг су предложили нову рачунарску хипотезу - док аналогно, учење, и еволуирајући системи су били ограничени супер-Тјуринговом рачунском снагом.

Остали предлози супер-рачунара

  • Тјурингова машина која може да заврши бесконачно много корака. Једноставно бити у стању да ради за неограничен број корака није довољно. Један математички модел је Зенонова машина (инспирисано Зеноновим парадоксима). Зенонова машина обавља свој први корак у израчунавању (рецимо) 1 минут, други корак у ½ минут, трећи корак у ¼ минут, итд Сумирајући 1+½+¼+... (геометријска серија) видимо да машина обавља бесконачно много корака у укупно 2 минута. Према Шагриру, Зенонове машине уводе физичке парадоксе, а њихово стање је логично дефинисано ван једне стране отвореног периода [0, 2), тако недефинисана тачно у 2 минута после почетка рачунања.[24]
  • Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939.
  • Средином 1960-их, Е Марк Голд и Хилари Патнам независно су предложили моделе индуктивног закључивања (на "ограничавање рекурзивних функционалности"[25] и "суђење и грешке предиката",[26] ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све рекурзивно бројиве скупове језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)"[26] Л. К. Шубертов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања" [27] проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком аритметичком предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина."
  • Прави компјутер (нека врста идеализованог аналогног рачунара) може обављати хиперрачунање [28] ако физика признаје опште реалне променљиве (не само за израчунавање реалних бројева), а то су на неки начин "упрегнуте" за обрачун. Ово може захтевати доста бизарних закона физике (на пример, мерљива физичка константа са пророчком вредношћу, као што су Чејтинова константа), те би у најмању руку захтевала способност да измери стварну-вредности физичке вредност произвољне прецизности и поред топлотне буке и квантних ефеката.
  • Предложена техника позната као фер недетерминисана или неограничена недетерминисана може дозволити израчунавања неизрачунљивих функција.[29] Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве".
  • Чини се да је природна могућност путовања кроз време (постојање затворених временских кривих (CTCs) чини хиперрачунање могуће само по себи. Међутим, то није тако пошто CTC не даје (по себи) неограничену количину складишног капацитета која би бесконачно рачунање захтевала. Ипак, постоје време и простор у којима се CTC регион може користити за релативистичко хиперрачунање.[30] Приступ CTC може дозволити брзо решење PSPACE-комплетних проблема, комплексност класе која, док је Тјуринг-одлучив, се генерално сматра рачунски сложеним.[31][32]
  • Према 1992 папиру,[33] рачунар који ради на Маламент-Хогарт простору и времену или у орбити око ротирајуће црне рупе [34] теоретски се може обављати без Тјуринговог израчунавања.[35][36]
  • Бесконачно време Тјурингове машине је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним редним бројевима. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање лимита редног броја и којима су резултати претходно бесконачног израчунавања доступни.[37]
  • Јан ван Леувен и Јири Видерман су написали папир [38] сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен саветима функција које представљају способност рачунара да се надогради.
  • Симбол секвенце је израчунљив у року ако постоји коначан, вероватно незаустављив програм на универзалној Тјуринговој машини која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други израчунљив реалан број, али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао Јирген Шмидхубер, може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио Курт Гедел (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе заустављање проблема би могло бити решено. Шмидхубер ([39][40]) користи овај приступ да дефинише скуп формално описивих или конструктивно израчунљивих универзума или конструктивне теорије свега. Генерализоване Тјурингове машине могу да реше проблем обуставе проценом Спикер секвенце.
  • Квантномеханички систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-израчунљиву функцију.[41] То није могуће користећи стандардни кјубит-модел квантног компјутера, јер је доказано да редовни квантни компјутер PSPACE-умањен (квантни компјутер који ради у полиномијалном времену може да симулира класични компјутер који ради у простору полинома).[42]
  • 1970, Е. С. Сантос дефинисао је класу расплинуте логике засноване на "нејасном алгоритму" и "фази Тјурингове машине".[43] Након тога, Л. Биаћино и Г. Герла су показали да би таква дефиниција омогућавала прорачун нерекурзивних језика; они су предложили алтернативни скуп дефиниција без ове тешкоће.[44] Јири Видерман је анализирао могућности Сантосовог првобитног предлога 2004. године. [45]
  • Дмитро Тарановски је предложио финитистички модел традиционалне нефинитистичке гране анализе, изграђен око Тјурингове машине опремљен брзо растућом функцијом као своје пророчиште. Овај и компликованији модели су били је у стању да дају тумачење другог реда аритметике.[46]

Анализа могућности

Многи предлози хиперрачунања износе алтернативним начинима да прочитате Пророчку машину или савет функције уграђене у иначе класичне машине. Други омогућен приступ је могућ неком вишем нивоу аритметичке хијерархије. На пример, супертаскинг Тјурингове машине, под уобичајеним претпоставкама, да је у стању да израчуна било који предикат у степену истинитосне табеле која садржи  или . Рекурзивно-ограничавање, с друге стране, може да израчуна било који предикат или функцију у одговарајућој мери степена Тјуринга, који је познат да буде . Доста даље је показано да ограничавање делимичне рекурзију омогућава прорачун управо предикатима.

Модел Израчунљиви предикати Белешке Референце
супертаскинг tt() зависност на спољашњем посматрачу [47]
Ограничавање / проба и грешке [25]
итеративно лимитирање (k пута) [27]
Blum-Shub-Smale машина неупоредив са традиционалним израчунљивим реалним функцијама [48]
Маламент-Хогарт простор-време ХТ зависност на просторновременској структури [49]
аналогно повратна неуронска мреже f је савет функција давање тежина везе; величина је ограничена рантајмом [2][50]
бесконачно време Тјурингове машине [51]
класична фаза Тјурингове машине за било коју рачунљиву t-норму [45]
растућа функција Пророчке машине за једносеквентни модел; су r.e. [46]

Таксономија "супер-рекурзивне" методологије рачунања

Марк Бургин је прикупио списак онога што он назива "супер-рекурзивни алгоритми" (од Бургина 2005: 132):

  • ограничавање рекурзивне функције и ограничавање парцијалне рекурзивне функције (E. M. Голд[25])
  • проба и грешке предиката (Хилари Патнам [26])
  • индуктивно закључивање машина  (Карл Херберт Смит)
  • индуктивне Тјурингове машине (један од Бургинових модела)
  • ограничавање Тјурингових машина (један од других Бургинових модела)
  • проба и грешке машина (Ja. Хинтика и A. Мутанен [52])
  • генералне Тјурингове машине (J. Шмидхубер[40])
  • Интернет машине (Јан ван Леувен и Видерман,J.[38])
  • еволуционарни рачунари, које користе ДНК да произведу вредност функције (Дарко Роглић [53])
  • фазни прорачун (Јири Видерман [45])
  • еволуционарне Тјурингове машине (Еуген Ебербах [54])

У истој књизи, он такође представља списак "алгоритамских шема":

  • Статичке неуронске мреже засноване на стварним тежинама или еквивалентно "Неуронске мреже коначне прецизне тежине, али са асинхроним ажурирањем, стохастичке медаље, развијање или учење (тежине и / или структура). (Хава Сигелман)

Критика

Мартин Дејвис, у својим списима о хиперрачунању [56][57] односи се на овој теми као "мит" и нуди контра-аргументе за физички остваривостима хиперрачунања. Што се тиче његове теорије, тврди да је ово ново поље основано 1990. године. Ова тачка гледишта се ослања на историју теорије израчунљивости (степени нерешивости, израчунљивост над функцијама, реалних бројева и редних бројева), као и горе наведено. У свом аргументу он прави примедбу да је све тривијално као: "Ако је неизрачунљивим улазима дозвољено онда су неизрачунљиви резултати достижни". Широко је прихваћено да се ова критика односи на најраније математичке и филозофске сугестије и игнорише многе од новијих предлога који нису предмет критике.

Ендрју Хоџес је написао критички коментар [58] на Коупленд и Праудфут чланку.[6]

Види још

Референце

  1. ^ а б Hava Siegelmann (Oct 1993).
  2. ^ а б в H.T. Siegelmann (Apr 1995).
  3. ^ Mike Stannett, Super-Turing Computation.
  4. ^ Mike Stannett, An Introduction to post-Newtonian and super-Turing computation.
  5. ^ Mike Stannett, 1990, X-machines and the halting problem: Building a super-Turing machine Formal Aspects of Computing, Volume 2, Issue 1. pp. 331-441. http://link.springer.com/article/10.1007%2FBF01888233
  6. ^ а б Copeland & Proudfoot, Alan Turing's forgotten ideas in computer science.
  7. ^ Alan Turing, 1939, Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2–45, Issue 1. pp. 161–228.[1]
  8. ^ "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were.
  9. ^ а б H.T. Siegelmann, "Neural Networks and Analog Computation: Beyond the Turing Limit", Birkhauser, Boston, December 1998
  10. ^ H.T. Siegelmann and E.D. Sontag (1995).
  11. ^ H.T. Siegelmann and E.D. Sontag (1994).
  12. ^ J.L. Balcázar and R. Gavaldà and H.T. Siegelmann (Jul 1997).
  13. ^ J. Cabessa and H. T. Siegelmann (2014).
  14. ^ J. Cabessa and H.T. Siegelmann (Apr 2012).
  15. ^ J.P. Neto, H.T. Siegelmann, and J.F. Costa, “Implementation of Programming Languages with Neural Nets,” International Journal of Computing Anticipatory Systems 1, 1997: 201-208
  16. ^ J. Kilian and H.T. Siegelmann, “The Dynamic Universality of Sigmoidal Neural Networks,” Information and Computation 128(1), 1996: 45-56.
  17. ^ H.T. Siegelmann, B.G. Horne, and C.L.Giles, “Computational Capabilities of Recurrent NARX Neural Networks,” IEEE Transaction on Systems, Man and Cybernetics – part B: Cybernetics 27(2), 1997: 208-215.
  18. ^ 47.
  19. ^ H.T. Siegelmann, A. Ben-Hur and S. Fishman, “Computational Complexity for Continuous Time Dynamics,” Physical Review Letters, 83(7), 1999: 1463-1466.
  20. ^ H.T. Siegelmann and S. Fishman, “Computation by Dynamical Systems,” Physica D 120, 1998 (1-2): 214-235.
  21. ^ A. Ben-Hur, J. Feinberg, S. Fishman and H. T. Siegelmann, “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.
  22. ^ A. Ben-Hur, J. Feinberg, S. Fishman and H. T. Siegelmann, “Probabilistic analysis of a differential equation for linear programming,” Journal of Complexity 19(4), August 2003: 474-510.
  23. ^ H. T. Siegelmann, “Turing on Super-Turing and Adaptivity”.
  24. ^ These models have been independently developed by many different authors, including Hermann Weyl (1927).
  25. ^ а б в E. M. Gold (1965).
  26. ^ а б в Hilary Putnam (1965).
  27. ^ а б L. K. Schubert (July 1974).
  28. ^ Arnold Schönhage, "On the power of random access machines", in Proc.
  29. ^ Edith Spaan, Leen Torenvliet and Peter van Emde Boas (1989).
  30. ^ Hajnal Andréka, István Németi and Gergely Székely, Closed Timelike Curves in Relativistic Computation Parallel Process.
  31. ^ Todd A. Brun, Computers with closed timelike curves can solve hard problems, Found.
  32. ^ S. Aaronson and J. Watrous.
  33. ^ Hogarth, M., 1992, 'Does General Relativity Allow an Observer to View an Eternity in a Finite Time?'
  34. ^ István Neméti; Hajnal Andréka (2006).
  35. ^ Etesi, G., and Nemeti, I., 2002 'Non-Turing computations via Malament-Hogarth space-times', Int.
  36. ^ Earman, J. and Norton, J., 1993, 'Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes', Philosophy of Science, 5, 22–42.
  37. ^ Joel David Hamkins and Andy Lewis, Infinite time Turing machines, Journal of Symbolic Logic, 65(2):567-604, 2000.[2]
  38. ^ а б Jan van Leeuwen; Jiří Wiedermann (September 2000).
  39. ^ Jürgen Schmidhuber (2000).
  40. ^ а б J. Schmidhuber (2002).
  41. ^ There have been some claims to this effect; see Tien Kieu (2003).
  42. ^ Bernstein & Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [3]
  43. ^ Santos, Eugene S. (1970).
  44. ^ Biacino, L.; Gerla, G. (2002).
  45. ^ а б в Wiedermann, Jiří (2004).
  46. ^ а б Dmytro Taranovsky (July 17, 2005).
  47. ^ Potgieter, Petrus H. (јул 2006). „Zeno machines and hypercomputation”. Theoretical Computer Science. 358 (1): 23—33. doi:10.1016/j.tcs.2005.11.040. 
  48. ^ Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale. Complexity and Real Computation. ISBN 0-387-98281-7. 
  49. ^ P.D. Welch (10 Sep 2006). „The extent of computation in Malament-Hogarth spacetimes”. British J. for Philosophy of Science. 59: 659—674. arXiv:gr-qc/0609035 Слободан приступ.  Проверите вредност парамет(а)ра за датум: |year= / |date= mismatch (помоћ)
  50. ^ Hava Siegelmann; Sontag, Eduardo (1994). „Analog Computation via Neural Networks”. Theoretical Computer Science. 131 (2): 331—360. doi:10.1016/0304-3975(94)90178-3. 
  51. ^ Joel David Hamkins; Lewis, Andy (2000). „Infinite Time Turing machines”. Journal of Symbolic Logic. 65 (2): 567—604. doi:10.2307/2586556. 
  52. ^ Hintikka, Ja; Mutanen, A. (1998).
  53. ^ Darko Roglic (24 Jul 2007).
  54. ^ Eugene Eberbach (2002).
  55. ^ Borodyanskii, Yu M; Burgin, M. S. (1994).
  56. ^ Davis, Martin (2006).
  57. ^ Davis 2004
  58. ^ Andrew Hodges.

Додатна литература

Спољашњи линкови

Преузето из „https://sr.wikipedia.org/w/index.php?title=Хиперрачунање&oldid=11600027”