Википедија

Tjuringova potpunost

U teoriji izračunljivosti (računarstvu), sistem za obradu podataka pravila (kao što je skup instrukcija računara, neki programski jezik, ili ćelijski automat) je rekao da je Tjuring potpun ili računski univerzalan ako se može koristiti za simulaciju bilo koje snimljene trake Tjuringove Mašine . Koncept je dobio ime po engleskom matematičaru Alanu Tjuringu. Klasičan primer je lambda račun.

Usko povezan koncept je koncept Tjuringove ekvivalencije - dva kompjutera P i K se nazivaju ekvivalentna ako P može simulirati K i K može da simulira P. Prema Čerč-Tjuringovoj tezi, koja pretpostavlja da su Tjuringove mašine najmoćnije kompjuterske mašine, za svaki računar u realnom svetu postoji Tjuringova mašina koja može da simulira svoje računske aspekte. Univerzalne Tjuringove mašine mogu simulirati bilo koju Tjuringovu Mašinu a samim tim i računarske aspekte svakog mogućeg računara u realnom svetu.

Da bi pokazao da je nešto Tjuring potpuno, dovoljno je da pokaže da može da se koristi da simulira neki Tjuring potpun sistem. Na primer, imperativno programiranje je Tjuring potpuna ako ima uslovno grananje (npr.: "ako" i "idi" izjave, ili "granaj ako je nula" uputstva. Vidi: Jedan skup računarskih instrukcija ( OISC)) i sposobnost da promeni proizvoljnu količinu računarskih memorijskih lokacija (npr. sposobnost održavanja proizvoljnog broja varijabli). Pošto je ovo gotovo uvek slučaj, većina (ako ne i svi) imperativni programi su Tjuring potpuni ako se ignorišu ograničenja konačne memorije.

Upotreba pored matematike uredi

U kolokvijalnoj upotrebi, termini "Tjuring potpun" ili "Tjuring ekvivalentan" se koriste da označe da bilo koji računar za opštu namenu ili računarski jezik mogu približno da simuliraju računarske aspekte bilo kog drugog računara za opštu namenu ili računarski jezik.

Pravi kompjuteri izgrađeni do sada su u suštini slični snimljenoj traci Tjuringove Mašine. Međutim, pravi kompjuteri imaju ograničene fizičke resurse, tako da su oni samo  linearno-ograničeni automat potpuni. Nasuprot tome, univerzalni računar se definiše kao uređaj sa Tjuring potpunim setom instrukcija, beskrajnom memorijom, i beskonačnim raspoloživim vremenom.

Formalne definicije uredi

U teoriji izračunljivosti (računarstvu), nekoliko usko povezanih termina koriste se da opišu računarske snage matematičkih  sistema (kao što je apstraktna mašina ili programski jezik):

Tjuringova potpunost
Matematički sistem koji može da izračuna svaku Tjuringovu-računsku funkciju zove se Tjuring potpun (ili Tjuring moćan). Alternativno, takav sistem je onaj koji može da simulira univerzalnu Tjuringovu mašinu.
Tjuring ekvivalentan
Tjuring-potpun sistem se naziva Tjuring ekvivalentan ako se svaka funkcija koja se može izračunati takođe Tjuring izračunljiva; tj, da izračunava potpuno istu klasu funkcija kao i Tjuringove mašine. Alternativno, Tjuring-ekvivalentan sistem je onaj koji može da simulira, i da bude simuliran, univerzalnom Tjuringovom mašinom. (Svi poznati Tjuring-potpuni sistemi su i Tjuring ekvivalentni, što dodaje podršku Čerč-Tjuringovoj tezi.)
(Računarska) univerzalnost
Sistem se zove univerzalnim u odnosu na klasu sistema ako mu se mogu izračunati sve računske funkcije od strane sistema u toj klasi (ili može da simulira svaki od tih sistema). Tipično, termin univerzalnost se prećutno koristi u odnosu na Tjuring-potpunu klasu sistema. Termin "slabo univerzalni" se ponekad koristi za razlikovanje sistema (npr. ćelijski automat) čija univerzalnost se ostvaruje samo izmenom standardne definicije Tjuringove mašine kako bi uključili ulazne tokove sa beskonačno mnogo 1s.

Istorija uredi

Tjuringova potpunost je značajna u svakom realno vremenskom dizajnu za računarske uređaje da može biti simuliran od strane univerzalne Tjuringove mašine. Čerč-Tjuringova teza glasi da je ovo zakon matematike - da univerzalna Tjuringova mašina može, u principu, obavljati bilo koji obračun da bilo koji drugi računar može programirati. To ništa ne govori o naporu potrebnom da napiše program, ili vreme potrebno mašini za obavljanje obračuna, ili sposobnostima mašina koje mogu posedovati a koji nemaju nikakve veze sa obračunom.

Čarls Bebidžova analitička mašina (1830) bi bila prva Tjuring-potpuna mašina ako bi izgrađena u vreme kada je projektovana. Bebidž ceni da je mašina bila u stanju velikih podviga obračuna, uključujući i primitivno logičko rasuđivanje, ali nije procenio da nijedna druga mašina može bolje. Od 1830. do 1940. , mehaničke mašine za računanje, kao što su šarke i multiplikatorima izgrađeni i poboljšani, ali nisu mogli da obavljaju uslovno granu i stoga nisu Tjuring potpuna.

Krajem 19. veka, Leopold Kroneker je formulisao pojmove izračunljivosti, definisanjem primitivnih rekurzivnih funkcija. Ove funkcije se mogu izračunati napamet, ali nisu dovoljne da se napravi univerzalni računar, jer su instrukcije koje ih izračunavaju ne dozvoljavaju beskonačnu petlju. Početkom 20. veka, Dejvid Hilbert je vodio program aksiomatizacije svih matematika sa preciznim aksiomima i preciznim logičnim pravilima oduzimanjem koje bi mogla da obavlja mašina. Ubrzo je postalo jasno da je mali skup pravila odbitaka dovoljan da proizvede posledice bilo kog skupa aksioma. Ova pravila su dokazana od strane Kurta Gedela 1930. kao dovoljna da proizvedu svaku teoremu. Međutim, one će uvek dokazati teoreme kao istinito i lažno, za aksiomatizaciju nije jednostavnija od Peanovih aksioma.

Stvarni pojam računanja je izolovan ubrzo nakon toga, počevši od Gedelove teoreme o nepotpunosti. Ove teoreme pokazale su da su aksiomni sistemi ograničeni kada obrazlažu o proračunu koji zaključuje njihove teoreme. Čerč i Tjuring su nezavisno pokazali da je Hilbertov program pronalaženja potpunog i konzistentnog skupa aksioma koji bi važio za celu matematiku bio nerešiv, i time identifikovali nekompletnost teoreme. Ovaj rad, zajedno sa Gedelovim radom na opštim rekurzivnim funkcijama, utvrdio da postoje skupovi jednostavnih uputstava, koja, kada se stave zajedno, su u stanju da proizvode bilo koje računanje. Gedelov rad je pokazao da je pojam računanja u suštini jedinstven.

Teorija izračunljivosti uredi

Prvi rezultat teorije izračunljivosti je da je nemoguće uopšte da se predvidi šta će Tjuring-kompletan program učiniti i posle proizvoljno dugo vremena. Na primer, nemoguće je utvrditi za svaki par programa-ulaz da li će se program, koji radi na ulazu, na kraju zaustaviti ili će nastaviti zauvek (vidi halting problem). To je nemoguće odrediti da li će program vratiti "istina" ili da li će se vratiti "laž". Za svaku karakteristiku eventualne proizvodnje programa, nemoguće je odrediti da li će ova karakteristika izdržati. To može da izazove probleme u praksi prilikom analiziranja kompjuterskih programa. Jedan od načina da se to izbegne je da izazove program da se zaustavi izvršenje nakon određenog perioda vremena (tajmaut), ili da ograniče moć uputstva za kontrolu protoka. Takvi sistemi nisu Tjuring-potpuni dizajnirani.

Druga teorema pokazuje da postoje problemi rešivi Tjuring-potpunim jezicima koji se ne mogu rešiti bilo kojim jezikom samo sa sposobnošću konačnih petlji (npr, na bilo kom jeziku koji garantuje svaki program će na kraju završiti do zastoja). S obzirom na garantovanu obustavu jezik, računarsku funkciju koja je proizvedena od strane Kantorove dijagonale argumenta o svim računarskim funkcijama u tom jeziku nije izračunljiv na tom jeziku.

Tjuringova proročka mašina uredi

Računar sa pristupom beskrajnoj traci podataka može biti moćniji od Tjuringove mašine: na primer, traka možda sadrži rešenje halting problema ili nekog drugog Tjuringovog-neodlučivog problema. Takva beskrajna traka podataka se zove Tjuringova proročka mašina. Čak i Tjuringova proročka mašina sa slučajnim podacima nije izračunljiva (sa verovatnoćom 1), jer postoje mnogi izračunljivi proračuni ali neizračunljivi proroci. Dakle, računar sa slučajnom Tjuringovom proročkom mašinom može izračunati stvari koje Tjuringova mašina ne može.

Digitalna fizika uredi

Svi poznati zakoni fizike imaju posledice koji su za izračunavanje nizom aproksimacija na digitalnom računaru. Hipoteza koja se zove digitalna fizika navodi da ovo nije slučajno, da je to zato što je sam svemir izračunljiv na univerzalnoj Tjuringovoj mašini. To bi značilo da nema kompjutera moćnijeg od univerzalne Tjuringove mašine koji mogu biti fizički izgrađeni (vidi Čerč-Tjuringovu tezu - filozofske implikacije).

Primeri uredi

Računarski sistemi (algebre, kalkulusa) koji se pominju kao Tjuring potpuni sistemi su namenjeni za studiranje teorijskog računarstva. Oni treba da budu što jednostavniji, tako da bi bilo lakše da se shvate granice računanja. Evo nekoliko:

Većina programskih jezika, konvencionalni i nekonvencionalni, su Tjuring-potpuni. To uključuje:

Tjuringova potpunost je apstraktna izjava sposobnosti, a ne propisivanje specifičnosti jezika koji se koristi za sprovođenje te sposobnosti. Funkcije se koriste za postizanje Tjuringove potpunosti može biti sasvim drugačiji; Fortran sistemi će koristiti petlje konstrukcije ili čak GoTo na izjave da se postigne ponavljanje; Haskel i Prolog, bez petlje skoro u potpunosti, će koristiti rekurziju.

Tjuringova potpunost u deklarativnom SQL se realizuje kroz zajedničku tabelu rekurzivnih izraza. Ne iznenađuje, proceduralna proširenja SQL (PLSQL, itd) su takođe Tjuring potpuna. To ilustruje jedan od razloga zašto su relativno snažni ne-Tjuring-potpuni jezici retki: snažniji jezik je u početku, složeniji su zadaci na kojima se primenjuje i ranije njen nedostatak potpunosti počinje da se doživljava kao mana, podsticanje je proširenje dok ne bude Tjuring potpun.

Ne otkucan Lambda račun je Tjuring potpun, ali mnogi otkucani lambda kalkulusi, uključujući Sistem F, nisu. Vrednost kucanih sistema se zasniva na njihovoj sposobnosti da predstavljaju većinu tipičnih kompjuterskih programa, dok otkriva više grešaka.

Pravilo 110 i Konvejeva igra života, oba ćelijska automata, su Tjuring potpuni.

Na nižem nivou, svaki jezik koji može da simulira osnovne komponente (logička kola, itd) je Tjuring potpun. Hardver opis jezici poput VHDL i Verilog su Tjuring potpuni, jer se oba koriste za dizajniranje čipova od kojih su moderni računari napravljeni. Majnkraft koji je u stanju da imitira logička kola koristeći svoj redstoun i klip mehanizma, takođe Tjuring potpun.

Jezici koji nisu Tjuring poptuni uredi

Postoje mnogi računarski jezici koji nisu Tjuring potpuni. Jedan takav primer je skup regularnih jezika, najčešće regularnih izraza, koji su generisani u konačnom automatu. Moćniji, ali još uvek ne Tjuring-potpuno produženje konačnih automata je kategorija potisni automati i kontekstno slobodna gramatika, koje se obično koriste za generisanje analize stabla u početnoj fazi kompilatora. Dalji primeri su neke od ranih verzija Piksel Šader jezika ugrađenih u Direct3D i OpenGL proširenja.

U kompletno funkcionalnom programiranju programskih jezika, kao što su Charity i Epigram, sve funkcije su ukupne i moraju se prekinuti. Charity koristi tip sistema i kontrole konstrukcije zasnovane na teoriji kategorije, dok Epigram koristi zavisne vrste. Petlja jezika je dizajnirana tako da izračunava samo funkcije koje su primitivno rekurzivne. Sve ovo izračuna odgovarajuće podskupove ukupnih izračunljivih funkcija, dok je ceo set kompletnih izračunljivih funkcija neizračunljiv nabrajanjem. Takođe, pošto su sve funkcije u ovim jezicima konačne, algoritmi za rekurzivne setove nabrajanja ne mogu biti napisani na ovim jezicima, u suprotnosti sa Tjuringovim mašinama.

Iako (ne otkucan) lambda račun je Tjuring-potpun, prosto otkucan lambda račun nije.

Jezici podataka uredi

Pojam Tjuringova-potpunost se ne odnosi na jezike kao što su XML, HTML, JSON, YAML i S-expressions, jer se obično koriste za predstavljanje struktuiranih podataka, ne opisuju računanja. Oni se ponekad nazivaju jezicima za obeležavanje, ili tačnije kao "posuda sa jezicima" ili " jezicima za opisivanje podataka". Međutim, pravilo 110, Tjuring potpun ćelijski automat uspešno je realizovan u CSS-u, čime dokazuje (u određenoj meri) svoju Tjuringovu potpunost.

Vidi još uredi

Reference uredi

Literatura uredi

Spoljašnje veze uredi

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Тјурингова_потпуност&oldid=27028469”