Introduzione allo studio dell'informatica teorica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 18:
Contrariamente ad altre materie, dove la storia delle origini si perde molto indietro nel tempo o è particolarmente sfumata, nel caso dell'informatica teorica esiste un evento scatenante: nel 1928 David Hilbert formulò il cosiddetto ''Entscheidungsproblem'', in italiano ''problema di decisione''; sinteticamente il problema consiste nel valutare se, a partire da un insieme di assiomi e da una proposizione matematica, esiste una procedura che permette di decidere meccanicamente se la proposizione può essere dedotta dagli assiomi oppure no.
Nel giro di otto anni venne pubblicata una serie di lavori che consentirono di rispondere negativamente allo stimolo proposto da Hilbert: i teoremi di incompletezza di Gödel, pubblicati nel 1931, pur non essendo direttamente collegati alla soluzione del problema di decisione
I loro articoli diedero inizio allo sviluppo di due formalismi per la rappresentazione della computazione: il <math>\lambda</math> calcolo di Curch e la macchina di Turing, oggi conosciuti come due tra i formalismi massimi.
| |||