Calcolabilità

Branca della teoria della computazione che studia quali funzioni o problemi possono essere risolti in linea di principio da un modello di calcolo astratto come la macchina di Turing. Distingue i problemi decidibili da quelli indecidibili, come il celebre problema dell'arresto.