Хиперрачунање или супер-Тјурингово рачунање се односи на моделе рачунања који превазилазе Тјурингову израчунљивост. Ово укључује различите хипотетичке методе за израчунавање не-Тјурингове-израчунљиве функције.
Термин " супер-Тјурингово рачунање" појавио се почетком 1990-их, са најмање два независна извора наведена у литератури. Појавио се у разговорима, PhD тезе,Hava Siegelmann (Oct 1993). па чак и ранији технички извештаји Хаве Сигелмана од раних 1990-их за веома посебну теорију (описану у наставку) и постао је подобласт израчунавања од њеног научног папира 1995. Такође се појавио 1990. у разговору Mike Stannett, Super-Turing Computation. и 1991. у техничком извештајуMike Stannett, An Introduction to post-Newtonian and super-Turing computation. Мајка Стенета, који је такође објавио теоријску дискусију једне X-машине базиране на "супер-Тјуринговој машини" у марту 1990.
Термин "хиперрачунање" уведен је у 1999. од стране Џека Копленда и Дајане Праудфут.Copeland & Proudfoot, .
Услови нису баш синоними: "супер-Тјурингово израчунавање" од Сигелмана обично подразумева да ће предложени модел вероватно постојати у природи (преко биологије и / или физике) и стога може да буде физички остварив, док "хиперрачунање" може бити општа математичка или филозофска идеја.
Историја Математички модел који иде преко Тјурингових машина је увео Алан Тјуринг 1938. у својој докторској дисертацији Системи логике базирани на ординалима.Alan Turing, 1939, Volumes 2–45, Issue 1. . Овај рад је истраживао математичке системе у којима је пророчка машина била доступна, што би могло да израчуна једну произвољну (не) рекурзивну функцију из природних бројева у природне бројеве. Он је користио овај уређај да докаже да чак и у оним моћнијим системима, неодлучив задатак је и даље присутан. Тјурингове пророчке машине су математичке апстракције, а нису физички оствариве."Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were.
Хиперрачунање и Черч–Тјурингова теза Черч–Тјурингова теза наводи да се свака алгоритмички израчунљива функција може израчунати помоћу Тјурингове машине. Суперкомпјутери рачунају функције које Тјурингова машина не може и који су, стога, неизрачунљиви у Черч-Тјуринговом смислу.
Пример проблема који Тјурингова машина не може да реши јесте Халтинг проблем. Тјурингова машина не може да одлучи да ли се произвољан програм зауставља или ради заувек. Неки предлажу да би суперкомпјутери могли да симулирају програм са бесконачним бројем корака и да укажу кориснику да ли је програм заустављен. Посебно, Сигелман је показала у својој докторској дисертацији 1993, и касније у својој књизи 1998,H.T. Siegelmann, "Neural Networks and Analog Computation: Beyond the Turing Limit", Birkhauser, Boston, December 1998 да Халтинг проблем Тјурингових машина може да се реши са аналогним периодичним неуронским мрежама.
Супер-Тјурингово рачунање и супер-Тјурингова теза У раним 1990-им Хава Сигелман и Едуардо Сонтаг су доказали да је њихов нови компјутерски модел, Вештачка Рекурентна Природна Мрежа (ARNN), могла да обавља изван Тјурингове границе (хиперрачунање)
Сигелман и њене колеге су открили хијерархију добро утврђених рачунарских класа које почињу од Тјурингове машине и уздижу се до пуне супер Тјурингове снаге Сигелман је описала у разним публикацијама које постоје много начини да се дође до супер-Тјуринговог рачунања. Док је прво показала постојање супер-Тјуринговог рачунања преко аналогне неуронске мреже са фиксном (не за учење) и неограниченом тежином, отишла је да доказује супер-Тјурингову снагу у многим различитим остваривим машинама укључујући и мале прецизне тежине неуронске мреже које примају своју моћ од: учења у аналогном домену, или користећи стокастику, или развијање током времена, или коришћење података из окружења, или система који су Тјурингови у било којим израчунљивим корацима и између промена на једну од наведених метода. Види још рад у Верификацији својстава неуронских мрежа.
Сигелманин научни рад показује први корак ослобађања овог рачунања док садашњи напори постоје од стране физичара и инжењера у изградњи таквих система. Сигелманино недавно истраживање доказује да је стање простора супер-Тјуринговог рачунања а простор Тјурингових машина само , што даје ново схватање да је Тјурингов тест - као раздвајање простора различитих величина.
Теорија је довела до бољег разумевања неуронске мреже (Фондација дубоког учења) и подржаних иновативних апликација у тако осетљивим областима као што су регистрације радара и контрола нуклеарних електрана. J.P. Neto, H.T. Siegelmann, and J.F. Costa, "Implementation of Programming Languages with Neural Nets" J. Kilian and H.T. Siegelmann, Information and Computation , 1996: 45-56. H.T. Siegelmann, B.G. Horne, and C.L.Giles, IEEE Transaction on Systems, Man and Cybernetics – part B: Cybernetics 47. Сигелман и њене колеге су отишле даље да створе теорију сложености за континуирано време и физичке системе.H.T. Siegelmann and S. Fishman, Physica D 120, . Као конкретан пример Сигелманова група је анализирала линеарно програмирање и друге компјутерско научне проблеме који показују да аналогни рачунари могу да реше брже од дискретних временских рачунара. 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.
Недавна публикација открива да је Алан Тјуринг био у потрази за супер-Тјуринговим израчунавањем заснованим на принципима мозга, и показао своје предложене правце како се траже да се савршено слажу са Сигелманим теоријама. H. T. Siegelmann, "Turing on Super-Turing and Adaptivity". Сигелман и Сонтаг су предложили нову рачунарску хипотезу - док аналогно, учење, и еволуирајући системи су били ограничени супер-Тјуринговом рачунском снагом.
Остали предлози супер-рачунара Тјурингова машина која може да заврши бесконачно много корака. Једноставно бити у стању да ради за неограничен број корака није довољно. Један математички модел је Зенонова машина (инспирисано Зеноновим парадоксима). Зенонова машина обавља свој први корак у израчунавању (рецимо) 1 минут, други корак у ½ минут, трећи корак у ¼ минут, итд Сумирајући 1+½+¼+... (геометријска серија) видимо да машина обавља бесконачно много корака у укупно 2 минута. Према Шагриру, Зенонове машине уводе физичке парадоксе, а њихово стање је логично дефинисано ван једне стране отвореног периода [0, 2), тако недефинисана тачно у 2 минута после почетка рачунања.These models have been independently developed by many different authors, including Hermann Weyl (1927). Тјурингова оригинална Пророчка машина, дефинисана од стране Тјурнинга 1939. Средином 1960-их, Е Марк Голд и Хилари Патнам независно су предложили моделе индуктивног закључивања (на "ограничавање рекурзивних функционалности" и "суђење и грешке предиката", ). Ови модели омогућавају неким нерекурзивним скуповима бројева или језика (укључујући све рекурзивно бројиве скупове језика) да се "науче у року"; док, по дефиницији, само рекурзивни скупови бројева или језика могу се препознати по Тјуринговој машини. Док ће се машина стабилизовати на тачан одговор на било ком наученом скупу у неком коначном времену, то само може да се идентификује као тачно да је рекурзивна; у супротном, коректност је основана само када машина ради заувек и истичући да никада ревидира свој одговор. Патнам је идентификовао ову нову интерпретацију као класу "емпиријског" предиката, наводећи: "ако смо увек" претпоставка "генерисали одговор да је тачан, направићемо коначан број грешака, али ћемо на крају добити тачан одговор. (Напомена, међутим, да чак и ако смо стигли до тачног одговора (на крају коначног низа) нисмо сигурни да имамо тачан одговор.)" Л. К. Шубертов папир 1974. "Итеративно ограничење рекурзије и програм проблема минимизирања" проучавао ефекте итеративног поступка ограничавања; ово омогућава сваком аритметичком предикату да се израчуна. Шуберт је написао: "Интуитивно, итеративна ограничавајућа идентификација може се сматрати вишим редом индуктивног закључка који се изводи колективно од стране све веће заједнице нижег реда индуктивних закључака машина." Прави компјутер (нека врста идеализованог аналогног рачунара) може обављати хиперрачунање Arnold Schönhage, "On the power of random access machines", in Proc. ако физика признаје опште реалне променљиве (не само за израчунавање реалних бројева), а то су на неки начин "упрегнуте" за обрачун. Ово може захтевати доста бизарних закона физике (на пример, мерљива физичка константа са пророчком вредношћу, као што су Чејтинова константа), те би у најмању руку захтевала способност да измери стварну-вредности физичке вредност произвољне прецизности и поред топлотне буке и квантних ефеката. Предложена техника позната као фер недетерминисана или неограничена недетерминисана може дозволити израчунавања неизрачунљивих функција. Постоји спор у литератури око тога да ли је ова техника кохерентна, и да ли заиста дозвољава неизрачунљивим функцијама да буду "израчунљиве". Чини се да је природна могућност путовања кроз време (постојање затворених временских кривих (CTCs) чини хиперрачунање могуће само по себи. Међутим, то није тако пошто CTC не даје (по себи) неограничену количину складишног капацитета која би бесконачно рачунање захтевала. Ипак, постоје време и простор у којима се CTC регион може користити за релативистичко хиперрачунање.Hajnal Andréka, István Németi and Gergely Székely, Closed Timelike Curves in Relativistic Computation Parallel Process. Приступ CTC може дозволити брзо решење PSPACE-комплетних проблема, комплексност класе која, док је Тјуринг-одлучив, се генерално сматра рачунски сложеним.Todd A. Brun, Computers with closed timelike curves can solve hard problems, Found.S. Aaronson and J. Watrous. Према 1992 папиру,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. Бесконачно време Тјурингове машине је генерализација Зенонове машине, која може обављати бескрајно дуге прорачуне чији кораци су набројани потенцијално трансфинитним редним бројевима. Њени модели иначе обичне-Тјурингове машине због којих су незаустављање израчунавања завршени уносом посебног стања резервисаног за постизање лимита редног броја и којима су резултати претходно бесконачног израчунавања доступни. Јан ван Леувен и Јири Видерман су написали папир Jan van Leeuwen; Jiří Wiedermann (September 2000). сугеришући да интернет треба да буде моделиран као јединствен некомпјутерисан систем опремљен саветима функција које представљају способност рачунара да се надогради.