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 vere 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 ad 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à e 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.

---

|