Una funzione è un oggetto matematico che pone in corrispondenza due insiemi A e B detti Dominio e Codominio. In particolare per ogni elemento del dominio A è associato un solo elemento del codominio B. Si indica con
f: A → B
oppure
y = f(x), intendendo x ∈ A, y ∈ B.
Una funzione è calcolabile se esiste un algoritmo che prendendo in ingresso i valori x fornisce in uscita gli stessi valori y della funzione.
Un algoritmo è una sequenza finita di istruzioni che deve terminare dopo un tempo finito e un numero finito di eventuali iterazioni; quindi l’insieme di tutti gli algoritmi è numerabile.
Però per ogni funzione calcolabile possono esistere più algoritmi, seppur in numero finito. Anche l’insieme di tutte le funzioni calcolabili è quindi numerabile, però non può essere posto in corrispondenza biunivoca con l’insieme degli algoritmi, quindi la cardinalità è diversa.
Link utili
Dispense del corso di Modelli Simulativi, prof. P.Bouquet, Università di Trento
http://disi.unitn.it/~bouquet/ModelliSimulativi2005/diario.html