Une relation comparant deux langages ou formalismes formels selon laquelle l’un est dit au moins aussi expressif que l’autre lorsqu’il peut définir ou simuler toutes les propriétés définissables dans le second.

Principe

L’expressivité se mesure par la définissabilité ou la simulation fidèle : L1 est au moins aussi expressif que L2 s’il existe un encodage ou une interprétation systématique qui associe à chaque propriété définissable en L2 une propriété définissable en L1 ; cela définit en général un préordre (réflexif, transitif) sur les langages.

Démonstration

La logique propositionnelle est strictement moins expressive que la logique du premier ordre car certaines propriétés de la structure (par exemple « il existe deux éléments distincts ») sont exprimables en premier ordre mais pas propositionnellement ; de même, de nombreux cadres modaux sont moins expressifs que le fragment de la logique du premier ordre obtenu par la traduction standard des formules modales en formules du premier ordre sur les cadres.

Mauvaise application

Confondre l’expressivité relative avec la décidabilité, la complexité ou la concision : conclure par exemple qu’un langage plus expressif est nécessairement indécidable, ou confondre expressivité et brièveté des formules.

Conséquence

Quand un langage est au moins aussi expressif qu’un autre, des méta–résultats, des résultats de définissabilité et certaines distinctions sémantiques peuvent être transférés via l’encodage ; cela oriente le choix du formalisme pour la spécification et l’analyse.

Inversion

La relation inverse met en évidence une inexpressivité stricte : L1 est moins expressif que L2 lorsqu’il existe des propriétés définissables en L2 que aucun encodage en L1 ne peut capturer, montrant des écarts qualitatifs entre langages.

Limite

S’applique aux langages formels et formalismes munis d’une notion claire de définissabilité ou de satisfaction ; elle ne compare pas directement les performances d’implémentation, la complexité de recherche de preuves ou la concision pragmatique sauf si ceux‑ci font explicitement partie du critère de définissabilité.

Tension sémantique

Concurrence avec des notions comme la décidabilité et la concision : un langage plus expressif peut sacrifier la décidabilité ou exiger des formules plus longues, de sorte que l’expressivité doit être pondérée par des considérations algorithmiques et pratiques.

Synthèse

L’expressivité relative est le préordre sur les formalismes induit par l’existence d’encodages ou de simulations systématiques qui préservent la définissabilité ; il identifie quand un langage peut capturer fidèlement les ressources descriptives d’un autre en signalant les compromis avec la décidabilité et la complexité.