Un límite formal dentro de un lenguaje lógico o fragmento dado a partir del cual distinciones semánticas o propiedades adicionales no pueden expresarse sin alterar el lenguaje (añadiendo cuantificadores, predicados o características de orden superior) o sin incurrir en mayor complejidad computacional.

Principio

Los límites de expresividad surgen de restricciones sintácticas e invariantes (por ejemplo, propiedades de cierre o preservación bajo homomorfismos, bisimulación o indistinguibilidad de Ehrenfeucht-Fraïssé) que impiden que el lenguaje discrimine ciertas configuraciones semánticas.

Demostración

La lógica de primer orden en grafos finitos no puede expresar 'conectividad' ni la propiedad 'el dominio es finito' de manera invariante para grafos de tamaño arbitrario; esta incapacidad es una barrera de expresividad que obliga a usar clausura transitiva, lógicas de punto fijo o cuantificación de segundo orden para capturar dichas propiedades.

Aplicación incorrecta

Interpretar una barrera de expresividad como una imposibilidad ontológica absoluta en lugar de una limitación relativa al sintaxis o a la clase de modelos elegida; o usar la existencia de una barrera para alegar dureza computacional sin separar la complejidad descriptiva de la algorítmica.

Consecuencia

Identificar una barrera de expresividad motiva ampliar el lenguaje (añadir operadores como clausura transitiva o contaje) o restringir la clase de modelos (trabajar sobre estructuras ordenadas o de ancho de árbol acotado) para obtener las distinciones necesarias, y organiza teoremas de clasificación y resultados de cota inferior en complejidad descriptiva.

Inversión

Eliminar o relajar las restricciones sintácticas (por ejemplo añadiendo cuantificadores de segundo orden, operadores de punto fijo o predicados de cardinalidad) puede romper la barrera y permitir definir la propiedad antes inexprimible; a la inversa, probar una barrera insalvable dentro de un marco extendido revela límites más profundos.

Límite

Las barreras de expresividad son siempre relativas a una lógica, firma y clase de estructuras especificadas; no afirman por sí mismas nada sobre la factibilidad de calcular una propiedad ni sobre semánticas fuera del marco formal elegido.

Tensión semántica

Existe tensión entre expresividad y tratabilidad: las lógicas más ricas superan barreras pero suelen aumentar la complejidad, mientras que los lenguajes más débiles mantienen tratabilidad pero encuentran barreras; también hay tensión entre concisión (descripciones más breves) y expresividad pura (existencia de alguna fórmula).

Síntesis

Una barrera de expresividad señala dónde un lenguaje formal elegido agota su poder discriminatorio: es una obstrucción formal y relativa, determinada por invariantes sintácticos y consideraciones sobre la clase de modelos, que indica si conviene extender el lenguaje, adaptar los modelos o aceptar la limitación.