Efektivni metod

Efektivni metod (takođe poznat i kao procedura odlučivanja ili efektivna procedura) za klasu problema je metod čiji svaki korak se može opisati kao mehanička operacija, i koji ako se strogo prati, onoliko dugo koliko je potrebno, uvek:

• daje neki odgovor, i nikad se ne desi da ne da nikakav odgovor;
• uvek daje tačan odgovor, a nikad ne daje netačan odgovor;
• uvek završava nakon konačnog broja koraka, nikad mu nije potreban beskonačan broj koraka;
• radi za sve instance problema iz odgovarajuće klase.

Efektivni metod za računanje vrednosti funkcije je algoritam; funkcije koje imaju efektivni metod se ponekad nazivaju efektivno izračunljive.

Nekoliko nezavisnih napora za formalnu karakterizaciju efektivne izračunljivosti je dovelo do više različitih predloga definicija (opšta rekurzija, Tjuringove mašine, λ-kalkulus) za koje je kasnije pokazano da su ekvivalentne; pojam koji ove definicije daju je poznat kao (rekurzivna) izračunljivost.

Čerčova teza glasi da se ova dva pojma poklapaju: svaka funkcija teorije brojeva koja je efektivno izračunljiva je rekurzivno izračunljiva. Čerčova teza nije matematički iskaz i ne može se dokazati matematičkim dokazom.

Dalje razjašnjavanje izraza efektivni metod može da uključi zahtev da, kada je problem izvan klase problema za koji je metod načinjen, on se zaustavlja ili upada u beskonačnu petlju bez zaustavljanja, ali ne sme da vrati odgovor kao u slučaju kada je problem iz odgovarajuće klase problema.

Suštinska osobina efektivnog metoda je da on ne zahteva nikakvu kreativnost od osobe ili mašine koja ga izvršava.

Vidi još

• Problem odlučivanja
• Funkcijski problem

• S. C. Kleene (1967). Mathematical logic. Reprinted, Dover. 2002. ISBN 978-0-486-42533-7. стр. 233. ff., esp. стр. 231.