Thèse de Church–Turing

Une affirmation fondatrice, informelle, selon laquelle toute fonction calculable par une procédure finie et mécanique (un algorithme effectif) peut être calculée par une machine de Turing ; elle identifie la calculabilité au sens intuitif et algorithmique à la calculabilité par Turing.