Funzione calcolabile: differenze tra le versioni

Versione delle 21:35, 25 feb 2013

Versione delle 10:19, 8 lug 2014

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}}non ancora dimostrata) [[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à ==