
super-recursive algorithm

computability theory mein, super-recursive algorithm samanya algorithm kaa ack saamaanyikaran haye joe adhik shaktishali haye, yaani turing machines kii tulanaa mein adhik ganana karein. iss shabd koo maark bergin dwara pesh kiya gayaa thaa, jinaki pustak "super-recursive algorithm" unake siddhant koo vikasit karati haye aur kaee ganitiya model prastut karati haye. turing masheenen aur paaramparik algorithm key anya ganitiya model shodhkartaon koo punaraavarti algorithm aur unaki gananaon key gunon koo khojane kii anumati dete hain. isi tarah, atee-punaraavarti algorithm key ganitiya model, jaise kii prerak turing masheenen, shodhkartaon koo atee-punaraavarti algorithm aur unaki gananaon key gunon koo khojane kii anumati detee hain.
bergin key saath-saath anya shodhkartaon (selim aeye. key. ell., eugene aberback, peater kugal, zaan vaine leeuven, havaa seagleman, peater wegner aur jeeri weederman sahit) jinhone vibhinn prakaar key super-recursive algorithm kaa adhyayan kiya aur super-recursive algorithm key siddhant mein yogdan diyaa, ney tark diyaa haye kii super-recursive algorithm kaa upayog church-turing thesis koo galat saabit karane key liye kiya jaa sakata haye, lekin iss drishtikon kii ganitiya samudaay key bheetar aalochana kii gaee haye aur ise vyaapak roop seey sweekaar naheen kiya gayaa haye.
paribhasha.
bergin (2005:13) algorithm key liye punaraavarti algorithm shabd kaa upayog kartaa haye jise turing machines parr lagu kiya jaa sakata haye, aur adhik samanya arthon mein "algorithm" shabd kaa upayog kartaa haye. phir algorithm kaa ack super-recursive varg "algorithm kaa ack varg haye jisamen kissy bhee turing machine dwara ganana yogya naheen honey vaale karyon kii ganana karna sambhav haye" (bergin 2005:107).
atee-punaraavarti algorithm atee-sanganana seey nikatata seey sambandhit hain. 
ack tarah seey sadharan ganana aur sadharan algorithm key beach sambandh key samaan. ganana ack prakriya haye, jabaki ack algorithm aisee prakriya kaa ack seemit rachanaatmak vivaran haye. iss prakaar ack atee-punaraavarti algorithm ack computational prakriya (input aur output kii prakriyaon sahit) koo paribhaashit kartaa haye jise punaraavarti algorithm dwara mahsoos naheen kiya jaa sakata haye."(bergin 2005:108). ack adhik pratibandhit paribhasha kii maang haye kii hypercomputation ack supertask koo hull kartaa haye (dekhein copland 2002; hagger aur corolev 2007).
super-recursive algorithm bhee algoridmic yojanaon seey sambandhit hain, joe super-recursive algorithm kii tulanaa mein adhik samanya hain. bergin kaa tark haye kii super-recursive algorithm aur una algorithm yojanaon key beach spasht antar karna aavashyak haye joe algorithm naheen hain. iss bhed key tahat, kuchh prakaar key hypercomputation super-recursive algorithm dwara praapt kiye jaate hain, jaise.jee., prerak turing masheenen, jabaki anya prakaar key hypercomputation algoridmic yojana dwara nirdeshit hotey hain, ee.jee., anant samay turing masheenen. yeh bataata haye kii super-recursive algorithm parr kaise kaam kartaa haye joe hypercomputation seey sambandhit haye aur isake vipareet. iss tark key anusaar, atee-punaraavarti algorithm ack atee-computational prakriya koo paribhaashit karane kaa sirf ack tarika haye.
udaaharan.
atee-punaraavarti algorithm key udaharanon mein shamil hain (bergin 2005:132):
algoridmic yojanaon key udaharanon mein shamil hainh
vyaavhaarik atee-punaraavarti algorithm key udaharanon key liye, bergin kii pustak dekhein.
prerak turing masheenen.
prerak turing masheenen atee-punaraavarti algorithm key ack mahatvapurna varg koo lagu karati hain. ack prerak turing machine ack kaary koo puuraa karane key liye achchi tarah seey paribhaashit nirdeshon kii ack nishchit soochi haye, joe ack praarambhik sthiti diye jaane parr, kramik avasthaon kii ack achchi tarah seey paribhaashit shrinkhala key madhyam seey aage badhegi, joe antatah antim parinam degi. ack prerak turing machine aur ack sadharan turing machine key beach kaa antar yeh haye kii ack sadharan turing machine koo apana parinam praapt karane parr rukna chaahiye, jabaki kuchh mamalon mein ack prerak turing machine parinam praapt karane key baad, binaa ruke ganana karna jaari rakh sakati haye. clean koo prakriya kahaa jaataa haye joe "ganana prakriya yaa algorithm" (clean 1952:137) key naam seey ruke binaa hamesha key liye chala sakati haye. clean ney yeh bhee maang kii kii iss tarah key algorithm koo antatah "kuchh vastu" (clean 1952:137) pradarshit karna chaahiye. bergin kaa tark haye kii yeh sthiti prerak turing machines dwara santusht haye, kyonki unake parinam seemit sankhya mein charanon key baad pradarshit kiye jaate hain. jaba unakaa antim utpaadan kiya jaataa haye tou prerak turing machines koo rokane kaa nirdesh naheen diyaa jaa sakata haye, iska kaaran yeh haye kii kuchh mamalon mein prerak turing masheenen yeh bataane mein saksham naheen hoe sakati hain kii parinam kiss charan mein praapt kiya gayaa haye.
saral prerak turing masheenen ganana key anya models key barabar hain jaise kii smidhubar kii samanya turing masheenen, hillery putnam key pareekshan aur truti purvanuman, soney key aanshik punaraavarti karyon koo seemit karna, aur hintica aur mutenen (1998) kii pareekshan-aur-truti masheenen. adhik unnat prerak turing masheenen bahut adhik shaktishali hoti hain. inductive turing machines key padanukram hain joe ankganitiya padanukram (bergin 2005) key manmaane sett mein sadasyata taya curr sakate hain. ganana key anya samkaksh models kii tulanaa mein, saral prerak turing masheenen aur samanya turing masheenen computing automata kaa pratyaksh nirmaan detee hain joe poori tarah seey bhautik machines mein adharit hoti hain. isake vipareet, pareekshan aur truti purvanirdhaarit kartaa haye, punaraavarti karyon koo seemit kartaa haye, aur aanshik punaraavarti karyon koo seemit kartaa haye, joe unake herfer key liye aupchaarik niyamon key saath prateekon kii kewal vaakya rachana pranaliyon koo prastut kartaa haye. saral prerak turing masheenen aur samanya turing masheenen aanshik punaraavarti karyon koo seemit karane aur pareekshan-aur-truti purvaanumaanon seey sambandhit hain kyonki turing masheenen aanshik punaraavarti karyon aur lambda calculus seey sambandhit hain.
prerak turing machines kii gair-halling gananaon koo anant-samay gananaon key saath bhramit naheen kiya jaanaa chaahiye (udaaharan key liye, potjeetar 2006 dekhein). sabse pahale, prerak turing machines kii kuchh gananaaen rook jaati hain. jaisa kii paaramparik turing machines key mamle mein, kuchh rukane vaali gananaaen parinam detee hain, jabaki anya naheen. bhale hii yeh naheen rukta haye, ack prerak turing machine samay-samay parr utpaadan karati haye. yadi yeh utpaadan badalana bund curr detaa haye, tou ise ganana kaa parinam maanaa jaataa haye.
sadharan turing machines aur saral prerak turing machines key beach dou mukhya antar hain. pahala antar yeh haye kii sadharan prerak turing masheenen bhee paaramparik turing machines kii tulanaa mein bahut adhik curr sakati hain. doosara antar yeh haye kii ack paaramparik turing machine hamesha yeh nirdhaarit karegi (ack antim sthiti mein aakar) jaba parinam praapt kiya jaataa haye, jabaki ack sadharan prerak turing machine, kuchh mamalon mein (jaise kii jaba "computing" kuchh aisaa haye jisaki ganana ack sadharan turing machine dwara naheen kii jaa sakati haye), yeh nirdhaaran karane mein saksham naheen hogi.
shmidhubar kii saamaanyikrit turing masheenen.
ack prateek anukram seema mein ganana yogya haye yadi ack saarvbhaumik turing machine parr ack seemit, sambhavatah gair-halling prograam haye joe anukram key pratyek prateek koo vriddhi seey output kartaa haye. isamen π kaa diadic vistaar shamil haye lekin phir bhee adhikansh vaastavik sankhyaaen shamil naheen hain, kyonki adhikansh koo ack seemit karyakram dwara varnit naheen kiya jaa sakata haye. kewal likhane key liye utpaadan tape vaali paaramparik turing masheenen apane pichhale output koo sampaadit naheen curr sakati hain; saamaanyikrit turing masheenen, jurgen shmidhubar key anusaar, apane utpaadan tape key saath-saath apane kaary tape koo bhee sampaadit curr sakati hain. vaha rachanaatmak roop seey varnit prateek anukramon koo una logon key roop mein paribhaashit kartaa haye jinake paas ack seemit, gair-halling prograam haye joe ack saamaanyikrit turing machine parr chala rhaa haye, jaise kii koee bhee output prateek antatah abhisaran kartaa haye, yaani, yeh kuchh seemit praarambhik samay antaral key baad aur naheen badalata haye. shmidhubar (2000,2002) iss drishtikon kaa upayog aupchaarik roop seey varnan karane yogya yaa rachanaatmak roop seey computable brahmaandon yaa harr cheej key rachanaatmak siddhanton key sett koo paribhaashit karane key liye kartaa haye. saamaanyikrit turing masheenen aur saral prerak turing masheenen super-recursive algorithm key dou varg hain joe recursive algorithm (skmidhubar 2000) key sabse karib hain.
church-turing thesis seey sambandh.
punaraavartan siddhant mein church-turing thesis "algorithm" shabd kii ack vishesh paribhasha parr nirbhar kartaa haye. aisee paribhashaon key aadhar parr joe aamtaur parr punaravritti siddhant mein upayog kii jaane vaali paribhashaon kii tulanaa mein adhik samanya hain, bergin kaa tark haye kii atee-punaraavarti algorithm, jaise kii prerak turing masheenen church-turing thesis koo galat saabit karati hain. vaha aage saabit karate hain kii atee-punaraavarti algorithm saiddhaantik roop seey quantum algorithm kaa upayog karane kii tulanaa mein aur bhee adhik dakshata laabh pradaan curr sakate hain.
super-recursive algorithm kii bergin kii vyakhya koo ganitiya samudaay mein virodh kaa saamana karna padaa haye. ack aalochak tarkashastri martin davis hain, joe tark dete hain kii bergin key daavon koo "dashakon seey" achchi tarah seey samajha gayaa haye. davis kahate hain, 
david bergin key una daavon parr vivaad kartaa haye joe ankganitiya padanukram key star sootra _ 1 parr sett karate hain, jinhen computable kahaa jaa sakata haye, kahate hain

