computabilità

computabilità In logica matematica, nozione che di solito s’identifica con quella di ricorsività generale, introdotta intorno al 1936 da A.M. Turing e da E.L. Post. Una funzione numerica di n variabili si dice computabile se esiste un algoritmo per cui si possa, con un numero finito di passi, calcolare per ogni ennupla di argomenti il valore assunto dalla funzione.