Introduzione allo studio dell'informatica teorica: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
Riga 12:
 
=Cenni storici sull'informatica teorica=
L'informatica teorica è una disciplina che studia il concetto di computazione e ci si potrebbe riferire ad essa con il nome di teoria della computazione, come accade ancora oggi in diverse università britanniche e statunitensi.
DA COMPLETARE
 
Sebbene lo studio di alcuni degli argomenti cardine dell'informatica teorica risalgano a qualche millennio fa, lo studio sistematico ed organico della disciplina avviene da meno di un secolo.
 
Contrariamente ad altre materie, dove la storia delle origini si perde molto indietro nel tempo o è particolarmente sfumata, nel caso dell'informatica teorica tutti riconoscono l'esistenza di un momento scatenante: nel 1928 David Hilbert formula il famoso ''Entscheidungsproblem'', in italiano ''problema di decisione'', con l'intento di sondare i limiti associati alle applicazioni della logica matematica.
 
Nel giro di otto anni viene pubblicata una serie di lavori che consentono 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, gettano qualche dubbio sul fatto che lo si possa risolvere positivamente. Successivamente, nel 1936 Alonzo Church ed Alan Turing pubblicano indipendentemente due differenti risultati che avversano il problema di decisione.
 
I loro articoli daranno 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.
 
=Il contesto della disciplina=