Funzione calcolabile: differenze tra le versioni

Versione delle 22:41, 19 lug 2005

Versione attuale delle 11:12, 2 nov 2023

(25 versioni intermedie di 22 utenti non mostrate)

Riga 1:

{{F|matematica|dicembre 2015}}

#REDIRECT [[Funzione ricorsiva]]

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]].

== Proprietà ==

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

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

Secondo la (non 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]]

* il [[lambda calcolo]] di Church

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

Alternativamente esse possono essere definite come gli 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==

*[[Turing equivalenza]]

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{portale|matematica}}

[[Categoria:Teoria della calcolabilità]]