Introduzione allo studio dell'informatica teorica: differenze tra le versioni

La teoria della computabilità si occupa esclusivamente dell'esistenza di un algoritmo e prescinde completamente dalle sue prestazioni, ossia non bada al modo in cui l'algoritmo in questione impiega le risorse a sua disposizione; questi aspetti saranno invece l'oggetto dello studio della teoria della complessità.

 

In generale l'esistenza di un algoritmo non è sufficiente per renderlo utilizzabile: é possibile che richieda un quantitativo ingente di risorse o che fornisca i risultati in tempi troppo lunghi.