Izračunljiva funkcija

"Sve rekurzivne funkcije" se prosleđuju ovde. Za druge vrste "rekurzivne funkcije", videti Rekurzivna funkcija (višeznačna odrednica).

Izračunljive funkcije su osnovni predmeti istraživanja u teoriji računanja. Izračunljive funkcije su formalizovane analogno intuitivnom pojmu algoritma, u smislu da se funkcija za izračunavanje ako postoji algoritam koji može da uradi posao funkcije, odnosno da doprinos domenu funkcije može vratiti u odgovarajući izlaz. Funkcije za izračunavanje se koriste kako bi razgovarali o računanju bez pozivanja na bilo koji konkretan model obračuna, kao što su Tjuringove mašine ili mašine registra. Bilo koja definicija, međutim, mora se pozivati na određen model obračuna, ali sve važeće definicije daju iste klase funkcija. Posebni modeli računanja koji dovode do niza funkcija za računanje su Tjuringove funkcije za računanje  i μ rekurzivne funkcije.

Pre preciznog definisanja funkcije za izračunavanje, matematičari često koriste neformalan termin efikasno proračunljivosti. Ovaj termin je od tada došao da se identifikuju sa funkcijama za izračunavanje. Imajte na umu da delotvorno računanje ovih funkcija ne implicira da mogu biti efikasno izračunate (tj. izračunavanje u razumnom vremenskom roku). U stvari, za neke efikasno izračunljive funkcije može se pokazati da će svaki algoritam koji ih izračunava biti veoma neefikasan u smislu da vreme rada algoritma raste eksponencijalno (ili čak supereksponencijalno) sa dužinom ulaza. Polja izvodljive izračunljivosti i izračunljive kompleksnosti studijskih funkcija koje se mogu efikasno izračunati.

Prema Čerč-Tjuringova tezi, funkcije za izračunavanje su upravo funkcije koje se mogu izračunati pomoću mehaničkog uređaja za izračunavanja kojem je dato neograničena količina vremena i prostora. Ekvivalentno, ova teza navodi da svaka funkcija koja ima algoritam za izračunljiva je i obrnuto. Imajte na umu da se algoritam u tom smislu shvata kao redosled koraka lica sa neograničenim vremenom i beskrajnim snabdevanjem papira i olovki.

Blumove aksiome se mogu koristiti za definisanje apstraktne teorije kompleksnosti izračunavanja na setu funkcija za izračunavanje. U teoriji kompleksnosti izračunavanja, problem određivanja složenosti funkcija za izračunavanje je poznat kao problem funkcije.

Definicija

Usklađenost funkcije je neformalni pojam. Jedan od načina da se opiše je da se može reći da je funkcija za izračunavanje ako se njena vrednost može dobiti efikasnim postupkom. Sa više strogoće, funkcija  $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$  je izračunljiva ako i samo ako postoji efektivan postupak koji, ako je data bilo kaja k-torka $\mathbf {x}$ prirodnih brojeva, daje vrednost $f(\mathbf {x} )$. U dogovoru sa ovom definicijom, ostatak ovog članka pretpostavlja da izračunljive funkcije uzimaju konačno mnogo prirodnih brojeva kao argumente i proizvode vrednost koja je jedan prirodan broj.

Kao dodatak ovog neformalnog opisa, postoje više formalne, matematičke definicije. Klasa izračunljivih funkcija se može definisati u mnogim ekvivalentnim modelima obračuna, uključujući

• Tjuringova mašina
• μ-rekurzivne funkcije
• Lambda račun
• Post mašine (Post-Tjuringove mašine i mašine za oznaku).
• Mašine registra

Iako ovi modeli koriste različite reprezentacije za funkcije, njihovi ulazi i njihovi rezultati, prevode postojeće između bilo koja dva modela, i tako svaki model opisuje u suštini ista klasa funkcija, što dovodi do mišljenja da je formalno izračunavanje i prirodno i ne previše usko.

Na primer, mogu se formalizovati izračunljive funkcije kao μ-rekurzivne funkcije, koje su delimične funkcije koje uzimaju konačne zapise prirodnih brojeva i vraćaju jedan prirodni broj (kao gore). One su najmanja klasa parcijalnih funkcija koje uključuju konstantnu, naslednika, i projekciju funkcije i zatvorene su pod složenom funkcijom, primitivna rekurzija, i μ operater .

Ekvivalentno, izračunljive funkcije mogu biti ozvaničene kao funkcije koje mogu da se obračunavaju od strane idealizovanog računarskog agenta, kao što je Tjuringova mašina ili mašina registra. Formalno gledano, delimična funkcija $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ može se izračunati ako i samo ako postoji kompjuterski program sa sledećim karakteristikama:

1. Ako je $f(\mathbf {x} )$ definisano, onda će program odraditi unetu vrednost $\mathbf {x}$ sa vrednošću $f(\mathbf {x} )$ smeštenoj u memoriji računara.
2. Ako $f(\mathbf {x} )$ nije definisano, onda program nikada neće izvršiti uneto $\mathbf {x}$.

Karakteristike izračunljivih funkcija

Glavni članak: Algoritam

Osnovne karakteristike izračunljive funkcije su da mora postojati konačan postupak (algoritam) koji govori kako da se izračuna funkcija. Modeli računanja gorenavedeni daju različite interpretacije onoga što je procedura i kako se koristi, ali ove interpretacije dele mnoge osobine. Činjenica da ovi modeli daju ekvivalentne klase izračunljivih funkcija proizlazi iz činjenice da je svaki model sposoban da čita i oponaša postupak za bilo koji od drugih modela, koliko kompajler može da čita uputstva u jednom kompjuterskom jeziku i emituje uputstva u drugom jeziku.

Enderton [1977] daje sledeće karakteristike postupka za izračunavanje izračunljive funkcije; slične karakterizacije su dali Tjuring [1936], Rodžers [1967] i drugi.

• "Mora da postoje tačna uputstva (tj. program), konačne dužine, za postupak."

Tako svaka izračunljiva funkcija mora imati ograničen program koji u potpunosti opisuje kako funkcija treba da se izračuna. Moguće je izračunati funkciju samo prateći uputstva; nema nagađanja ili je potreban poseban uvid.

• "Ako je postupku data k-torka x u domenu f, a zatim konačni broj diskretnih koraka postupka se mora prekinuti i proizvesti f(x)."

Intuitivno, postupak se nastavlja korak po korak, sa posebnim pravilom da pokrije šta se radi na svakom koraku obračuna. Jedino konačno mnogo koraka se može obaviti pre vrednosti vraćene funkcije.

• "Ako je postupku data k-torka x koja nije u svom domenu f, onda postupak može ići unedogled, nikada da se zaustavi. Ili može da se zaglavi u nekom trenutku (tj, jedna od njenih instrukcija se ne može izvršiti) , ali ne sme se pretvarati da proizvede vrednost za f u x. "

Prema tome, ako vrednost za nije f(x) ikada pronađena, to mora biti tačna vrednost. Nije neophodno za računarskog agenta da razlikuje tačne rezultate od onih pogrešnih, jer je postupak uviek tačan kada se stvara ishod.

Enderton ide na listu nekoliko objašnjenja ova 3 zahteva postupka za izračunljivu funkciju:

1. Postupak mora teorijski da radi za proizvoljno velike argumente. Nije pretpostavljano da su argumenti manji od broja atoma Zemlje, na primer.
2. Postupak je potreban da se zaustavi posle konačno mnogo koraka kako bi se proizveo izlaz, ali može da prođe proizvoljno mnogo koraka pre zaustavljanja. Nema vremensko ograničenje koje je pretpostavljeno.

1. Iako postupak može koristiti samo konačan iznos prostora tokom uspešnog izračunavanja, ne postoji vezan iznos prostora koji se koristi. Pretpostavlja se da može dodatni prostor za odlaganje dati procedura, kad god postupak traži to.

Da rezimiramo, na osnovu ovog gledišta funkcija je izračunljiva ako: (a) dat je doprinos o svom domenu, verovatno oslanjajući se na neograničen skladišni prostor, može dati odgovarajući izlaz prema proceduri (program, algoritam) koji se formira od strane konačnog broja egzaktnih nedvosmislenih instrukcija; (b) vraća takav izlaz (zaustavlja) u konačnom broju koraka; i (c) ako je dao svoj doprinos koji nije u svom domenu bilo kad zaustavljan ili se zaglavi.

Oblast računske kompleksnosti proučava funkcije sa propisanim granicama na vremenu i / ili prostoru dozvoljenom u uspešnom izračunavanju.

Izračunljivi skupovi i relacije

Skup A od prirodnih brojeva je izračunljiv (sinonimi: rekurzivni, odlučan) ako postoji izračunljiva, ukupna funkcija f takva da za bilo koji prirodni broj n, f(n) = 1 ako je n u A i f(n) = 0 ako n nije u A.

Skup prirodnih brojeva je brojno izračunljiv (sinonimi: rekurzivno brojiv, poluodlučan) ako postoji izračunljiva funkcija f takva da za svaki broj n, f(n) je definisano ako i samo ako je n u setu. Tako je set je brojivo izračunljiv ako i samo ako je domen neke izračunljive funkcije. Reč brojiv se koristi, jer su ovo ekvivalenti za neprazan podskup B prirodnih brojeva:

• B je domen izračunljive funkcije.
• B je opseg ukupno izračunljive funkcije. Ako je B beskonačno onda se funkcija može pretpostaviti da je injektivna.

Ako je skup B opseg funkcija f onda funkcija može da se posmatra kao nabrajanje B, jer će spisak f(0), f(1), ...  uključivati svaki element B.

Zato što svaka relacija prirodnih brojeva može biti identifikovana sa odgovarajućim setom konačnih sekvenci prirodnih brojeva, pojmovi izračunljive relacije i brojno izračunljive relacije može se definisati iz njihovih analoga za skupove.

Formalni jezici

Glavni članak: Formalni jezik

U teoriji izračunljivosti u računarstvu, uobičajeno je da se razmotre formalni jezici. Alfabet je proizvoljan skup. Reč na pismu je konačan niz simbola iz alfabeta; isti simbol može da se koristi više od jednog puta. Na primer, binarni nizovi su upravo reči azbuke {0, 1}. Jezik je podskup naplate svih reči na fiksnom pismom. Na primer, prikupljanje svih binarnih nizova koji sadrže tačno 3 jedinice je jezik preko binarne abecede.

Ključno svojstvo formalnog jezika je nivo težine koji je potreban da odluči da li će dati reč u jeziku. Neki kodni sistem mora biti razvijen da omogući izračunljivoj funkciji da da proizvoljnu reč u jeziku kao ulaz; ovo se obično smatra rutinom. Jezik je nazvan izračunljivim (sinonimi: rekurzivni, odlučan) ako postoji za izračunavanje funkcija f takva da za svaku reč w pisma, f(w) = 1 ako je reč u jeziku i f(w) = 0 ako reč nije u jeziku. Tako je jezik za izračunavanje samo u slučaju da postoji procedura koja je u stanju da pravilno kaže da li su proizvoljne reči u jeziku.

Jezik je brojno izračunljiv (sinonimi: rekurzivno brojiv, poluodlučan) ako postoji za izračunavanje funkcija f takva da je f(w) definisano ako i samo ako je reč w je na jeziku. Termin brojiv ima istu etimologiju kao u brojivo izračunljivim skupovima prirodnih brojeva.

Primeri

Sledeće funkcije su izračunljive:

• Svaka funkcija sa ograničenim domenom; primer, neki konačan niz prirodnih brojeva.
• Svaka konstantna funkcija f : N^k → N, f(n₁,...n_k) := n.
• Sabiranje f : N² → N, f(n₁,n₂) := n₁ + n₂
• Funkcija koja daje spisak glavnih faktora broja.
• Najveći zajednički delilac dva broja je za izračunljiva funkcija.
• Bezuov stav, linearna jednačina Diofantina

Ako su f i g izračunljivi, onda su i: f + g, f * g, $f\circ g$ ako je f unarna operacija, max(f,g), min(f,g), arg max{y ≤ f(x)} i mnogo drugih kombinacija.

Sledeći primeri ilustruju kako funkcija može biti izračunljiva iako se ne zna koji je algoritam izračunava.

• Funkcija f takva da je f(n) = 1 ako postoji niz najmanje n uzastopnih petica u decimalnom proširenju π, f(n) = 0 u suprotnom, je izračunljiva. (Funkcija f je ili stalna 1 funkcija, što je izračunljivo, inače postoji k takvo da je f(n) = 1 ako je n < k i f(n) = 0 ako je n ≥ k. Svaka takva funkcija je izračunljiva. Nije poznato da li postoje proizvoljno dugačke petice u decimalnom proširenju π, tako da ne znamo koja od tih funkcija je f. Ipak, znamo da funkcija f mora biti izračunljiva.)
• Svaki konačni segment na neizračunljivom nizu prirodnih brojeva (kao što je Bizi biver funkcija Σ) je izračunljiv. Npr, za svaki prirodan broj n, postoji algoritam koji izračunava konačni niz Σ (0), Σ (1), Σ (2), ..., Σ (n) - za razliku od činjenice da ne postoji algoritam koji izračunava celu Σ-sekvencu, odnosno Σ (n) za svako n. Tako "Print 0, 1, 4, 6, 13" je beznačajni algoritam za izračunavanje Σ (0), Σ (1), Σ (2), Σ (3), Σ (4); Slično tome, za svaku datu vrednost n, takav trivijalni algoritam postoji (iako možda nikada neće biti poznat ili proizveden od strane bilo koga) da se izračuna Σ (0), Σ (1), Σ (2), ..., Σ (n).

Čerč–Tjuringova teza

Glavni članak: Čerč-Tjuringova teza

Čerč–Tjuringova teza navodi da svaka funkcija za izračunavanje iz procedure koja poseduje tri svojstva gore navedena je izračunljiva funkcija. Zato što ove tri osobine nisu formalno navedene, Čerč–Tjuringova teza se ne može dokazati. Sledeće činjenice se često uzimaju kao dokaz za tezu:

• Mnogi ekvivalentni modeli računanja su poznati, a svi oni daju istu definiciju izračunljive funkcije (ili slabiju verziju, u nekim slučajevima).
• Nije predložen snažniji model računanja koji se generalno smatra efikasnim za izračunavanje.

Čerč–Tjuringova teza se ponekad koristi u dokazima da opravda da je određena funkcija za izračunavanje koja daje konkretan opis postupka za izračunavanje. To je dozvoljeno jer se veruje da sve takve upotrebe teze mogu biti uklonjene u dosadnom procesu pisanja formalnih postupaka za funkciju u nekom modelu obračuna.

Neizračunljive funkcije i nerešivi problemi

Glavni članak: Lista neodlučnih problema

Svaka izračunljiva funkcija ima ograničenu proceduru koja je eksplicitna, daje nedvosmislene instrukcije o tome kako da se izračuna. Osim toga, ova procedura mora da se kodira u konačnom pismu koje koristi računarski model, tako da su samo brojive mnoge izračunljive funkcije. Na primer, funkcije mogu da se kodiraju korišćenjem niza bitova (alfabet Σ = {0, 1} ).

Realni brojevi su nebrojivi tako da većina realnih brojeva nije izračunljiva. Pogledajte izračunljiv broj. Skup finiranih funkcija na prirodne brojeve je nebrojiv tako da većina nije izračunljiva. Konkretni primeri takvih funkcija su Bizi biver, Kolmogorova kompleksnost, ili bilo koja funkcija koja izlazi na cifre, a ne za izračunavanje broja, kao što su Čejtinova konstanta.

Slično tome, većina podgrupa prirodnih brojeva nisu izračunljive. Halting problem je bio prvi takav skup koji je mogao biti izgrađen. Entscheidungsproblem, predložen od strane Dejvida Hilberta, pitao je li je efikasna procedura da se odredi koja matematička izjava (kodirana kao prirodni broj) je istinita. Tjuring i Čerč su samostalno pokazali 1930. da je ovaj skup prirodnih brojeva neizračunljiv. Prema Čerč-Tjuringovoj tezi, ne postoji efikasna procedura (sa algoritmom) koja može da obavlja ova izračunavanja.

Ekstenzije izračunljivosti

Relativna izračunljivost

Pojam izračunljivosti funkcije može se relativizovati na proizvoljnom skupu prirodnih brojeva A. Funkcija f je definisana da bude izračunljiva u A (ekvivalentno A-izračunljiva ili izračunljiva u odnosu na A) kada se zadovoljava definicija izračunljive funkcije sa modifikacijom koja omogućava pristup kao orakl. Kao i kod koncepta za izračunavanje funkcije relativne izračunljivosti može dati jednake definicije u mnogim različitim modelima obračuna. Ovo se obično postiže dopunom modela izračunavanja sa dodatnom primitivnom operacijom koja pita da li je dat ceo broj član A. Takođe možemo govoriti o f kao izračunljivoj u g identifikacijom sa g grafa.

Teorija više rekurzije

Hiperaritmetička teorija proučava one skupove koji mogu da se izračunaju iz izračunljivih rednih brojeva iteracije u Tjuringovom skoku praznog skupa. Ovo je ekvivalentno skupovima definisanim kao univerzalne i egzistencijalne formule na jeziku drugog reda aritmetike i nekim modelima hiperračunanja. Čak i više opšte teorije rekurzije su proučavale, kao što su teorija E-rekurzije u kojoj svaki skup može da se koristi kao argument na e-rekurzivnoj funkciji.

Hiperračunanje

Iako Čerč-Tjuringova teza navodi da izračunljive funkcije uključuju sve funkcije sa algoritmima, moguće je razmotriti šire klase funkcija koje opuštaju uslove koje moraju da poseduju algoritmi. Oblast hiperračunanja proučava modele računanja koji prevazilaze normalna Tjuringova računanja.

Vidi još

• Izračunljiv broj
• Efektivni metod
• Teorija izračunljivosti
• Teorija izračunljivosti (računarstvo)
• Tjuringov stepen
• Aritmetička hijerarhija
• Hiperračunanje
• Superrekurzivni algoritam
• Samoizračunljiva funkcija

Literatura

• Cutland, Nigel. Computability. Cambridge University Press, 1980.
• Enderton, H.B. (1977). „Elements of recursion theory”. Handbook of Mathematical Logic. North-Holland. str. 527—566. 
• Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
• Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.