¿Está terminado CSS Turing?

CSS no es, en la medida en que sé, Turing completo. Pero mi conocimiento de CSS es muy limitado.

  • ¿Está terminado CSS Turing?
  • ¿Alguno de los borradores o comités existentes está considerando las características del lenguaje que podrían permitir la integridad de Turing si no es ahora?

Puedes codificar la Regla 110 en CSS3, por lo que es Turing completa siempre que consideres que un archivo HTML y las interacciones del usuario correspondientes son parte de la “ejecución” de CSS. Una implementación bastante buena está disponible, y otra implementación se incluye aquí:

body { -webkit-animation: bugfix infinite 1s; margin: 0.5em 1em; } @-webkit-keyframes bugfix { from { padding: 0; } to { padding: 0; } } /* * 111 110 101 100 011 010 001 000 * 0 1 1 0 1 1 1 0 */ body > input { -webkit-appearance: none; display: block; float: left; border-right: 1px solid #ddd; border-bottom: 1px solid #ddd; padding: 0px 3px; margin: 0; font-family: Consolas, "Courier New", monospace; font-size: 7pt; } body > input::before { content: "0"; } p { font-family: Verdana, sans-serif; font-size: 9pt; margin-bottom: 0.5em; } body > input:nth-of-type(-n+30) { border-top: 1px solid #ddd; } body > input:nth-of-type(30n+1) { border-left: 1px solid #ddd; clear: left; } body > input::before { content: "0"; } body > input:checked::before { content: "1"; } body > input:checked { background: #afa !important; } input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "1"; } input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fa0; } input:checked + input:checked + input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "0"; } input:checked + input:checked + input:checked + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fff; } input:not(:checked) + input:not(:checked) + input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input::before { content: "0"; } input:not(:checked) + input:not(:checked) + input:not(:checked) + *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input { background: #fff; } body > input:nth-child(30n) { display: none !important; } body > input:nth-child(30n) + label { display: none !important; } 
 

Rule 110 in (webkit) CSS, proving Turing-completeness.

Un aspecto de la exhaustividad de Turing es que su problema de detención es indecidible .

Esto significa que no hay un algoritmo general para determinar si un progtwig CSS terminará de ejecutarse o se repetirá para siempre.

¡Pero podemos derivar tal algoritmo para CSS! Aquí está:

  • Si la hoja de estilo no declara ninguna animación , se detendrá.

  • Si tiene animaciones, entonces:

    • Si cualquier animation-iteration-count es infinite y el selector que contiene coincide en el HTML, no se detendrá.

    • De lo contrario, se detendrá.

Eso es. Como acabamos de mostrar que el problema de detención es decidible para CSS, se deduce que CSS no está completo .

(Otras personas mencionaron IE 6, que permite incrustar expresiones JavaScript arbitrarias en CSS, lo que obviamente agregará completitud a Turing. Pero esa característica no es estándar, y nadie en su sano juicio la usa de todos modos).


Daniel Wagner sacó a colación un punto que me perdí en la respuesta original. Señala que, aunque he cubierto animaciones , otras partes del motor de estilo, como la coincidencia de selector o el diseño, también pueden llevar a la integridad de Turing. Si bien es difícil hacer un argumento formal acerca de estos, trataré de delinear por qué es poco probable que Turing complete.

Primero: los lenguajes completos de Turing tienen alguna manera de volver a introducir datos en sí mismo , ya sea mediante recursión o bucle. Pero el diseño del lenguaje CSS es hostil a esta retroalimentación:

  • @media consultas de @media solo pueden verificar las propiedades del navegador, como el tamaño de la vista o la resolución de píxeles. Estas propiedades pueden cambiar a través de la interacción del usuario o código de JavaScript (por ejemplo, cambiar el tamaño de la ventana del navegador), pero no a través de CSS solo.

  • ::before pseudoelementos ::before y ::after no se consideran parte del DOM , y no se pueden combinar de ninguna otra forma.

  • Los combinadores de selectores solo pueden inspeccionar los elementos anteriores y anteriores al elemento actual, por lo que no se pueden usar para crear ciclos de dependencia.

  • Es posible alejar un elemento cuando pasas el cursor sobre él , pero la posición solo se actualiza cuando mueves el mouse.

Eso debería ser suficiente para convencerlo de que la coincidencia de selectores, por sí sola, no puede ser completa . Pero, ¿qué hay del diseño?

El algoritmo de diseño de CSS moderno es muy complejo, con características como Flexbox y Grid enlodando las aguas. Pero incluso si fuera posible activar un bucle infinito con el diseño, sería difícil aprovechar esto para realizar un cálculo útil. Esto se debe a que los selectores CSS inspeccionan solo la estructura interna del DOM, no cómo estos elementos están distribuidos en la pantalla. Entonces, cualquier prueba de integridad de Turing que use el sistema de disposición debe depender solo del diseño .

Finalmente, y esta es quizás la razón más importante, los proveedores de navegadores tienen interés en mantener el CSS no completo . Al restringir el idioma, los proveedores permiten optimizaciones inteligentes que hacen que la web sea más rápida para todos. Además, Google dedica toda una granja de servidores a buscar errores en Chrome. Si hubiera una forma de escribir un bucle infinito usando CSS, entonces probablemente ya lo habrían encontrado 😉

Según este artículo, no lo es . El artículo también argumenta que no es una buena idea hacerlo uno.

Para citar uno de los comentarios:

Entonces, no creo que CSS esté completo. No hay capacidad para definir una función en CSS. Para que un sistema sea completo, tiene que ser posible escribir un intérprete: una función que interpreta expresiones que denotan progtwigs para ejecutar. CSS no tiene variables que sean directamente accesibles para el usuario; por lo que ni siquiera puede modelar la estructura que representa el progtwig para ser interpretada en CSS.

Turing-completeness no se trata solo de “definir funciones” o “tener ifs / loops / etc”. Por ejemplo, Haskell no tiene “loop”, lambda-calculus no tiene “ifs”, etc …

Por ejemplo, este sitio: http://experthuman.com/programming-with-nothing . El autor usa Ruby y crea un progtwig “FizzBuzz” con solo cierres (sin cadenas, números ni nada de eso) …

Hay ejemplos cuando las personas calculan algunas funciones aritméticas en Scala usando solo el sistema de tipo

Entonces, sí, en mi opinión, CSS3 + HTML es turing-completo (incluso si no se puede hacer un cómputo real con eso sin volverse loco)

El problema fundamental aquí es que cualquier máquina escrita en HTML + CSS no puede evaluar infinitamente muchos pasos (es decir, no puede haber recursión “real”) a menos que el código sea infinitamente largo. Y la pregunta de si esta máquina alcanzará la configuración H en n pasos o menos siempre será responsable si n es finita.

Esta respuesta no es precisa porque mezcla la descripción de UTM y UTM en sí (Máquina universal de Turing).

Tenemos una buena respuesta, pero desde una perspectiva diferente y no muestra directamente defectos en la respuesta superior actual.


En primer lugar, podemos aceptar que los humanos pueden funcionar como UTM. Esto significa que si lo hacemos

 CSS + Human == UTM 

Entonces, la parte de CSS es inútil porque todo el trabajo puede ser realizado por Human que hará la parte de UTM. El acto de hacer clic puede ser UTM, porque no hace clic al azar sino solo en lugares específicos.

En lugar de CSS, podría usar este texto ( Regla 110 ):

 000 -> 0 001 -> 1 010 -> 1 011 -> 1 100 -> 0 101 -> 1 110 -> 1 111 -> 0 

Para guiar mis acciones y el resultado será el mismo. Esto significa este texto UTM? No, esto es solo una entrada (descripción) que otro UTM (humano o computadora) puede leer y ejecutar. Hacer clic es suficiente para ejecutar cualquier UTM.


La parte crítica que falta en CSS es la capacidad de cambiar su propio estado de manera arbitraria, si CSS pudiera generar clics, entonces sería UTM. La argumentación de que sus clics son “inestables” para CSS no es precisa porque la verdadera “manivela” para CSS es Layout Engine que la ejecuta y debería ser suficiente para demostrar que CSS es UTM.

CSS no es un lenguaje de progtwigción, por lo que la cuestión de la turing-completitud no tiene sentido. Si las extensiones de progtwigción se agregan a CSS, como fue el caso en IE6, esa nueva síntesis es una cosa completamente diferente.

CSS es simplemente una descripción de estilos; no tiene ninguna lógica, y su estructura es plana.