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

С Википедије, слободне енциклопедије
Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м ciscenje
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке; козметичке измене
Ред 2: Ред 2:
'''Хиперрачунање''' или '''супер-Тјурингово рачунање''' се односи на моделе рачунања који превазилазе Турингову израчунљивост. Ово укључује различите хипотетичке методе за [[Рачунање|израчунавање]] не-[[Израчунљива функција|Тјурингове-израчунљиве функције]].
'''Хиперрачунање''' или '''супер-Тјурингово рачунање''' се односи на моделе рачунања који превазилазе Турингову израчунљивост. Ово укључује различите хипотетичке методе за [[Рачунање|израчунавање]] не-[[Израчунљива функција|Тјурингове-израчунљиве функције]].


Термин " супер-Тјурингово рачунање" појавио се почетком 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">H.T. Siegelmann (Apr 1995). </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>Mike Stannett, 1990, ''[http://link.springer.com/article/10.1007%2FBF01888233 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</ref>
Термин " супер-Тјурингово рачунање" појавио се почетком 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">H.T. Siegelmann (Apr 1995). </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>Mike Stannett, 1990, ''[http://link.springer.com/article/10.1007%2FBF01888233 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</ref>


Термин "хиперрачунање" уведен је у 1999. од стране [[Џек Копленд|Џека Копленда]] и [[Дајана Праудфут|Дајане Праудфут]].<ref name="CandP">Copeland and Proudfoot, ''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science]''. </ref>
Термин "хиперрачунање" уведен је у 1999. од стране [[Џек Копленд|Џека Копленда]] и [[Дајана Праудфут|Дајане Праудфут]].<ref name="CandP">Copeland & Proudfoot, ''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science]''.</ref>


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


== Историја ==
== Историја ==
Математички модел који иде преко Тјурингових машина је увео [[Алан Тјуринг]] 1938. у својој докторској дисертацији ''[[Системи логике базирани на ординалима]]''.<ref>Alan Turing, 1939, ''Systems of Logic Based on Ordinals'' Proceedings London Mathematical Society Volumes 2–45, Issue 1, pp. 161–228.[http://plms.oxfordjournals.org/content/s2-45/1/161.extract]</ref> Овај рад је истраживао математичке системе у којима је [[пророчка машина]] била доступна, што би могло да израчуна једну произвољну (не) рекурзивну функцију из [[Природан број|природних бројева]] у природне бројеве. Он је користио овај уређај да докаже да чак и у оним моћнијим системима, [[неодлучив задатак]] је и даље присутан. Тјурингове пророчке машине су математичке апстракције, а нису физички оствариве.<ref>"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. </ref>
Математички модел који иде преко Тјурингових машина је увео [[Алан Тјуринг]] 1938. у својој докторској дисертацији ''[[Системи логике базирани на ординалима]]''.<ref>Alan Turing, 1939, ''Systems of Logic Based on Ordinals'' Proceedings London Mathematical Society Volumes 2–45, Issue 1. pp. 161–228.[http://plms.oxfordjournals.org/content/s2-45/1/161.extract]</ref> Овај рад је истраживао математичке системе у којима је [[пророчка машина]] била доступна, што би могло да израчуна једну произвољну (не) рекурзивну функцију из [[Природан број|природних бројева]] у природне бројеве. Он је користио овај уређај да докаже да чак и у оним моћнијим системима, [[неодлучив задатак]] је и даље присутан. Тјурингове пророчке машине су математичке апстракције, а нису физички оствариве.<ref>"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were.</ref>


== Хиперрачунање и Черч–Тјурингова теза ==
== Хиперрачунање и Черч–Тјурингова теза ==
Ред 32: Ред 32:


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


== Остали предлози супер-рачунара ==
== Остали предлози супер-рачунара ==
* Тјурингова машина која може да заврши бесконачно много корака. Једноставно бити у стању да ради за неограничен број корака није довољно. Један математички модел је [[Зенонова машина|Зенонoва машина]] (инспирисано [[Zenonovi paradoksi|Зеноновим парадоксима]]).Зенонова машина обавља свој први корак у израчунавању (рецимо) 1 минут, други корак у ½ минут, трећи корак у ¼ минут, итд Сумирајући [[1/2 + 1/4 + 1/8 + 1/16 + ⋯|1+½+¼+...]] (геометријска серија) видимо да машина обавља бесконачно много корака у укупно 2 минута. Према Шагриру, Зенонове машине уводе физичке парадоксе, а њихово стање је логично дефинисано ван једне стране отвореног периода [0, 2), тако недефинисана тачно у 2 минута после почетка рачунања.<ref>These models have been independently developed by many different authors, including <cite class="citation book">[[Херман Вајл|Hermann Weyl]] (1927). </cite></ref>
* Тјурингова машина која може да заврши бесконачно много корака. Једноставно бити у стању да ради за неограничен број корака није довољно. Један математички модел је [[Зенонова машина]] (инспирисано [[Zenonovi paradoksi|Зеноновим парадоксима]]).Зенонова машина обавља свој први корак у израчунавању (рецимо) 1 минут, други корак у ½ минут, трећи корак у ¼ минут, итд Сумирајући [[1/2 + 1/4 + 1/8 + 1/16 + ⋯|1+½+¼+...]] (геометријска серија) видимо да машина обавља бесконачно много корака у укупно 2 минута. Према Шагриру, Зенонове машине уводе физичке парадоксе, а њихово стање је логично дефинисано ван једне стране отвореног периода [0, 2), тако недефинисана тачно у 2 минута после почетка рачунања.<ref>These models have been independently developed by many different authors, including <cite class="citation book">[[Херман Вајл|Hermann Weyl]] (1927). </cite></ref>
* Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939.
* Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939.
* Средином 1960-их, [[Е Марк Голд]] и [[Хилари Патнам]] независно су предложили моделе [[Индукција (логика)|индуктивног закључивања]] (на "ограничавање рекурзивних функционалности"<ref name="LimRecurs"><cite class="citation journal">E. M. Gold (1965). </cite></ref> и "суђење и грешке предиката",<ref name="TrialError"><cite class="citation journal">Hilary Putnam (1965). </cite></ref> ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све рекурзивно бројиве скупове језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)"<ref name="TrialError"><cite class="citation journal">Hilary Putnam (1965). </cite></ref> [[Л. К. Шуберт]]ов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања" <ref name="IterLimRec"><cite class="citation journal">L. K. Schubert (July 1974). </cite></ref> проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком [[Аритметичка хијерархија|аритметичком]] предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина."
* Средином 1960-их, [[Е Марк Голд]] и [[Хилари Патнам]] независно су предложили моделе [[Индукција (логика)|индуктивног закључивања]] (на "ограничавање рекурзивних функционалности"<ref name="LimRecurs"><cite class="citation journal">E. M. Gold (1965). </cite></ref> и "суђење и грешке предиката",<ref name="TrialError"><cite class="citation journal">Hilary Putnam (1965). </cite></ref> ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све рекурзивно бројиве скупове језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)"<ref name="TrialError"><cite class="citation journal">Hilary Putnam (1965). </cite></ref> [[Л. К. Шуберт]]ов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања" <ref name="IterLimRec"><cite class="citation journal">L. K. Schubert (July 1974). </cite></ref> проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком [[Аритметичка хијерархија|аритметичком]] предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина."
* [[Прави компјутер]] (нека врста идеализованог [[Аналогни рачунар|аналогног рачунара]]) може обављати хиперрачунање <ref>Arnold Schönhage, "On the power of random access machines", in ''Proc. ''</ref> ако физика признаје опште реалне променљиве (не само за [[Израчунљив број|израчунавање реалних бројева]]), а то су на неки начин "упрегнуте" за обрачун. Ово може захтевати доста бизарних закона физике (на пример, мерљива [[Fizičke konstante|физичка константа]] са пророчком вредношћу, као што су [[Чејтинова константа]]), те би у најмању руку захтевала способност да измери стварну-вредности физичке вредност произвољне прецизности и поред [[Термални шум|топлотне буке]] и [[Квантна механика|квантних]] ефеката.
* [[Прави компјутер]] (нека врста идеализованог [[Аналогни рачунар|аналогног рачунара]]) може обављати хиперрачунање <ref>Arnold Schönhage, "On the power of random access machines", in ''Proc. ''</ref> ако физика признаје опште реалне променљиве (не само за [[Израчунљив број|израчунавање реалних бројева]]), а то су на неки начин "упрегнуте" за обрачун. Ово може захтевати доста бизарних закона физике (на пример, мерљива [[Fizičke konstante|физичка константа]] са пророчком вредношћу, као што су [[Чејтинова константа]]), те би у најмању руку захтевала способност да измери стварну-вредности физичке вредност произвољне прецизности и поред [[Термални шум|топлотне буке]] и [[Квантна механика|квантних]] ефеката.
* Предложена техника позната као [[Неограничена недетерминисана|фер недетерминисана]] или [[неограничена недетерминисана]] може дозволити израчунавања неизрачунљивих функција.<ref><cite class="citation journal">Edith Spaan, Leen Torenvliet and Peter van Emde Boas (1989). </cite></ref> Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве".
* Предложена техника позната као [[Неограничена недетерминисана|фер недетерминисана]] или [[неограничена недетерминисана]] може дозволити израчунавања неизрачунљивих функција.<ref><cite class="citation journal">Edith Spaan, Leen Torenvliet and Peter van Emde Boas (1989). </cite></ref> Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве".
* Чини се да је природна могућност путовања кроз време (постојање [[Затворене временске криве|затворених временских кривих]] (''CTCs'') чини хиперрачунање могуће само по себи. Међутим, то није тако пошто ''CTC'' не даје (по себи) неограничену количину складишног капацитета која би бесконачно рачунање захтевала. Ипак, постоје време и простор у којима се ''CTC'' регион може користити за релативистичко хиперрачунање.<ref>Hajnal Andréka, István Németi and Gergely Székely, ''Closed Timelike Curves in Relativistic Computation'' Parallel Process. </ref> Приступ ''CTC'' може дозволити брзо решење [[PSPACE-комплетно|PSPACE-комплетних]] проблема, комплексност класе која, док је Тјуринг-одлучив, се генерално сматра рачунски сложеним.<ref>Todd A. Brun, ''Computers with closed timelike curves can solve hard problems'', Found.</ref><ref>S. Aaronson and J. Watrous. </ref>
* Чини се да је природна могућност путовања кроз време (постојање [[Затворене временске криве|затворених временских кривих]] (''CTCs'') чини хиперрачунање могуће само по себи. Међутим, то није тако пошто ''CTC'' не даје (по себи) неограничену количину складишног капацитета која би бесконачно рачунање захтевала. Ипак, постоје време и простор у којима се ''CTC'' регион може користити за релативистичко хиперрачунање.<ref>Hajnal Andréka, István Németi and Gergely Székely, ''Closed Timelike Curves in Relativistic Computation'' Parallel Process.</ref> Приступ ''CTC'' може дозволити брзо решење [[PSPACE-комплетно|PSPACE-комплетних]] проблема, комплексност класе која, док је Тјуринг-одлучив, се генерално сматра рачунски сложеним.<ref>Todd A. Brun, ''Computers with closed timelike curves can solve hard problems'', Found.</ref><ref>S. Aaronson and J. Watrous.</ref>
* Према 1992 папиру,<ref>Hogarth, M., 1992, 'Does General Relativity Allow an Observer to View an Eternity in a Finite Time?'</ref> рачунар који ради на [[Маламент-Хогарт простор и време|Маламент-Хогарт простору и времену]] или у орбити око ротирајуће [[црне рупе]] <ref><cite class="citation book">István Neméti; Hajnal Andréka (2006). </cite></ref> теоретски се може обављати без Тјуринговог израчунавања.<ref>Etesi, G., and Nemeti, I., 2002 'Non-Turing computations via Malament-Hogarth space-times', Int.</ref><ref>Earman, J. and Norton, J., 1993, 'Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes', Philosophy of Science, 5, 22–42.</ref>
* Према 1992 папиру,<ref>Hogarth, M., 1992, 'Does General Relativity Allow an Observer to View an Eternity in a Finite Time?'</ref> рачунар који ради на [[Маламент-Хогарт простор и време|Маламент-Хогарт простору и времену]] или у орбити око ротирајуће [[црне рупе]] <ref><cite class="citation book">István Neméti; Hajnal Andréka (2006). </cite></ref> теоретски се може обављати без Тјуринговог израчунавања.<ref>Etesi, G., and Nemeti, I., 2002 'Non-Turing computations via Malament-Hogarth space-times', Int.</ref><ref>Earman, J. and Norton, J., 1993, 'Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes', Philosophy of Science, 5, 22–42.</ref>
* '''Бесконачно време Тјурингове машине''' је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним [[Редни број|редним бројевима]]. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање [[Лимит редног броја|лимита редног броја]] и којима су резултати претходно бесконачног израчунавања доступни.<ref>Joel David Hamkins and Andy Lewis, Infinite time Turing machines, ''Journal of Symbolic Logic'', 65(2):567-604, 2000.[http://jdh.hamkins.org/Publications/2000e]</ref>
* '''Бесконачно време Тјурингове машине''' је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним [[Редни број|редним бројевима]]. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање [[Лимит редног броја|лимита редног броја]] и којима су резултати претходно бесконачног израчунавања доступни.<ref>Joel David Hamkins and Andy Lewis, Infinite time Turing machines, ''Journal of Symbolic Logic'', 65(2):567-604, 2000.[http://jdh.hamkins.org/Publications/2000e]</ref>
* [[Јан ван Леувен]] и Јири Видерман су написали папир <ref name="InternetMachines"><cite class="citation book">Jan van Leeuwen; Jiří Wiedermann (September 2000). </cite></ref> сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен [[Савет (комплексност)|саветима]] функција које представљају способност рачунара да се надогради.
* [[Јан ван Леувен]] и Јири Видерман су написали папир <ref name="InternetMachines"><cite class="citation book">Jan van Leeuwen; Jiří Wiedermann (September 2000). </cite></ref> сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен [[Савет (комплексност)|саветима]] функција које представљају способност рачунара да се надогради.
* Симбол секвенце је ''израчунљив у року'' ако постоји коначан, вероватно незаустављив програм на [[Универзална Тјурингова машина|универзалној Тјуринговој машини]] која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други [[Израчунљив број|израчунљив реалан број]], али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао [[Јирген Шмидхубер]], може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио [[Курт Гедел]] (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе [[Халтинг проблем|заустављање проблема]] би могло бити решено. Шмидхубер (<ref name="genTuring2000"><cite class="citation journal">Jürgen Schmidhuber (2000). </cite></ref><ref name="GenKolm"><cite class="citation journal">J. Schmidhuber (2002). </cite></ref>) користи овај приступ да дефинише скуп формално описивих или конструктивно израчунљивих универзума или конструктивне [[Теорија свега|теорије свега]]. Генерализоване Тјурингове машине могу да реше проблем обуставе проценом [[Спикер секвенца|Спикер секвенце]].
* Симбол секвенце је ''израчунљив у року'' ако постоји коначан, вероватно незаустављив програм на [[Универзална Тјурингова машина|универзалној Тјуринговој машини]] која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други [[Израчунљив број|израчунљив реалан број]], али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао [[Јирген Шмидхубер]], може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио [[Курт Гедел]] (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе [[Халтинг проблем|заустављање проблема]] би могло бити решено. Шмидхубер (<ref name="genTuring2000"><cite class="citation journal">Jürgen Schmidhuber (2000). </cite></ref><ref name="GenKolm"><cite class="citation journal">J. Schmidhuber (2002). </cite></ref>) користи овај приступ да дефинише скуп формално описивих или конструктивно израчунљивих универзума или конструктивне [[Теорија свега|теорије свега]]. Генерализоване Тјурингове машине могу да реше проблем обуставе проценом [[Спикер секвенца|Спикер секвенце]].
* [[Квантна механика|Квантномеханички]] систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-[[Израчунљива функција|израчунљиву функцију]].<ref>There have been some claims to this effect; see <cite class="citation journal">Tien Kieu (2003). </cite></ref> То није могуће користећи стандардни [[кјубит]]-модел квантног компјутера, јер је доказано да редовни квантни компјутер [[PSPACE-умањен]] (квантни компјутер који ради у [[Субекспоненцијално време|полиномијалном времену]] може да симулира класични компјутер који ради у [[Простор полинома|простору полинома]]).<ref>Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [http://www.cs.berkeley.edu/~vazirani/bv.ps]</ref>
* [[Квантна механика|Квантномеханички]] систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-[[Израчунљива функција|израчунљиву функцију]].<ref>There have been some claims to this effect; see <cite class="citation journal">Tien Kieu (2003). </cite></ref> То није могуће користећи стандардни [[кјубит]]-модел квантног компјутера, јер је доказано да редовни квантни компјутер [[PSPACE-умањен]] (квантни компјутер који ради у [[Субекспоненцијално време|полиномијалном времену]] може да симулира класични компјутер који ради у [[Простор полинома|простору полинома]]).<ref>Bernstein & Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [http://www.cs.berkeley.edu/~vazirani/bv.ps]</ref>
* 1970, Е.С. Сантос дефинисао је класу [[Расплинута логика|расплинуте логике]] засноване на "нејасном алгоритму" и "фази Тјурингове машине".<ref><cite class="citation journal">Santos, Eugene S. (1970). </cite></ref> Након тога, Л. Биаћино и Г. Герла су показали да би таква дефиниција омогућавала прорачун нерекурзивних језика; они су предложили алтернативни скуп дефиниција без ове тешкоће.<ref><cite class="citation journal">Biacino, L.; Gerla, G. (2002). </cite></ref> Јири Видерман је анализирао могућности Сантосовог првобитног предлога 2004. године. <ref name="ClassicalFuzzy"><cite class="citation journal">Wiedermann, Jiří (2004). </cite></ref>
* 1970, Е.С. Сантос дефинисао је класу [[Расплинута логика|расплинуте логике]] засноване на "нејасном алгоритму" и "фази Тјурингове машине".<ref><cite class="citation journal">Santos, Eugene S. (1970). </cite></ref> Након тога, Л. Биаћино и Г. Герла су показали да би таква дефиниција омогућавала прорачун нерекурзивних језика; они су предложили алтернативни скуп дефиниција без ове тешкоће.<ref><cite class="citation journal">Biacino, L.; Gerla, G. (2002). </cite></ref> Јири Видерман је анализирао могућности Сантосовог првобитног предлога 2004. године. <ref name="ClassicalFuzzy"><cite class="citation journal">Wiedermann, Jiří (2004). </cite></ref>
* Дмитро Тарановски је предложио [[Финитизам|финитистички]] модел традиционалне нефинитистичке гране анализе, изграђен око Тјурингове машине опремљен брзо растућом функцијом као своје пророчиште. Овај и компликованији модели су били је у стању да дају тумачење другог реда аритметике.<ref name="Taranovsky"><cite class="citation web">Dmytro Taranovsky (July 17, 2005). </cite></ref>
* Дмитро Тарановски је предложио [[Финитизам|финитистички]] модел традиционалне нефинитистичке гране анализе, изграђен око Тјурингове машине опремљен брзо растућом функцијом као своје пророчиште. Овај и компликованији модели су били је у стању да дају тумачење другог реда аритметике.<ref name="Taranovsky"><cite class="citation web">Dmytro Taranovsky (July 17, 2005). </cite></ref>
Ред 62: Ред 62:
| tt(<math>\Sigma^0_1, \Pi^0_1</math>)
| tt(<math>\Sigma^0_1, \Pi^0_1</math>)
| зависност на спољашњем посматрачу
| зависност на спољашњем посматрачу
| <ref>{{cite journal| author=Petrus H. Potgieter| title=Zeno machines and hypercomputation| journal=Theoretical Computer Science| volume=358 | issue=1 |date=July 2006 | pages=23–33| doi=10.1016/j.tcs.2005.11.040}}</ref>
| <ref>{{cite journal|last=Potgieter|first=Petrus H.| title=Zeno machines and hypercomputation| journal=Theoretical Computer Science| volume=358 | issue=1 |date=July 2006 | doi=10.1016/j.tcs.2005.11.040|pages=23–33}}</ref>
|-
|-
| Ограничавање / проба и грешке
| Ограничавање / проба и грешке
Ред 77: Ред 77:
|
|
| неупоредив са традиционалним израчунљивим реалним функцијама
| неупоредив са традиционалним израчунљивим реалним функцијама
| <ref>{{cite book|author=[[Lenore Blum]], Felipe Cucker, Michael Shub, and [[Stephen Smale]]|title=Complexity and Real Computation|isbn=0-387-98281-7}}</ref>
| <ref>{{cite book|author=[[Lenore Blum]], Felipe Cucker, Michael Shub, and [[Stephen Smale]]|title=Complexity and Real Computation|id=ISBN 0-387-98281-7}}</ref>
|-
|-
| [[Маламент-Хогарт простор-време]]
| [[Маламент-Хогарт простор-време]]
| '''[[Хипераритметичка теорија|ХТ]]'''
| '''[[Хипераритметичка теорија|ХТ]]'''
| зависност на просторновременској структури
| зависност на просторновременској структури
| <ref>{{cite journal | author=[[P.D. Welch]] | title = The extent of computation in Malament-Hogarth spacetimes | date=10 Sep 2006 | arxiv=gr-qc/0609035 | journal=British J. for Philosophy of Science |volume=59 |year= 2009 | pages=659–674}}</ref>
| <ref>{{cite journal | author=[[P.D. Welch]] | title = The extent of computation in Malament-Hogarth spacetimes | date=10 Sep 2006 | arxiv=gr-qc/0609035 | journal=British J. for Philosophy of Science |volume=59 |year=2009|pages=659–674}}</ref>
|-
|-
|-
|-
Ред 88: Ред 88:
| <math> \Delta^0_1[f] </math>
| <math> \Delta^0_1[f] </math>
| ''f'' је савет функција давање тежина везе; величина је ограничена рантајмом
| ''f'' је савет функција давање тежина везе; величина је ограничена рантајмом
| <ref name="Siegelmann.1995"/><ref>{{cite journal | author=[[Hava Siegelmann]] | author2=Eduardo Sontag | title=Analog Computation via Neural Networks | journal=Theoretical Computer Science | volume=131 | year=1994 | pages=331–360 | doi=10.1016/0304-3975(94)90178-3 | issue=2 | authorlink2=Eduardo Sontag}}</ref>
| <ref name="Siegelmann.1995"/><ref>{{cite journal | author=[[Hava Siegelmann]] |last2=Sontag|first2=Eduardo| title=Analog Computation via Neural Networks | journal=Theoretical Computer Science | volume=131 |year=1994| doi=10.1016/0304-3975(94)90178-3 | issue=2 | authorlink2=Eduardo Sontag|pages=331–360}}</ref>
|-
|-
| бесконачно време Тјурингове машине
| бесконачно време Тјурингове машине
| <math> \ge T(\Sigma^1_1) </math>
| <math> \ge T(\Sigma^1_1) </math>
|
|
| <ref>{{cite journal|author=[[Joel David Hamkins]]|author2=Andy Lewis|title=Infinite Time Turing machines|journal=Journal of Symbolic Logic|year=2000|volume=65|issue=2|pages=567–604|url=http://jdh.hamkins.org/Publications/2000e|doi=10.2307/2586556}}</ref>
| <ref>{{cite journal|author=[[Joel David Hamkins]]|last2=Lewis|first2=Andy|title=Infinite Time Turing machines|journal=Journal of Symbolic Logic|year=2000|volume=65|issue=2|url=http://jdh.hamkins.org/Publications/2000e|doi=10.2307/2586556|pages=567–604}}</ref>
|-
|-
| класична фаза Тјурингове машине
| класична фаза Тјурингове машине
Ред 120: Ред 120:
* '''еволуционарне Тјурингове машине''' (Еуген Ебербах <ref><cite class="citation journal">Eugene Eberbach (2002). </cite></ref>)
* '''еволуционарне Тјурингове машине''' (Еуген Ебербах <ref><cite class="citation journal">Eugene Eberbach (2002). </cite></ref>)
У истој књизи, он такође представља списак "алгоритамских шема":
У истој књизи, он такође представља списак "алгоритамских шема":
* '''Тјурингове машине са произвољним''' [[Пророчка машина|Пророчким машинама]] (Алан Тјуринг)<br />
* '''Тјурингове машине са произвољним''' [[Пророчка машина|Пророчким машинама]] (Алан Тјуринг)

* '''трансрекурзивни оператори''' (Бородиански и Бургин <ref><cite class="citation journal">Borodyanskii, Yu M; Burgin, M. S. (1994). </cite></ref>)
* '''трансрекурзивни оператори''' (Бородиански и Бургин <ref><cite class="citation journal">Borodyanskii, Yu M; Burgin, M. S. (1994). </cite></ref>)
* [[Реално рачунање|машине које рачунају са реалним бројевима]] (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл)<br />
* [[Реално рачунање|машине које рачунају са реалним бројевима]] (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл)

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



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


[[Ендрју Хоџес]] је написао критички коментар <ref name="HodgesSCIAM"><cite class="citation web">Andrew Hodges. </cite></ref> на Коупленд и Праудфут чланку.<ref name="CandP">Copeland and Proudfoot, ''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science]''. </ref>
[[Ендрју Хоџес]] је написао критички коментар <ref name="HodgesSCIAM"><cite class="citation web">Andrew Hodges. </cite></ref> на Коупленд и Праудфут чланку.<ref name="CandP">Copeland & Proudfoot, ''[http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science]''.</ref>


== Види још ==
== Види још ==
Ред 134: Ред 137:
* [[Дигитална физика]]
* [[Дигитална физика]]


== References ==
== Референце ==
{{Reflist}}
{{reflist}}


== Додатна литература ==
== Додатна литература ==
Ред 145: Ред 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 (2008), ''[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. [[:en:Special:BookSources/9780387308869|ISBN 978-0-387-30886-9]]
* Apostolos Syropoulos (2008), ''[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=|isbn=978-0-387-30886-9|pages=}}
* Burgin, M. S. (1983) Inductive Turing Machines, ''Notices of the Academy of Sciences of the USSR'', v. 270, No. 6, pp.&nbsp;1289–1293
* Burgin, M. S. (1983) Inductive Turing Machines, ''Notices of the Academy of Sciences of the USSR'', v. 270, No. 6, ppp. 1289–1293
* Mark Burgin (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. [[:en:Special:BookSources/0387955690|ISBN 0-387-95569-0]]
* Mark Burgin (2005), ''Super-recursive algorithms'', Monographs in computer science, Springer. {{page|year=|id=ISBN 0-387-95569-0|pages=}}
* Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, ''The computer Journal'', 2007
* Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, ''The computer Journal'', 2007
* <cite class="citation journal">Cooper, S. B. (2006). [http://www.amsta.leeds.ac.uk/~pmt6sbc/preprints/hyp.comp.eff.pdf "Definability as hypercomputational effect"] (PDF). </cite><cite class="citation journal">''Applied Mathematics and Computation'' '''178''': 72–82. [[Digitalni identifikator objekta|doi]]:[[doi:10.1016/j.amc.2005.09.072|10.1016/j.amc.2005.09.072]].</cite>
* <cite class="citation journal">Cooper, S. B. (2006). [http://www.amsta.leeds.ac.uk/~pmt6sbc/preprints/hyp.comp.eff.pdf "Definability as hypercomputational effect"] (PDF). </cite><cite class="citation journal">''Applied Mathematics and Computation'' '''178''': 72–82. [[Digitalni identifikator objekta|doi]]:[[doi:10.1016/j.amc.2005.09.072|10.1016/j.amc.2005.09.072]].</cite>
* <cite class="citation book">Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper and S. S. Goncharov. [http://www.amsta.leeds.ac.uk/~pmt6sbc/preprints/co.pdf ''Computability and Models: Perspectives East and West''] (PDF). </cite><cite class="citation book">Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. pp.&nbsp;137–160.</cite>
* <cite class="citation book">Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper and S. S. Goncharov. [http://www.amsta.leeds.ac.uk/~pmt6sbc/preprints/co.pdf ''Computability and Models: Perspectives East and West''] (PDF). </cite><cite class="citation book">Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. ppp. 137–160.</cite>
* Copeland, J. (2002) ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_MINDS_AND_MACHINES/VOLUME_12_NO_4/NV6361035557Q678.pdf Hypercomputation]'', Minds and machines, v. 12, pp.&nbsp;461–502
* Copeland, J. (2002) ''[http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_MINDS_AND_MACHINES/VOLUME_12_NO_4/NV6361035557Q678.pdf Hypercomputation]'', Minds and machines, v. 12, ppp. 461–502
* Martin Davis (2006), "[http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. ''The requested URL /~simon/TEACH/28000/DavisUniversal.pdf was not found on this server.'' Lecture notes in computer science, 3988 pp.&nbsp;125–132
* Martin Davis (2006), "[http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. ''The requested URL /~simon/TEACH/28000/DavisUniversal.pdf was not found on this server.'' Lecture notes in computer science, 3988 ppp. 125–132
* Hagar, A. and Korolev, A., ''[http://philsci-archive.pitt.edu/archive/00003180/ Quantum Hypercomputation—Hype or Computation?]'', (2007)
* Hagar, A. and Korolev, A., ''[http://philsci-archive.pitt.edu/archive/00003180/ Quantum Hypercomputation—Hype or Computation?]'', (2007)
* Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts
* Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

Верзија на датум 16. јануар 2016. у 02:24

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

Термин " супер-Тјурингово рачунање" појавио се почетком 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=11550492”