A metamatematikában, a matematikai logikában és a számíthatóságelméletben a hatékony módszer vagy hatékony eljárás olyan véges idő alatt végrehajtható, determinisztikus eljárás, amely egy adott problémakörbe tartozó feladat megoldására szolgál. A szakirodalomban gyakran mechanikus módszernek vagy mechanikus eljárásnak is nevezik.Azokat a függvényeket, amelyekhez létezik hatékony módszer, hatékonyan kiszámítható függvényeknek nevezzük.
Definíció Formálisan egy módszer akkor tekinthető hatékonynak egy adott problémakör esetében, ha az alábbi feltételek teljesülnek:
Az eljárás véges számú, egyértelműen meghatározott és pontos utasításból áll. Amennyiben az eljárást a saját problémakörébe tartozó feladatra alkalmazzuk: mindig véges számú lépés után befejeződik (terminál), minden esetben helyes eredményt szolgáltat. Elméletileg egy ember is végre tudja hajtani, kizárólag íróeszköz és jegyzetpapír segítségével. A sikeres végrehajtáshoz nincs szükség kreativitásra vagy különleges belátásra; elegendő az utasítások pontos és következetes követése.The Cambridge Dictionary of Philosophy, effective procedure
Egyes definíciók további követelményként előírják, hogy az eljárás ne adjon vissza érvényesnek tűnő eredményt olyan esetekben, amikor a bemenet nem tartozik a meghatározott problémakörbe. Ez a megszorítás szűkíti azoknak a problémaköröknek a halmazát, amelyekhez hatékony módszer rendelhető.
Algoritmusok Egy függvény értékeinek meghatározására szolgáló hatékony módszert algoritmusnak nevezzük.
Az algoritmus olyan lépések sorozata, amely pontosan meghatározza, hogyan kell egy adott feladatot megoldani. Az algoritmusok alapvető szerepet játszanak az informatikában és a számítástudományban, mivel minden számítógépes program működése valamilyen algoritmus végrehajtásán alapul.
Kiszámítható függvények A hatékony kiszámíthatóság fogalmának formális meghatározására több, egymástól független megközelítés született. Ezek közé tartoznak:
az általánosan rekurzív függvények elmélete, a Turing-gépek modellje, a λ-kalkulus.
Később bebizonyították, hogy ezek a különböző modellek azonos számítási képességgel rendelkeznek, vagyis ugyanazokat a függvényeket képesek kiszámítani. Az általuk leírt fogalmat rekurzív, illetve effektív számíthatóságnak nevezzük.
Church–Turing-tézis A Church–Turing-tézis szerint az effektíven kiszámítható függvények és a rekurzívan kiszámítható függvények köre megegyezik. Másképpen fogalmazva: minden olyan számelméleti függvény, amelyhez létezik hatékony eljárás, egy Turing-gép segítségével is kiszámítható.
Fontos hangsúlyozni, hogy a Church–Turing-tézis nem matematikai tétel, hanem egy alapvető elméleti állítás a számítás természetéről. Emiatt matematikai bizonyítással nem igazolható, ugyanakkor a különböző számítási modellek egyenértékűsége erős alátámasztást nyújt számára.
Megjegyzések
Jegyzetek
Fordítás
Kapcsolódó szócikkek Rekurzió
Kategória:Alkalmazott matematika