PARTE II. AUTOMI INFINITI. CALCOLABILITÀ — Cap. 6. Funzioni ricorsive
Presenteremo di seguito un’altra formulazione della calcolabilità effettiva sotto forma della nozione di funzione ricorsiva. Si mostrerà che questa teoria definisce la stessa classe di procedure delle macchine di Turing.
Le nozioni che saranno presentate sono apparse indipendentemente dai lavori di Turing e di Church. Successivamente si è però constatato che tali nozioni conducono alla stessa classe di procedure effettive, il che costituisce un ulteriore argomento per dimostrare la validità della tesi di Turing.
Lo studio delle funzioni ricorsive, per mezzo delle quali daremo una nuova formulazione della calcolabilità, condurrà anche ad alcune osservazioni interessanti per i programmi destinati ai calcolatori.
