Rappel: Machine RAM

L'exécution d'un programme sur une instance de machine RAM

Pour décrire l'exécution d'un programme, on donne quelques définitions de manière à formaliser les idées assez intuitives liées au déroulement d'un programme.

Définition: On notel'état des variables d'un programme P, c'est une liste d'équation de la forme V=m, où V est une variable et m un nombre entier non négatif. Cette liste décrit l'ensemble des variables.

Définition: L'état d'un programme P de longueur n (ie avec n instructions) est une paire (i,) avec 1in et un état des variables de P.

Définition: Un calcul P est une liste d'états de P noté S1, S2, S3,....Sk tels que Si+1 est le successeur de Siet Sk est un état terminal.

ie S_i est l'état des variables à la ligne d'instruction numéro i.

Ensembles Calculables, Fonction calculables

Soit P un programme sur une instance de machine RAM utilisant les variables X₁,X₂, X₃ ...X_n (n1) et soient r₁, r₂, ...r_m des nombres données. On forme l'état des variables par les équations:

X₁=r₁,X₂=r₂, X₃=r₃, ...,X_m=r_m

Y=0

Z_i=0 pour tous les Z_i dans P

Soit l'état initial S₁=(1,). Deux cas sont possibles:

1. Il existe un calcul S₁, S₂, S₃,....S_k de P commencant par S₁. Dans ce cas notons _P^(m)(r₁, r₂, ...r_m) la valeur de Y dans l'état terminal S_k.

2.Il n'existe pas de calcul commencant par S₁. Dans ce cas _P^(m)(r₁, r₂, ...r_m) n'est pas définie.

Définition: Pour tout programme P, et m1, la fonction P(m)(r1, r2, ...rm) est dite calculée par P.

Théorème: Un ensemble E est calculable si est seulement si E et Ec sont récurssivement énumérable.

Note: E_c représente l'ensemble complémentaire de E.

Théorème: Si E est calculable alors E est récurssivement énumérable.

Soit E un ensemble. Un prédicat est une fonction dont les valeurs osnt prises dans l'ensemble {VRAI,FAUX}. Par exemple l'ensemble des prédicats définis sur les naturels est donc : {N^k {VRAI,FAUX} | k0}. On définit ici un prédicat P_E:

P_E(x) <=> x E

Les prédicats sont des fonctions totales. Ainsi

P_E: E={x| P(x)=1}

Définition: L'ensemble E est dit calculable si PE est calculable.

Définition: Une fonction est dite calculable si elle est partiellement calculable et totale sur Nn où n est le nombre de variable de la fonction.