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.
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.
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à
Una funzione calcolabile è in generale una funzione parziale
Secondo la (non ancora dimostrata) 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
- le macchine di Turing
- i sistemi combinatori di Post
- le macchine a registri elementari
Voci correlate
Collegamenti esterni
- Funzione calcolabile, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) computable function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Funzione calcolabile, su MathWorld, Wolfram Research.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.