teoria della calcolabilità

La teoria della calcolabilità, della computabilità, o teoria della ricorsione cerca di comprendere cosa può essere effettivamente computato, ovvero quali funzioni ammettono un procedimento di calcolo automatico per ricavarne i valori. L'obiettivo principale è quello di rendere rigorosa (matematicamente formale) l'idea intuitiva di "funzione calcolabile" e scoprire quali siano le possibilità ed i limiti delle cose che ci proponiamo di calcolare. Questa disciplina è comune sia alla matematica che alla computer science. Da una parte l'approccio è quello di approfondire il concetto di calcolabile cercando di individuare le categorie di problemi teoricamente risolvibili e dall'altro mappare questo concetto su cosa i computer sono in grado di elaborare in linea di principio, ovvero senza restrizioni fisiche come, per esempio, costi, tempo, spazio di memoria. Per tali ragioni la teoria della calcolabilità è strettamente legata con la teoria della complessità il cui scopo è quello di vincolare l'idea di calcolabile ai suddetti limiti con particolare attenzione al tempo e allo spazio. Un altro importante aspetto è quello di definire matematicamente il concetto di algoritmo in modo che i programmi possano essere concretamente pensati in termini di oggetti matematici e più precisamente come funzioni che preso un determinato input ritornato un risultato.
Per saperne di più visita Wikipedia.org...