calcolabilita
calcolabilità
La teoria che studia la possibilità di calcolare una funzione dagli interi sugli interi mediante un modello astratto di computazione come per es. la macchina di Turing. Oltre al suo interesse teorico, l’importanza di questa disciplina è legata alla determinazione dei limiti alla risolubilità di un problema mediante un calcolatore. Le basi teoriche furono poste nei primi decenni del Novecento come conseguenza degli studi sugli insiemi infiniti sviluppatisi negli anni precedenti. Infatti gli algoritmi di calcolo appartengono a un insieme infinito numerabile (cioè i cui elementi possono essere messi in corrispondenza biunivoca con i numeri interi) mentre le funzioni appartengono a un insieme non numerabile: questo implica che devono esistere funzioni cui non corrisponde alcun algoritmo di calcolo, ovvero problemi non risolubili mediante algoritmi. Il primo di questi problemi, scoperto da Alan Turing nel 1936, può essere formulato in termini intuitivi affermando che non esiste algoritmo che, presi come dati d’ingresso un altro algoritmo A arbitrario e dati arbitrari D per esso, stabilisca in tempo finito se il calcolo di A su D termina in tempo finito.