Funzione calcolabile
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.
|
Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità. 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.
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àModifica
Una funzione calcolabile è in generale una funzione parziale
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
Voci correlateModifica
Collegamenti esterniModifica
- (EN) Funzione calcolabile, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.