Funzione calcolabile

Template:F 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à

Una funzione calcolabile è in generale una funzione parziale

$f:\mathbb{N}\to \mathbb{N}$

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

• Turing equivalenza

Collegamenti esterni

• Template:Collegamenti esterni