Funzione calcolabile: differenze tra le versioni

Versione delle 19:02, 8 set 2017

Versione attuale delle 11:12, 2 nov 2023

(3 versioni intermedie di 3 utenti non mostrate)

Riga 1:

{{F|matematica|dicembre 2015}}

Le '''funzioni calcolabili''' sono il principale oggetto di studio della [[teoria della calcolabilità]]. {{cn|NonLe èfunzioni possibilecalcolabili daresono una definizionel'analogo formale delledella funzioninozione calcolabiliintuitiva di [[algoritmo]],}} manel essesenso corrispondonoche all'intuitivouna concettofunzione diè "problemacalcolabile se esiste un algoritmo che può esseresvolgere calcolato"il compito della funzione stessa, ecioè quindise dato un input del dominio della funzione, questa è in grado di [[algoritmo]]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]].

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

Riga 21:

==Voci correlate==

*[[Turing equivalenza]]

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{portale|matematica}}