PARTEA II-a. AUTOMATE INFINITE. CALCULABILITATE — Cap. 6. Funcții recursive
Vom prezenta în continuare o altă formulare a calculabilității efective sub forma noțiunii de funcție recursivă. Se va arăta că această teorie definește aceeași clasă de proceduri ca și mașinile Turing.
Noțiunile ce vor fi prezentate au apărut independent de lucrările lui Turing și ale lui Church. Ulterior s-a constatat însă că aceste noțiuni conduc la aceeași clasă de proceduri efective, ceea ce constituie un argument în plus pentru a demonstra valabilitatea tezei lui Turing.
Studiul funcțiilor recursive cu ajutorul cărora vom da o nouă formulare a calculabilității va conduce și la câteva observații interesante pentru programele destinate calculatoarelor.
