Lo studio della "teoria della computazione", o come viene chiamata all'UniVe, Calcolabilità e Linguaggi Formali, riguarda tre argomenti:
- Complessità
- Calcolabilità
- Automi
La complessità indaga i costi di esecuzione degli algoritmi, in particolare li suddivide in classi, le cui principali sono polinomiale ed esponenziale.
La calcolabilità riguarda quali problemi siano risolvibili da un computer: per esempio, se risolvi un problema la risposta è che si può, ma se per ora non riesci non puoi sapere se il motivo è che non hai elaborato abbastanza oppure se è proprio interminabile.
Gli automi definiscono quali sono le caratteristiche di una macchina in grado di calcolare.