Étant donné que les langues officielles seules n'ont pas de sémantique, d'autres constructions formelles sont nécessaires pour la spécification formelle de la sémantique du programme.
le jeu d'entrées sur lequel une certaine machine de Turing s'arrête.