Loading AI tools
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.
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
- 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 in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
