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

Contenuto cancellato Contenuto aggiunto
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.
 
Sebbene lo studiol'interesse diper alcuni degli argomenti cardine dell'informatica teorica risalganorisalga 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 diesiste un momentoevento scatenante: nel 1928 David Hilbert formula il famoso ''Entscheidungsproblem'', in italiano ''problema di decisione''; sinteticamente il problema consiste nel valutare se, cona l'intentopartire dida sondareun iinsieme limitidi associatiassiomi allee applicazionida dellauna logicaproposizione matematica, esiste una procedura che permette di decidere se la proposizione può essere dedotta dagli assiomi oppure no.
 
Nel giro di otto anni vienevenne pubblicata una serie di lavori che consentonoconsentirono 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. SuccessivamenteIn seguito, nel 1936 Alonzo Church ed Alan Turing pubblicanopubblicarono indipendentemente due differenti risultati che avversanoavversarono definitivamente il problema di decisione.
 
I loro articoli darannodiedero 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.
 
Sebbene i due formalismi siano equivalenti sul piano logico, la strategia seguita da Alan Turing di immaginare un dispositivo fisico in grado di svolgere computazioni automaticamente spinse i ricercatori a chiedersi se fosse possibile realizzare davvero una macchina.
Qualche tentativo era stato compiuto, con fortune alterne, prima di allora: si ricordano in particolare la macchina analitica di Babbage e soprattutto la macchina di Leibnitz, che aveva introdotto l'impiego del sistema binario nelle calcolatrici.
Il resto è storia recente: l'invenzione dei calcolatori, basati su modelli analoghi a quelli ideati da Turing, ha comportato una rapida evoluzione di tutti i settori coinvolti, con particolare attenzione per l'elettronica e per il software.
 
=Il contesto della disciplina=