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,[senza fonte] ma esse corrispondono all'intuitivo concetto di "problema che può essere calcolato", e quindi di algoritmo.

Secondo la (non ancora dimostrata) tesi di Church-Turing, le funzioni calcolabili corrispondono alle funzioni ricorsive, e quindi a tutti i modelli di calcolo equivalenti.

Proprietà[modifica | modifica wikitesto]

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

Alternativamente esse possono essere definite come quelli algoritmi calcolabili da

Voci correlate[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica