calcolabilità

sf. [da calcolare]. In logica matematica, proprietà di una funzione (definita sui numeri naturali) di essere calcolabile in modo meccanico. Ciò avviene quando esiste un insieme finito di regole che possono essere comprese e applicate da una macchina e in base alle quali sia possibile, dato un argomento, raggiungere in un numero finito di passi il valore della funzione; oppure, nel caso che la funzione non sia definita per quell'argomento, la macchina procede indefinitamente.