Funzione calcolabile

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 (non ancora dimostrata) tesi di Church-Turing, la classe delle funzioni calcolabili è equivalente alla classe delle funzioni definite da

Alternativamente esse possono essere definite come gli algoritmi calcolabili da

Voci correlate

modifica

Collegamenti esterni

modifica
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica