Хиперрачунање

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

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

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

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

Историја

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

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

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

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

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

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

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

Сигелманин научни рад показује први корак ослобађања овог рачунања док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања $2^{\aleph _{0}}$ а простор Тјурингових машина само $\aleph _{0}$, што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина. 

Теорија је довела до бољег разумевања неуронске мреже (Фондација дубоког учења) и подржаних иновативних апликација у тако осетљивим областима као што су регистрације радара и контрола нуклеарних електрана. Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе. Као конкретан пример Сигелманова група је анализирала линеарно програмирање и друге компјутерско научне проблеме који показују да аналогни рачунари могу да реше брже од дискретних временских рачунара. 

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

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

• Тјурингова машина која може да заврши бесконачно много корака. Једноставно бити у стању да ради за неограничен број корака није довољно. Један математички модел је Зенонова машина (инспирисано Зеноновим парадоксима). Зенонова машина обавља свој први корак у израчунавању (рецимо) 1 минут, други корак у ½ минут, трећи корак у ¼ минут, итд Сумирајући 1+½+¼+... (геометријска серија) видимо да машина обавља бесконачно много корака у укупно 2 минута. Према Шагриру, Зенонове машине уводе физичке парадоксе, а њихово стање је логично дефинисано ван једне стране отвореног периода [0, 2), тако недефинисана тачно у 2 минута после почетка рачунања.
• Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939.
• Средином 1960-их, Е Марк Голд и Хилари Патнам независно су предложили моделе индуктивног закључивања (на "ограничавање рекурзивних функционалности" и "суђење и грешке предиката", ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све рекурзивно бројиве скупове језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)" Л. К. Шубертов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања"  проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком аритметичком предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина."
• Прави компјутер (нека врста идеализованог аналогног рачунара) може обављати хиперрачунање  ако физика признаје опште реалне променљиве (не само за израчунавање реалних бројева), а то су на неки начин "упрегнуте" за обрачун. Ово може захтевати доста бизарних закона физике (на пример, мерљива физичка константа са пророчком вредношћу, као што су Чејтинова константа), те би у најмању руку захтевала способност да измери стварну-вредности физичке вредност произвољне прецизности и поред топлотне буке и квантних ефеката.
• Предложена техника позната као фер недетерминисана или неограничена недетерминисана може дозволити израчунавања неизрачунљивих функција. Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве".
• Чини се да је природна могућност путовања кроз време (постојање затворених временских кривих (CTCs) чини хиперрачунање могуће само по себи. Међутим, то није тако пошто CTC не даје (по себи) неограничену количину складишног капацитета која би бесконачно рачунање захтевала. Ипак, постоје време и простор у којима се CTC регион може користити за релативистичко хиперрачунање. Приступ CTC може дозволити брзо решење PSPACE-комплетних проблема, комплексност класе која, док је Тјуринг-одлучив, се генерално сматра рачунски сложеним.
• Према 1992 папиру, рачунар који ради на Маламент-Хогарт простору и времену или у орбити око ротирајуће црне рупе  теоретски се може обављати без Тјуринговог израчунавања.
• Бесконачно време Тјурингове машине је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним редним бројевима. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање лимита редног броја и којима су резултати претходно бесконачног израчунавања доступни.
• Јан ван Леувен и Јири Видерман су написали папир  сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен саветима функција које представљају способност рачунара да се надогради.
• Симбол секвенце је израчунљив у року ако постоји коначан, вероватно незаустављив програм на универзалној Тјуринговој машини која постепено избацује сваки симбол секвенце. Ово укључује диадично ширење π и сваки други израчунљив реалан број, али ипак искључује све неизрачунљиве. Традиционална Тјурингова машина не може да мења своје раније излазе; генерализована Тјурингова машина, као што је дефинисао Јирген Шмидхубер, може. Он је конструктивно описао симболе секвенце као оне које имају коначан, незаустављив програм који ради на генерализованој Тјуринговој машини, тако да сваки излаз симбола на крају конвергира; то јест, не мења ништа више после неког коначног почетног временског интервала. Због ограничења први је изложио Курт Гедел (1931), да може бити немогуће предвидети само време конвергенције од заустављања програма, иначе заустављање проблема би могло бити решено. Шмидхубер () користи овај приступ да дефинише скуп формално описивих или конструктивно израчунљивих универзума или конструктивне теорије свега. Генерализоване Тјурингове машине могу да реше проблем обуставе проценом Спикер секвенце.
• Квантномеханички систем који на неки начин користи бесконачно суперпозиција стања да израчуна не-израчунљиву функцију. То није могуће користећи стандардни кјубит-модел квантног компјутера, јер је доказано да редовни квантни компјутер PSPACE-умањен (квантни компјутер који ради у полиномијалном времену може да симулира класични компјутер који ради у простору полинома).
• 1970, Е. С. Сантос дефинисао је класу расплинуте логике засноване на "нејасном алгоритму" и "фази Тјурингове машине". Након тога, Л. Биаћино и Г. Герла су показали да би таква дефиниција омогућавала прорачун нерекурзивних језика; они су предложили алтернативни скуп дефиниција без ове тешкоће. Јири Видерман је анализирао могућности Сантосовог првобитног предлога 2004. године. 
• Дмитро Тарановски је предложио финитистички модел традиционалне нефинитистичке гране анализе, изграђен око Тјурингове машине опремљен брзо растућом функцијом као своје пророчиште. Овај и компликованији модели су били је у стању да дају тумачење другог реда аритметике.

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

Многи предлози хиперрачунања износе алтернативним начинима да прочитате Пророчку машину или савет функције уграђене у иначе класичне машине. Други омогућен приступ је могућ неком вишем нивоу аритметичке хијерархије. На пример, супертаскинг Тјурингове машине, под уобичајеним претпоставкама, да је у стању да израчуна било који предикат у степену истинитосне табеле која садржи $\Sigma _{1}^{0}$ или $\Pi _{1}^{0}$. Рекурзивно-ограничавање, с друге стране, може да израчуна било који предикат или функцију у одговарајућој мери степена Тјуринга, који је познат да буде $\Delta _{2}^{0}$. Доста даље је показано да ограничавање делимичне рекурзију омогућава прорачун управо $\Sigma _{2}^{0}$предикатима.

Модел	Израчунљиви предикати	Белешке	Референце
супертаскинг	tt($\Sigma _{1}^{0},\Pi _{1}^{0}$)	зависност на спољашњем посматрачу
Ограничавање / проба и грешке	$\Delta _{2}^{0}$
итеративно лимитирање (k пута)	$\Delta _{k+1}^{0}$
Blum-Shub-Smale машина		неупоредив са традиционалним израчунљивим реалним функцијама
Маламент-Хогарт простор-време	ХТ	зависност на просторновременској структури
аналогно повратна неуронска мреже	$\Delta _{1}^{0}[f]$	f је савет функција давање тежина везе; величина је ограничена рантајмом
бесконачно време Тјурингове машине	$\geq T(\Sigma _{1}^{1})$
класична фаза Тјурингове машине	$\Sigma _{1}^{0}\cup \Pi _{1}^{0}$	за било коју рачунљиву t-норму
растућа функција Пророчке машине	$\Delta _{1}^{1}$	за једносеквентни модел; $\Pi _{1}^{1}$ су r.e.

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

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

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

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

• Тјурингове машине са произвољним Пророчким машинама (Алан Тјуринг)
• трансрекурзивни оператори (Бородиански и Бургин )
• машине које рачунају са реалним бројевима (Л. Блум, Ф Цуцкер М. Шуб, С. Смејл)
• Статичке неуронске мреже засноване на стварним тежинама или еквивалентно "Неуронске мреже коначне прецизне тежине, али са асинхроним ажурирањем, стохастичке медаље, развијање или учење (тежине и / или структура). (Хава Сигелман)

Критика

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

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

Види још

• Рачунање
• Дигитална физика
• Супер-задатак

Литература

• 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.
• Ord, Toby (2002). „Hypercomputation: Computing more than the Turing machine can compute”. arXiv:math/0209332 . 
• 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
• Putz, Volkmar; Svozil, Karl (2010). „Can a computer be "pushed" to perform faster-than-light?”. arXiv:1003.1238 . 

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

• Ord, Toby (2002). „Hypercomputation: computing more than the Turing machine”. arXiv:math/0209332 . 

Спољашње везе

• Hypercomputation Research Network
• Hypercomputation
• 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