Хиперрачунање — разлика између измена
Alter: doi. Add: s2cid, pages, volume, journal, date, title, authors 1-1. | Use this tool. Report bugs. | #UCB_Gadget ознака: враћена измена |
грешке ознаке: ручно враћање враћена измена |
||
Ред 1: | Ред 1: | ||
'''Хиперрачунање''' или '''супер-Тјурингово рачунање''' се односи на моделе рачунања који превазилазе Тјурингову израчунљивост. Ово укључује различите хипотетичке методе за [[Рачунање|израчунавање]] не-[[Израчунљива функција|Тјурингове-израчунљиве функције]]. |
'''Хиперрачунање''' или '''супер-Тјурингово рачунање''' се односи на моделе рачунања који превазилазе Тјурингову израчунљивост. Ово укључује различите хипотетичке методе за [[Рачунање|израчунавање]] не-[[Израчунљива функција|Тјурингове-израчунљиве функције]]. |
||
Термин " супер-Тјурингово рачунање" појавио се почетком 1990-их, са најмање два независна извора наведена у литератури. Појавио се у разговорима, PhD тезе,<ref name="Siegelmann.1993"><cite class="citation thesis">Hava Siegelmann (Oct 1993). </cite></ref> па чак и ранији технички извештаји [[Хава Сигелман|Хаве Сигелмана]] од раних 1990-их за веома посебну теорију (описану у наставку) и постао је подобласт израчунавања од њеног [[Сајенс (магазин)|научног]] папира 1995.<ref name="Siegelmann.1995"> |
Термин " супер-Тјурингово рачунање" појавио се почетком 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. стр. 331-441. http://link.springer.com/article/10.1007%2FBF01888233</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] {{Wayback|url=http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 |date=20131111194007 }}''.</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] {{Wayback|url=http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 |date=20131111194007 }}''.</ref> |
||
Ред 16: | Ред 16: | ||
== Супер-Тјурингово рачунање и супер-Тјурингова теза == |
== Супер-Тјурингово рачунање и супер-Тјурингова теза == |
||
У раним 1990-им [[Хава Сигелман]] и [[Едуардо Сонтаг]] су доказали да је њихов нови компјутерски модел, Вештачка Рекурентна Природна Мрежа (''ARNN''), могла да обавља изван Тјурингове границе (хиперрачунање)<ref> |
У раним 1990-им [[Хава Сигелман]] и [[Едуардо Сонтаг]] су доказали да је њихов нови компјутерски модел, Вештачка Рекурентна Природна Мрежа (''ARNN''), могла да обавља изван Тјурингове границе (хиперрачунање)<ref><cite class="citation journal">H.T. Siegelmann and E.D. Sontag (1995). </cite></ref><ref><cite class="citation journal">H.T. Siegelmann and E.D. Sontag (1994). </cite></ref> |
||
Сигелман и њене колеге су открили хијерархију добро утврђених рачунарских класа које почињу од Тјурингове машине и уздижу се до пуне супер Тјурингове снаге <ref> |
Сигелман и њене колеге су открили хијерархију добро утврђених рачунарских класа које почињу од Тјурингове машине и уздижу се до пуне супер Тјурингове снаге <ref><cite class="citation journal">J.L. Balcázar and R. Gavaldà and H.T. Siegelmann (Jul 1997). </cite></ref> Сигелман је описала у разним публикацијама које постоје много начини да се дође до супер-Тјуринговог рачунања. Док је прво показала постојање супер-Тјуринговог рачунања преко аналогне неуронске мреже са фиксном (не за учење) и неограниченом тежином, отишла је да доказује супер-Тјурингову снагу у многим различитим остваривим машинама укључујући и мале прецизне тежине неуронске мреже које примају своју моћ од: учења у аналогном домену, или користећи стокастику,<ref name="Siegelmann.1998" /> или развијање током времена,<ref><cite class="citation journal">J. Cabessa and H. T. Siegelmann (2014). </cite></ref> или коришћење података из окружења, или система који су Тјурингови у било којим израчунљивим корацима и између промена на једну од наведених метода. Види још рад у [[Верификација својстава неуронских мрежа|Верификацији својстава неуронских мрежа]]. |
||
Сигелманин научни рад показује први корак ослобађања овог рачунања<ref name="Siegelmann.1995" /> док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања <math>2^{\aleph_0}</math> а простор Тјурингових машина само [[Алеф број|<math>\aleph_0</math>]], што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина. <ref> |
Сигелманин научни рад показује први корак ослобађања овог рачунања<ref name="Siegelmann.1995" /> док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања <math>2^{\aleph_0}</math> а простор Тјурингових машина само [[Алеф број|<math>\aleph_0</math>]], што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина. <ref><cite class="citation journal">J. Cabessa and H.T. Siegelmann (Apr 2012). </cite></ref> |
||
Теорија је довела до бољег разумевања неуронске мреже (Фондација [[Дубоко учење|дубоког учења]]) и подржаних иновативних апликација у тако осетљивим областима као што су регистрације радара и контрола нуклеарних електрана. |
Теорија је довела до бољег разумевања неуронске мреже (Фондација [[Дубоко учење|дубоког учења]]) и подржаних иновативних апликација у тако осетљивим областима као што су регистрације радара и контрола нуклеарних електрана. |
||
<ref>J.P. Neto, H.T. Siegelmann, and J.F. Costa, |
<ref>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</ref> |
||
<ref>J. Kilian and H.T. Siegelmann, |
<ref>J. Kilian and H.T. Siegelmann, “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, |
<ref>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.</ref> |
||
<ref>47. </ref> |
<ref>47. </ref> |
||
Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе.<ref>H.T. Siegelmann, A. Ben-Hur and S. Fishman, |
Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе.<ref>H.T. Siegelmann, A. Ben-Hur and S. Fishman, “Computational Complexity for Continuous Time Dynamics,” Physical Review Letters, 83(7), 1999: 1463-1466.</ref><ref>H.T. Siegelmann and S. Fishman, “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 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, |
<ref>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.</ref> |
||
Недавна публикација открива да је Алан Тјуринг био у потрази за супер-Тјуринговим израчунавањем заснованим на принципима мозга, и показао своје предложене правце како се траже да се савршено слажу са Сигелманим теоријама. |
Недавна публикација открива да је Алан Тјуринг био у потрази за супер-Тјуринговим израчунавањем заснованим на принципима мозга, и показао своје предложене правце како се траже да се савршено слажу са Сигелманим теоријама. |
||
<ref>H. T. Siegelmann, |
<ref>H. T. Siegelmann, “Turing on Super-Turing and Adaptivity”.</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 [[Херман Вајл|Hermann Weyl]] (1927).</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 [[Херман Вајл|Hermann Weyl]] (1927).</ref> |
||
* Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939. |
* Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939. |
||
* Средином 1960-их, [[Е Марк Голд]] и [[Хилари Патнам]] независно су предложили моделе [[Индукција (логика)|индуктивног закључивања]] (на "ограничавање рекурзивних функционалности"<ref name="LimRecurs"> |
* Средином 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" /> [[Л. К. Шуберт]]ов папир 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> |
* Предложена техника позната као [[Неограничена недетерминисана|фер недетерминисана]] или [[неограничена недетерминисана]] може дозволити израчунавања неизрачунљивих функција.<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>István Neméti; Hajnal Andréka (2006).</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>István Neméti; Hajnal Andréka (2006).</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> |
* '''Бесконачно време Тјурингове машине''' је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним [[Редни број|редним бројевима]]. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање [[Лимит редног броја|лимита редног броја]] и којима су резултати претходно бесконачног израчунавања доступни.<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] {{Wayback|url=http://jdh.hamkins.org/Publications/2000e |date=20111005150801 }}</ref> |
||
* [[Јан ван Леувен]] и Јири Видерман су написали папир <ref name="InternetMachines">Jan van Leeuwen; Jiří Wiedermann (September 2000).</ref> сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен [[Савет (комплексност)|саветима]] функција које представљају способност рачунара да се надогради. |
* [[Јан ван Леувен]] и Јири Видерман су написали папир <ref name="InternetMachines">Jan van Leeuwen; Jiří Wiedermann (September 2000).</ref> сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен [[Савет (комплексност)|саветима]] функција које представљају способност рачунара да се надогради. |
||
* Симбол секвенце је ''израчунљив у року'' ако постоји коначан, вероватно незаустављив програм на [[Универзална Тјурингова машина|универзалној Тјуринговој машини]] која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други [[Израчунљив број|израчунљив реалан број]], али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао [[Јирген Шмидхубер]], може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио [[Курт Гедел]] (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе [[Халтинг проблем|заустављање проблема]] би могло бити решено. Шмидхубер (<ref name="genTuring2000"> |
* Симбол секвенце је ''израчунљив у року'' ако постоји коначан, вероватно незаустављив програм на [[Универзална Тјурингова машина|универзалној Тјуринговој машини]] која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други [[Израчунљив број|израчунљив реалан број]], али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао [[Јирген Шмидхубер]], може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио [[Курт Гедел]] (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> |
* [[Квантна механика|Квантномеханички]] систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-[[Израчунљива функција|израчунљиву функцију]].<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> |
* 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> |
||
Ред 75: | Ред 75: | ||
| |
| |
||
| неупоредив са традиционалним [[Израчунљив број|израчунљивим реалним]] функцијама |
| неупоредив са традиционалним [[Израчунљив број|израчунљивим реалним]] функцијама |
||
| <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= |
| <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=}}</ref> |
||
|- |
|- |
||
| [[Маламент-Хогарт простор-време]] |
| [[Маламент-Хогарт простор-време]] |
||
Ред 116: | Ред 116: | ||
* '''еволуционарни рачунари, које користе ДНК да произведу вредност функције''' (Дарко Роглић <ref><cite class="citation arxiv">Darko Roglic (24 Jul 2007). </cite></ref>) |
* '''еволуционарни рачунари, које користе ДНК да произведу вредност функције''' (Дарко Роглић <ref><cite class="citation arxiv">Darko Roglic (24 Jul 2007). </cite></ref>) |
||
* '''фазни прорачун''' (Јири Видерман <ref name="ClassicalFuzzy" />) |
* '''фазни прорачун''' (Јири Видерман <ref name="ClassicalFuzzy" />) |
||
* '''еволуционарне Тјурингове машине''' (Еуген Ебербах <ref> |
* '''еволуционарне Тјурингове машине''' (Еуген Ебербах <ref><cite class="citation journal">Eugene Eberbach (2002). </cite></ref>) |
||
У истој књизи, он такође представља списак "алгоритамских шема": |
У истој књизи, он такође представља списак "алгоритамских шема": |
||
* '''Тјурингове машине са произвољним''' [[Пророчка машина|Пророчким машинама]] (Алан Тјуринг) |
* '''Тјурингове машине са произвољним''' [[Пророчка машина|Пророчким машинама]] (Алан Тјуринг) |
||
* '''трансрекурзивни оператори''' (Бородиански и Бургин <ref> |
* '''трансрекурзивни оператори''' (Бородиански и Бургин <ref><cite class="citation journal">Borodyanskii, Yu M; Burgin, M. S. (1994). </cite></ref>) |
||
* [[Реално рачунање|машине које рачунају са реалним бројевима]] (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл) |
* [[Реално рачунање|машине које рачунају са реалним бројевима]] (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл) |
||
* '''Статичке неуронске мреже засноване на стварним тежинама''' или еквивалентно "Неуронске мреже коначне прецизне тежине, али са асинхроним ажурирањем, стохастичке медаље, развијање или учење (тежине и / или структура). (Хава Сигелман) |
* '''Статичке неуронске мреже засноване на стварним тежинама''' или еквивалентно "Неуронске мреже коначне прецизне тежине, али са асинхроним ажурирањем, стохастичке медаље, развијање или учење (тежине и / или структура). (Хава Сигелман) |
||
== Критика == |
== Критика == |
||
[[Мартин Дејвис]], у својим списима о хиперрачунању <ref name="Davis95"> |
[[Мартин Дејвис]], у својим списима о хиперрачунању <ref name="Davis95"><cite class="citation journal">Davis, Martin (2006). </cite></ref>{{sfn|Davis|2004|pp=}} односи се на овој теми као "мит" и нуди контра-аргументе за физички остваривостима хиперрачунања. Што се тиче његове теорије, тврди да је ово ново поље основано 1990. године. Ова тачка гледишта се ослања на историју теорије израчунљивости (степени нерешивости, израчунљивост над функцијама, реалних бројева и редних бројева), као и горе наведено. У свом аргументу он прави примедбу да је све тривијално као: "''Ако је неизрачунљивим улазима дозвољено онда су неизрачунљиви резултати достижни".'' Широко је прихваћено да се ова критика односи на најраније математичке и филозофске сугестије и игнорише многе од новијих предлога који нису предмет критике. |
||
[[Ендру Хоџес]] је написао критички коментар <ref name="HodgesSCIAM"><cite class="citation web">Andrew Hodges. </cite></ref> на Коупленд и Праудфут чланку.<ref name="CandP" /> |
[[Ендру Хоџес]] је написао критички коментар <ref name="HodgesSCIAM"><cite class="citation web">Andrew Hodges. </cite></ref> на Коупленд и Праудфут чланку.<ref name="CandP" /> |
||
Ред 143: | Ред 143: | ||
* Keith Douglas. ''[http://www.philosopher-animal.com/papers/take6c.PDF Super-Turing Computation: a Case Study Analysis]'' ([[PDF]]), M.S. Thesis, Carnegie Mellon University, 2003. |
* Keith Douglas. ''[http://www.philosopher-animal.com/papers/take6c.PDF Super-Turing Computation: a Case Study Analysis]'' ([[PDF]]), M.S. Thesis, Carnegie Mellon University, 2003. |
||
* L. Blum, F. Cucker, M. Shub, S. Smale, ''Complexity and Real Computation'', Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits. |
* L. Blum, F. Cucker, M. Shub, S. Smale, ''Complexity and Real Computation'', Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits. |
||
* |
* Toby Ord. [[arxiv:math/0209332|''Hypercomputation: Computing more than the Turing machine can compute'']]: A survey article on various forms of hypercomputation. |
||
* {{cite book|last=Syropoulos|first=Apostolos|title=Hypercomputation: Computing Beyond the Church-Turing Barrier|url=https://books.google.com/books?id=5gVOf_OQa04C|year=2008|publisher=Springer Science & Business Media|isbn=978-0-387-49970-3}} |
* {{cite book|last=Syropoulos|first=Apostolos|title=Hypercomputation: Computing Beyond the Church-Turing Barrier|url=https://books.google.com/books?id=5gVOf_OQa04C|year=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. стр. 1289–1293 |
* Burgin, M. S. (1983) Inductive Turing Machines, ''Notices of the Academy of Sciences of the USSR'', v. 270, No. 6. стр. 1289–1293 |
||
Ред 154: | Ред 154: | ||
* 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 |
||
* |
* Volkmar Putz and Karl Svozil, ''[[arxiv:1003.1238|Can a computer be "pushed" to perform faster-than-light?]]'', (2010) |
||
{{refend}} |
{{refend}} |
||
Ред 160: | Ред 160: | ||
* [http://www.hypercomputation.net/ Hypercomputation Research Network] |
* [http://www.hypercomputation.net/ Hypercomputation Research Network] |
||
* [http://www.hypercomputation.blogspot.com/ Hypercomputation] |
* [http://www.hypercomputation.blogspot.com/ Hypercomputation] |
||
* |
* [[arxiv:math/0209332|Toby Ord, ''Hypercomputation: computing more than the Turing machine'']] |
||
* [http://www.amirrorclear.net/academic/papers/many-forms.pdf Toby Ord, ''The many forms of hypercomputation''] |
* [http://www.amirrorclear.net/academic/papers/many-forms.pdf Toby Ord, ''The many forms of hypercomputation''] |
||
* [http://citeseer.ist.psu.edu/cotogno03hypercomputation.html Paolo Cotogno, ''Hypercomputation and the Physical Church-Turing thesis''] |
* [http://citeseer.ist.psu.edu/cotogno03hypercomputation.html Paolo Cotogno, ''Hypercomputation and the Physical Church-Turing thesis''] |
Верзија на датум 12. септембар 2023. у 19: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])
У истој књизи, он такође представља списак "алгоритамских шема":
- Тјурингове машине са произвољним Пророчким машинама (Алан Тјуринг)
- трансрекурзивни оператори (Бородиански и Бургин [55])
- машине које рачунају са реалним бројевима (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл)
- Статичке неуронске мреже засноване на стварним тежинама или еквивалентно "Неуронске мреже коначне прецизне тежине, али са асинхроним ажурирањем, стохастичке медаље, развијање или учење (тежине и / или структура). (Хава Сигелман)
Критика
Мартин Дејвис, у својим списима о хиперрачунању [56][57] односи се на овој теми као "мит" и нуди контра-аргументе за физички остваривостима хиперрачунања. Што се тиче његове теорије, тврди да је ово ново поље основано 1990. године. Ова тачка гледишта се ослања на историју теорије израчунљивости (степени нерешивости, израчунљивост над функцијама, реалних бројева и редних бројева), као и горе наведено. У свом аргументу он прави примедбу да је све тривијално као: "Ако је неизрачунљивим улазима дозвољено онда су неизрачунљиви резултати достижни". Широко је прихваћено да се ова критика односи на најраније математичке и филозофске сугестије и игнорише многе од новијих предлога који нису предмет критике.
Ендру Хоџес је написао критички коментар [58] на Коупленд и Праудфут чланку.[6]
Види још
Референце
- ^ а б Hava Siegelmann (Oct 1993).
- ^ а б в H.T. Siegelmann (Apr 1995).
- ^ Mike Stannett, Super-Turing Computation.
- ^ Mike Stannett, An Introduction to post-Newtonian and super-Turing computation.
- ^ Mike Stannett, 1990, X-machines and the halting problem: Building a super-Turing machine Formal Aspects of Computing, Volume 2, Issue 1. стр. 331-441. http://link.springer.com/article/10.1007%2FBF01888233
- ^ а б Copeland & Proudfoot, Alan Turing's forgotten ideas in computer science Архивирано на сајту Wayback Machine (11. новембар 2013).
- ^ Alan Turing, 1939, Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2–45, Issue 1. стр. 161–228.[1]
- ^ "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were.
- ^ а б H.T. Siegelmann, "Neural Networks and Analog Computation: Beyond the Turing Limit", Birkhauser, Boston, December 1998
- ^ H.T. Siegelmann and E.D. Sontag (1995).
- ^ H.T. Siegelmann and E.D. Sontag (1994).
- ^ J.L. Balcázar and R. Gavaldà and H.T. Siegelmann (Jul 1997).
- ^ J. Cabessa and H. T. Siegelmann (2014).
- ^ J. Cabessa and H.T. Siegelmann (Apr 2012).
- ^ 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
- ^ J. Kilian and H.T. Siegelmann, “The Dynamic Universality of Sigmoidal Neural Networks,” Information and Computation 128(1), 1996: 45-56.
- ^ 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.
- ^ 47.
- ^ H.T. Siegelmann, A. Ben-Hur and S. Fishman, “Computational Complexity for Continuous Time Dynamics,” Physical Review Letters, 83(7), 1999: 1463-1466.
- ^ H.T. Siegelmann and S. Fishman, “Computation by Dynamical Systems,” Physica D 120, 1998 (1-2): 214-235.
- ^ 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.
- ^ 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.
- ^ H. T. Siegelmann, “Turing on Super-Turing and Adaptivity”.
- ^ These models have been independently developed by many different authors, including Hermann Weyl (1927).
- ^ а б в E. M. Gold (1965).
- ^ а б в Hilary Putnam (1965).
- ^ а б L. K. Schubert (July 1974).
- ^ Arnold Schönhage, "On the power of random access machines", in Proc.
- ^ Edith Spaan, Leen Torenvliet and Peter van Emde Boas (1989).
- ^ Hajnal Andréka, István Németi and Gergely Székely, Closed Timelike Curves in Relativistic Computation Parallel Process.
- ^ Todd A. Brun, Computers with closed timelike curves can solve hard problems, Found.
- ^ S. Aaronson and J. Watrous.
- ^ Hogarth, M., 1992, 'Does General Relativity Allow an Observer to View an Eternity in a Finite Time?'
- ^ István Neméti; Hajnal Andréka (2006).
- ^ Etesi, G., and Nemeti, I., 2002 'Non-Turing computations via Malament-Hogarth space-times', Int.
- ^ Earman, J. and Norton, J., 1993, 'Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes', Philosophy of Science, 5, 22–42.
- ^ Joel David Hamkins and Andy Lewis, Infinite time Turing machines, Journal of Symbolic Logic, 65(2):567-604, 2000.[2] Архивирано на сајту Wayback Machine (5. октобар 2011)
- ^ а б Jan van Leeuwen; Jiří Wiedermann (September 2000).
- ^ Jürgen Schmidhuber (2000).
- ^ а б J. Schmidhuber (2002).
- ^ There have been some claims to this effect; see Tien Kieu (2003).
- ^ Bernstein & Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [3]
- ^ Santos, Eugene S. (1970).
- ^ Biacino, L.; Gerla, G. (2002).
- ^ а б в Wiedermann, Jiří (2004).
- ^ а б Dmytro Taranovsky (July 17, 2005).
- ^ Potgieter, Petrus H. (2006). „Zeno machines and hypercomputation”. Theoretical Computer Science. 358 (1): 23—33. S2CID 6749770. arXiv:cs/0412022
. doi:10.1016/j.tcs.2005.11.040.
- ^ Lenore Blum; Cucker, Felipe; Shub, Michael; Smale, Stephen (1998). Complexity and Real Computation. ISBN 978-0-387-98281-6.
- ^ P.D. Welch (10. 9. 2006). „The extent of computation in Malament-Hogarth spacetimes”. British J. For Philosophy of Science. 59 (4): 659—674. arXiv:gr-qc/0609035
. doi:10.1093/bjps/axn031. Проверите вредност парамет(а)ра за датум:
|year= / |date= mismatch
(помоћ) - ^ Siegelmann, Hava; Sontag, Eduardo (1994). „Analog Computation via Neural Networks”. Theoretical Computer Science. 131 (2): 331—360. doi:10.1016/0304-3975(94)90178-3.
- ^ Joel David Hamkins; Lewis, Andy (2000). „Infinite Time Turing machines”. Journal of Symbolic Logic. 65 (2): 567—604. JSTOR 2586556. arXiv:math/9808093
. doi:10.2307/2586556. Архивирано из оригинала 05. 10. 2011. г. Приступљено 15. 01. 2016.
- ^ Hintikka, Ja; Mutanen, A. (1998).
- ^ Darko Roglic (24 Jul 2007).
- ^ Eugene Eberbach (2002).
- ^ Borodyanskii, Yu M; Burgin, M. S. (1994).
- ^ Davis, Martin (2006).
- ^ Davis 2004.
- ^ Andrew Hodges.
Литература
- Stannett, Mike (1990). „X-machines and the halting problem: Building a super-turing machine”. Formal Aspects of Computing. 2 (1): 331—341. S2CID 7406983. doi:10.1007/BF01888233.
- Turing, A. M. (1939). „Systems of Logic Based on Ordinals†”. Proceedings of the London Mathematical Society: 161—228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
- Mike Stannett, The case for hypercomputation Архивирано на сајту Wayback Machine (4. март 2016), Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8–24, Special Issue on Hypercomputation
- Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
- Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
- Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church-Turing Barrier. 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. стр. 1289–1293
- Burgin, Mark (2005). Super-recursive algorithms. Springer. ISBN 978-0-387-95569-8.
- Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
- Cooper, S. Barry (2006). „Definability as hypercomputational effect”. Applied Mathematics and Computation. 178: 72—82. S2CID 1487739. doi:10.1016/j.amc.2005.09.072.
- Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper and S. S. Goncharov. Computability and Models: Perspectives East and West (PDF). Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. стр. 137–160.
- Copeland, J. (2002). Hypercomputation (PDF). Minds and machines, v. Архивирано из оригинала (PDF) 14. 03. 2016. г. Приступљено 15. 01. 2016. 12. стр. 461–502..
- Martin Davis (2006), "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. 125–132
- Hagar, A. and Korolev, A., Quantum Hypercomputation—Hype or Computation?, (2007)
- Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts
- Volkmar Putz and Karl Svozil, Can a computer be "pushed" to perform faster-than-light?, (2010)
Спољашње везе
- Hypercomputation Research Network
- Hypercomputation
- Toby Ord, Hypercomputation: computing more than the Turing machine
- Toby Ord, The many forms of hypercomputation
- Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis
- Gualtiero Piccinini, Computation in Physical Systems
- H.T. Siegelmann's publications page at University of Massachusetts Amherst