Teoria Della Computazione: Branca della logica matematica e dell'informatica teorica
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
Altri progetti
Wiki 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.
This article uses material from the Wikipedia Italiano article Teoria della computazione, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Il contenuto è disponibile in base alla licenza CC BY-SA 4.0, se non diversamente specificato. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Italiano (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.