Funzione calcolabile
Da Wikipedia, l'enciclopedia libera.
Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità. Non è possibile dare una definizione formale delle funzioni calcolabili, ma esse corrispondono all'intuitivo concetto di "problema che può essere calcolato", e quindi di algoritmo.
Secondo la (indimostrabile) tesi di Church-Turing, le funzioni calcolabili corrispondono alle funzioni ricorsive, e quindi a tutti i modelli di calcolo equivalenti.
[modifica] Proprietà
Una funzione calcolabile è in generale una funzione parziale
Secondo la (indimostrabile) tesi di Church-Turing, la classe delle funzioni calcolabili è equivalente alla classe delle funzioni definite da
- le funzioni ricorsive
- il lambda calcolo di Church
- gli algoritmi normali di Markov
Alternativamente esse possono essere definite come quelli algoritmi calcolabili da
- le macchine di Turing
- i sistemi combinatori di Post
- le macchine a registri elementari
Si veda l'articolo completo sulla Turing equivalenza.
