Ефективни метод

Ефективни метод (такође познат и као процедура одлучивања или ефективна процедура) за класу проблема је метод чији сваки корак се може описати као механичка операција, и који ако се строго прати, онолико дуго колико је потребно, увек:

• даје неки одговор, и никад се не деси да не да никакав одговор;
• увек даје тачан одговор, а никад не даје нетачан одговор;
• увек завршава након коначног броја корака, никад му није потребан бесконачан број корака;
• ради за све инстанце проблема из одговарајуће класе.

Ефективни метод за рачунање вредности функције је алгоритам; функције које имају ефективни метод се понекад називају ефективно израчунљиве.

Неколико независних напора за формалну карактеризацију ефективне израчунљивости је довело до више различитих предлога дефиниција (општа рекурзија, Тјурингове машине, λ-калкулус) за које је касније показано да су еквивалентне; појам који ове дефиниције дају је познат као (рекурзивна) израчунљивост.

Черчова теза гласи да се ова два појма поклапају: свака функција теорије бројева која је ефективно израчунљива је рекурзивно израчунљива. Черчова теза није математички исказ и не може се доказати математичким доказом.

Даље разјашњавање израза ефективни метод може да укључи захтев да, када је проблем изван класе проблема за који је метод начињен, он се зауставља или упада у бесконачну петљу без заустављања, али не сме да врати одговор као у случају када је проблем из одговарајуће класе проблема.

Суштинска особина ефективног метода је да он не захтева никакву креативност од особе или машине која га извршава.

Види још

• Проблем одлучивања
• Функцијски проблем

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