Formalisation du concept de calculabilité effective

Abstract

Une fonction sera dite calculable s'il existe un processus mécanique calculant la valeur de cette fonction pour des arguments quelconques. Cette phrase contient sans doute plusieurs points obscurs que nous nous proposons d'éclaircir dans ce mémoire. Les processus mécaniques qui seront étudiés seront de deux ordres. D'abord des processus du type algorithmique tels que définis par Markov et Turing et, ensuite, les systèmes d'équations, particulièrement les systèmes bâtis par Herbrand, OBdel et Church. A cette fin nous avons divisé ce mémoire en cinq chapitres. Après un court aperçu historique et l'introduction de la notation et de quelques notions élémentaires, nous aborderons au chapitre I la notion de fonction récursive. Nous donnerons alors les définitions de fonction et de prédicat récursifs, ainsi que quelques exemples de fonctions récursives qui seront très utiles pour la suite de ce mémoire. Au chapitre II sera donnée une définition formelle de la calculabilité, définition qui repose sur le concept de preuve d'une équation à partir d'un système d'équations. Cette caractérisation formelle de la calculabilité, due à Herbrand et CBdel, engendre une classe de fonctions qui sera démontrée identique à la classe des fonctions récursives. Nous étudierons au chapitre suivant le concept d'algorithme et la définition formelle que Markov en a donnée. Nous verrons que la classe des fonctions qui peuvent être calculées au moyen d'un tel algorithme peut aussi être identifiée a la classe des fonctions récursives. Au chapitre IV, nous donnerons une autre spécification formelle du concept d'algorithme. Cette spécification est due à Turing qui a construit certaines machines abstraites connues depuis lors sous le nom de machines de Turing. Après avoir défini le sens de fonction calculable au sens de Turing à l'aide d'un tel algorithme, nous démontrerons que toutes les fonctions calculables au sens de Turing sont partiellement calculables au sens de Markov et réciproquement. Nous aurons donc démontré que la classe des fonctions calculables au sens de Turing est la classe des fonctions semi-récursives. Nous établirons ensuite au chapitre suivant les bases du À-calcul défini par Church, Nous verrons que la classe des fonctions dérivables dans le À-calcul est la classe des fonctions récursives. En guise de conclusion, nous donnerons un aperçu de la thèse de Church qui affirme que; "La classe des fonctions effectivement calculables est la classe des fonctions récursives".