La teoria della computazione

La teoria della computazione è un ramo dell'informatica e della matematica che si occupa di comprendere quali problemi possono essere risolti con un algoritmo (ovvero sono computabili) e come queste soluzioni si relazionano alla complessità computazionale, cioè alla quantità di risorse (tempo, spazio) necessarie per trovare la soluzione.

Si articola principalmente in tre aree:

• Teoria degli automi
  La teoria degli automi studia i modelli matematici di computazione, come gli automi finiti, gli automi a pila, e le macchine di Turing. Questi modelli variano in base alla loro potenza computazionale. La teoria degli automi fornisce le basi per comprendere i linguaggi di programmazione e il design dei compilatori.

  Ad esempio, gli automi finiti sono utili per riconoscere pattern e linguaggi regolari, mentre le macchine di Turing, un modello più potente, sono capaci di simulare qualsiasi algoritmo di calcolo.

• Teoria della complessità computazionale
  La teoria della complessità computazionale indaga la difficoltà intrinseca dei problemi computazionali, classificandoli in base alle risorse necessarie per risolverli, come il tempo (complessità temporale) e lo spazio (complessità spaziale). Problemi come P vs. NP interrogano se ogni problema per cui una soluzione può essere verificata rapidamente (in tempo polinomiale, NP) possa anche essere risolto rapidamente (in tempo polinomiale, P). Questa area della teoria della computazione cerca di categorizzare e comprendere i limiti della computabilità e dell'efficienza degli algoritmi.
• Teoria della calcolabilità
  La teoria della calcolabilità si concentra su quali problemi sono computabili, cioè quali problemi possono essere risolti mediante procedimenti algoritmici. Fondamentalmente, esplora la distinzione tra problemi decidibili (per i quali esiste un algoritmo che trova una soluzione in un tempo finito) e problemi indecidibili (per i quali non esiste tale algoritmo). Un esempio famoso di problema indecidibile è il problema dell'arresto, che chiede se esista un algoritmo capace di determinare, data una descrizione di un programma e un input, se il programma terminerà o continuerà a eseguire all'infinito.

Oltre a queste aree principali, la teoria della computazione interagisce e si sovrappone con altri campi, come la logica matematica, l'algebra, e la teoria dei grafi, fornendo strumenti fondamentali per l'informatica teorica, la sicurezza dei dati, l'intelligenza artificiale, l'analisi degli algoritmi, e molto altro.  Non solo cerca di risolvere problemi pratici legati al calcolo ma cerca anche di rispondere a domande fondamentali sulla natura e i limiti del calcolo stesso.