Funzioni, macchine, algoritmi

La teoria della computabilità è un settore della ricerca logico-matematica che studia la nozione di calcolo algoritmico, ossia di calcolo eseguibile in modo meccanico. Essa è nata nel corso degli anni Trenta del Novecento nel contesto delle ricerche sulla logica e sui fondamenti della matematica. Con lo sviluppo dei calcolatori digitali la teoria della computabilità ha poi assunto il ruolo di disciplina dei fondamenti per l´informatica teorica. Attraverso di essa, la sua influenza culturale si è estesa ad ambiti quali l´intelligenza artificiale, le scienze cognitive, la linguistica. Di conseguenza, i risultati di teoria della computabilità si trovano al centro di alcuni dei crocevia più vitali e stimolanti della cultura filosofica e scientifica contemporanea, hanno una vasta portata culturale e sono rilevanti per molte differenti discipline. Questo volume vuole rendere accessibili, con un adeguato livello di approfondimento, i principali risultati della teoria della computabilità ad un pubblico che non disponga necessariamente di una specifica preparazione logico-matematica.