Teoria della computazione

La teoria della computazione è quella branca della matematica che si preoccupa di definire quali proprietà possiede uno specifico linguaggio formale. Le principali proprietà ricercate da un linguaggio formale sono:

• La correttezza: ogni volta che un linguaggio formale definisce un enunciato come vero questo enunciato deve effettivamente essere vero.
• La completezza: il linguaggio formale deve essere in grado di estrarre tutti gli enunciati veri, e solo quegli enunciati devono essere veri; se il linguaggio è completo non devono esistere altri enunciati veri al di fuori di quelli precedentemente estratti.
• La terminazione: ogni algoritmo correttamente definito nel linguaggio formale deve terminare sempre in tempo finito.

Non tutte le proprietà sono necessarie: spesso i linguaggi formali hanno solo la prima e la seconda proprietà. In alcune applicazioni ci si accontenta di avere anche solo la prima proprietà che chiaramente è irrinunciabile: senza la prima proprietà si potrebbero avere enunciati chiaramente falsi ma che vengono dichiarati veri dal linguaggio formale, generando contraddizioni.

Nel caso si abbiano tutte le tre proprietà è conveniente cercare di definire la complessità degli algoritmi definiti del linguaggio formale. La complessità è una funzione che stima il numero di passi necessari ad eseguire uno specifico algoritmo.

Voci correlate

• Computazione
• Teoria della complessità computazionale
• Teoria della computabilità
• Teoria della computabilità effettiva

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla teoria della computazione

Collegamenti esterni

• Fabrizio Luccio, Computazione, teoria della, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• (EN) Opere riguardanti Theory of Computation, su Open Library, Internet Archive.
• (EN) Algorithms, theory of / Mathematical theory of computation, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.