Funzione calcolabile: differenze tra le versioni

Versione delle 17:32, 21 giu 2019

Versione attuale delle 11:12, 2 nov 2023

(Una versione intermedia di un altro utente 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 8:

:<math>f: \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]]