Funzione calcolabile: differenze tra le versioni

Versione delle 22:41, 19 lug 2005

Versione delle 02:15, 28 lug 2005

Riga 1:

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]].

#REDIRECT [[Funzione ricorsiva]]

Secondo la (indimostrabile) [[tesi di Church-Turing]], le funzioni calcolabili corrispondono alle [[funzione ricorsiva|funzioni ricorsive]], e quindi a tutti i [[Turing equivalenza|modelli di calcolo equivalenti]].

== Proprietà ==

Una funzione calcolabile è in generale una [[funzione parziale]]

:<math>f:\subseteq \mathbb{N} \to \mathbb{N}</math>

Secondo la (indimostrabile) [[tesi di Church-Turing]], la classe delle funzioni calcolabili è equivalente alla classe delle funzioni definite da

* le [[funzione ricorsiva|funzioni ricorsive]]

* il [[lambda calcolo]] di Church

* gli [[algoritmo di Markov|algoritmi normali di Markov]]

Alternativamente esse possono essere definite come quelli algoritmi calcolabili da

* le [[macchina di Turing|macchine di Turing]]

* i [[sistemi di Post|sistemi combinatori di Post]]

* le [[macchina a registri|macchine a registri elementari]]

''Si veda l'articolo completo sulla [[Turing equivalenza]]''.

[[Categoria:Teoria della computazione]]

[[en:Computable function]]