Au départ il y a un langage L d'opérateurs d'arité fixé qui est par exemple :
L = {x, y, s(.), r(.), f(.,.), g(.,.)}
A partir de cet ensemble d'opérateurs, on peut construire d'autres opérateurs, mais tant qu'on ne les aura pas nommés, on ne les appellera pas opérateur mais simplement formule, la formule de leur définition. Et une formule est un programme. Il est composé d'opérateurs de L selon un mode de construction :
1) Composition close d'opérateurs, exemple : f(s(x),y)
2) Composition terminale-close d'opérateurs, exemple : f(f(y,.),.)
3) Compositions parallèles d'opérateurs, exemple : f(s,g(r,s))
4) Composition close d'opérateurs avec numérotation des variables, exemple : fs1gr1s1
5) Composition classique d'opérateurs : (u,v)-->f(v,s(u))
....
Et d'autres modes de construction sont envisageables, voir "la composition des opérateurs". Par exemple la composition parallèle f(s,g(r,s)) constitue une formule de L permettant de définir un nouvel opérateur que l'on peut nommer par v = f(s,g(r,s)), et qui possède une arité égale à 1. De même le programme fs1gr1s1 écrit en logique polonaise avec numérotation des variables, constitue une formule de L d'un autre type, et permet de définir un nouvel opérateur w = fs1gr1s1 qui est identique à v sauf en terme de complexité ou de méthode de calcul.
L est un ensemble d'opérateurs générateurs, et selon un mode de construction choisi, il engendre un ensemble de programmes qui, une fois nommés, sont des nouveaux opérateurs. Dans l'exemple précédant, l'opérateurs v est dit constructible par L, ou simplement L-constructible (contraction à l'anglaise), et cette propriété se note ainsi :
L |- v
On utilise le symbole de démonstration, car en logique intuissionniste, dire que L construit v, signifie que L démontre v.
On définie la complexité d'une formule comme égale à la somme des complexités de chaque opérateur apparaissant dans la formule. Et on note c(F) la complexité de la formule F. Voici deux exemples pour deux types de formules :
c("f(s,g(r,s))") = c("f") + c("s") + c("g") + c("r") + c("s").
c("fs1gr1s1") = c("f") + c("s") + c("1") + c("g") + c("r") + c("1")+ c("s") + c("1").
Les guillements sont nécessaires pour signifier que l'on s'interesse à la forme de la formule, et non à ce qu'elle vaut dans l'espace des opérateurs L-constructibles. C'est à dire qu'elle ne doit pas être remplacé par une autre formule ou un autre opérateur qui lui serait égale dans l'espace des opérateurs L-constructibles.
L'ensemble générateur, s'il ne précise pas de poid pour la complexité de ses éléments, est supposé composé d'éléments d'égale complexité et dont la complexité servira d'étalon. Parceque s'il en était autrement, il faudrait le justifier, et que délors en l'absence de justification, l'unité est alors canonique.
On pose arbitrairement un ensemble A d'opérateurs, appelé ensemble générateur. Les opérateurs appartenant à A ont par définition une complexité égale à 1. On définie le langage associé à cet ensemble, en nommant chacun des opérateurs de A. Le langage doit également préciser l'arité des opérateurs. La différence qui existe entre A et la langage associé correspond à la différence qui existe en le signifié et le signifiant. Un élément de A est un opérateur concret c'est à dire une fonction totalement calculable, une machine de turing sûr de donner un résultat en un temps finie, alors que le langage associé ne contient que le nom de celui-ci et son arité.
Par exemple posons :
A = {f(s,g(r,s)), g(s,r), r}
On nomme arbitrairement les opérateurs qui ne sont pas déja nommés : v = f(s,g(r,s)) et w = g(s,r). Voici le langage obtenue. Le langage L associé à A est égale à :
L = {r(.), v(.), w(.,.)}
Souvent on ne fait pas la différence entre les deux. Plus exactement on laisse le soin au contexte de lever l'ambiguité.
On définie la complexité d'un opérateur relativement à un ensemble générateur A (et selon un type de formule), comme égale à celle de la formule de complexité minimale appartenant au langage associé à A et produisant cet opérateur, et la complexité sera dite infinit s'il n'existe pas de telle formule. Un operateur u est dit A-constructible ssi il existe une formule appartenant au langage associé à A le calculant, et cette propriété se note ainsi :
A |- u
Et on note la complexité de u relative à A par :
cA(u)
On définie la relation |- entre deux ensembles finis d'opérateurs. A|-B signifie que A peut construire B, c'est à dire que tous les opérateurs de B peuvent être obtenu par une formule composé exclusivement d'opérateurs appartenants à A (et selon un mode de constrution de formule préalablement choisi)
Si un ensemble A d'opérateurs possède la propriété suivante :
∀x∈A (A-{x})|-A
Alors l'ensemble A est minimal et est appelé axiomatique.