Church, Alonzo

Matematico e logico-matematico statunitense (Washington 1903 - Hudson, Ohio, 1995), prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, dal 1967 di matematica e filosofia all'univ. di California. Nel 1936 enunciò la proposizione oggi chiamata tesi (o ipotesi o legge) di Ch., la quale afferma che ogni funzione effettivamente calcolabile (cioè ogni predicato decidibile) è ricorsiva generale. Essa ha formulazioni equivalenti nella tesi di Turing, nel principio di Markov di normalizzazione degli algoritmi e nel teorema di completezza di Post. La tesi di Ch. e l'affermazione inversa (cioè ogni funzione ricorsiva è effettivamente calcolabile) precisano la nozione di procedimento effettivo di calcolo nel caso di funzioni di numeri naturali. La tesi di Ch. non si può né dimostrare né confutare, ma solo rendere accettabile con argomenti di carattere sperimentale. Ch. sviluppò anche altre linee di ricerca, quali le relazioni con la logica combinatoria di Curry, le questioni di teoria dei tipi e il λ-calcolo. Tra le opere: The calculi of lambda-conversion (1941) e Introduction to mathematical logic (1956).