Extrapedia

In Informatica teorica e Matematica, la Teoria del calcolo (o della computazione) è la branca che si occupa di quanto efficientemente i problemi possano essere risolti su un modello computazionale, usando un algoritmo. Il campo è diviso in tre rami principali: teoria e linguaggi degli automi, Teoria della computabilità e Teoria della complessità computazionale, che sono collegati dalla domanda: “Quali sono le capacità e le limitazioni fondamentali dei computer?”. ¹⁾

Al fine di eseguire uno studio rigoroso del calcolo, gli scienziati informatici lavorano con un'astrazione matematica dei computer chiamata modello di calcolo. Gli informatici studiano la macchina di Turing perché è semplice da formulare, può essere analizzata e utilizzata per dimostrare i risultati, e perché rappresenta ciò che molti considerano il più potente modello di calcolo (Tesi di Church-Turing ). ²⁾ Potrebbe sembrare che la capacità di memoria potenzialmente infinita sia un attributo irrealizzabile, ma qualsiasi problema ³⁾ risolto da una macchina di Turing richiederà sempre solo una quantità limitata di memoria. Quindi, in linea di principio, qualsiasi problema che può essere risolto da una macchina di Turing può essere risolto anche da un computer che ha una quantità limitata di memoria.