CALCULABILITE

La notion intuitive de calcul provient des opérations élémentaires de l’arithmétique et concerne les entiers naturels. Lorsque nous posons une opération et que nous parvenons au résultat, nous avons une idée simple de ce qu’est le calcul effectif. La notion a été utilisée plus ou moins métaphoriquement (par ex., lorsque l’on envisage toute pensée comme un calcul) et étendue (par ex., aux opérations logiques). Dès lors se pose la question d’une définition rigoureuse et formelle de la calculabilité. Dans les années trente de notre siècle, plusieurs définitions ont été proposées. L’une d’entre elles consiste à considérer qu’est effectivement calculable toute fonction calculable par une machine de Turing. La thèse de Church pose que toutes les définitions sont équivalentes à celle de Turing.