kiszámítható függvény

Kapcsolódó fogalmak: 
kezelhetetlenség
Kapcsolódó fogalmak: 
Turing-automata
Kapcsolódó fogalmak: 
Church–Turing-tézis
Rövid szöveges bemutatás: 
A kiszámítható függvény fogalma gyakorlatilag megegyezik a kezelhetőség vizsgálatával. A kérdés maga az, hogy mikor tekinthető kiszámolható valami. Ha több évszázadon keresztül kell futnia az algoritmusnak de a végén képes értelmes választ adni a bemenetre, akkor az is kiszámíthatónak minősül vagy csak azok amelyek valamilyen rövidebb időkorláton belül tudnak végezni? A kiszámíthatóság fontos jellemző, azonban az időkorlát feladattól és egyéntől is függ, így inkább arra próbál választ adni, hogy a függvény (algoritmus), képes lesz-e valaha is értelmes választ adni vagy sem. A Church–Turing-tézis azt mondja ki, hogyha egy függvény kiszámítható akkor egy Turing-automata képes kiszámolni. Általában ezt a kissé absztrakt definíciót szokták alkalmazni.