Funzione calcolabile: differenze tra le versioni

Versione delle 15:01, 28 dic 2011

Versione delle 22:04, 10 ott 2012

Riga 1:

Le '''funzioni calcolabili''' sono il principale oggetto di studio della [[teoria della calcolabilità]]. {{cn|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 ({{cn|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à ==