Tesis de Church–Turing

Una afirmación fundacional informal que sostiene que toda función que pueda ser calculada por un procedimiento finito y mecánico (un algoritmo efectivo) puede ser calculada por una máquina de Turing; identifica la noción intuitiva de computabilidad algorítmica con la computabilidad por Turing.