Funzione calcolabile

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à

Una funzione calcolabile è in generale una funzione parziale

${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ 

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 gli algoritmi calcolabili da

• le macchine di Turing
• i sistemi combinatori di Post
• le macchine a registri elementari

Voci correlate

• Turing equivalenza

Collegamenti esterni

• Funzione calcolabile, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) computable function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Computable Function, su MathWorld, Wolfram Research.  

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