Funzione calcolabile: differenze tra le versioni

Versione delle 14:31, 3 apr 2015

Versione attuale delle 11:12, 2 nov 2023

(5 versioni intermedie di 5 utenti non mostrate)

Riga 1:

{{F|matematica|dicembre 2015}}

Le '''funzioni calcolabili''' sono il principale oggetto di studio della [[teoria della calcolabilità]]. {{cn|Non è possibile dare una definizione formale delle funzioni calcolabili,}} ma esse corrispondono all'intuitivo concetto di "problema che può essere calcolato", e quindi di [[algoritmo]].

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 [[funzione ricorsiva|funzioni ricorsive]], e quindi a tutti i [[Turing equivalenza|modelli di calcolo equivalenti]].

Line 5 ⟶ 6:

== Proprietà ==

Una funzione calcolabile è in generale una [[funzione parziale]]

:<math>f:\subseteq \mathbb{N} \to \mathbb{N}</math>

Secondo la (indimostrabilenon ancora dimostrata) [[tesi di Church-Turing]], la [[Classe (insiemistica)|classe]] delle funzioni calcolabili è equivalente alla classe delle funzioni definite da

* le [[funzione ricorsiva|funzioni ricorsive]]

Line 13 ⟶ 14:

* gli [[algoritmo di Markov|algoritmi normali di Markov]]

Alternativamente esse possono essere definite come quelligli algoritmi calcolabili da

* le [[macchina di Turing|macchine di Turing]]

* i [[sistemi di Post|sistemi combinatori di Post]]

* le [[macchina a registri|macchine a registri elementari]]

==Voci correlate==

''Si veda l'articolo completo sulla [[Turing equivalenza]]''.

*[[Turing equivalenza]]

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{portale|matematica}}

[[Categoria:Teoria della calcolabilità]]