Funzione calcolabile: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: aggiungo template {{Collegamenti esterni}} (ref) |
Corretto: "Le funzioni calcolabili sono l'analogo formale della nozione intuitiva di algoritmo, nel senso che una funzione è calcolabile se esiste un algoritmo che può svolgere il compito della funzione stessa, cioè se dato un input del dominio della funzione, questa è in grado di restituire il corrispondente output. " |
||
Riga 1:
{{F|matematica|dicembre 2015}}
Le '''funzioni calcolabili''' sono il principale oggetto di studio della [[teoria della calcolabilità]].
Secondo la (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]].
| |||