CALCULABILITE ET FONCTIONS RECURSTVES

Abstract

Ce travail constitue une introduction à la théorie de la calculabilité . Le contenu est composé de quatres chapitres. Le premier <<Notions sur la calculabilité» présente les notions généreaux de la calculabilité. Le deuxième <<Fonctions et prédicats primitifs récursifs>> donne des définitions formelle des fonctions et prédicats primitifs récursifs et on donnons quelque exemples. Le troisième chapitre est un <<Etude d'une fonction non primitive récursive» on particulions la fonction d'Ackremann. Le dernier chapitre <<Fonctions récursives et machines de Turing» on utilisons un autre modèle du calcul pour étudier les fonctions primitives récursives.