¿Está completo CSS Turing?

297

CSS no es, hasta donde sé, Turing completo. Pero mi conocimiento de CSS es muy limitado.

¿Está completo 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?

css turing-complete Adam Davis
fuente

28

Ya está hecho, si usas ie6. Se llaman expresiones CSS, y el consenso es que están horriblemente rotas y son peligrosas. JS incrustado en CSS ...

kibibu

13

@Kibibu - ¡Ay! ¡Borre esa idea de mi cerebro antes de que se pliegue sobre sí misma!

DVK

¿Cómo podría CSS posiblemente ser Turing-complete?

SLaks

1

@DVK: en realidad podrías hacer algunas cosas interesantes con ellos, particularmente en lo que respecta al diseño independiente de la resolución, que todavía son difíciles o extravagantes en CSS sin recurrir a tablas. Creo que si lo hubieran limitado a ser estrictamente un lenguaje de expresión declarativo sin efectos secundarios en lugar de permitir el acceso completo al motor de script, habría sido mejor recibido (y tal vez también si webkit hubiera aparecido primero)

kibibu

55

@SLaks: No subestimes el poder de HTML5 / CSS3 :)

Niklas B.

385

Puede codificar la Regla 110 en CSS3, por lo que se completa con Turing siempre que considere que un archivo HTML apropiado y las interacciones del usuario forman parte de la "ejecución" de CSS. Una muy buena aplicación 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; }

<p><a href="http://en.wikipedia.org/wiki/Rule_110">Rule 110</a> in (webkit) CSS, proving Turing-completeness.</p>

<!-- A total of 900 checkboxes required -->
<input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/><input type="checkbox"/>

Expandir fragmento

Adam Davis
fuente

2

La definición formal (más simple) de Turing Machine es simplemente una tupla de conjunto de estados, conjunto de símbolos, estado inicial, conjunto de estados de aceptación y una función de transición. No hay manivela en ella. Por cálculo queremos decir que alguien necesita aplicar fielmente la función de transición en la cinta, que es exactamente como hacer clic en este caso. Más formalmente, un modelo de cómputo puede verse como un conjunto de reglas que alguien debe seguir para hacer el cómputo. En ese sentido, creo que CSS es Turing-Complete.

John

2

Este fragmento no parece funcionar (Firefox 61). Veo una cuadrícula de casillas vacías; no pasa nada si las marca.

OrangeDog

2

@John "CSS se está completando" me inquieta, pero no tengo ningún problema con "CSS está tan completo como un par de rocas en la playa ". ¿Sería correcta la última afirmación?

Raphael Schmitz

1

@ R.Schmitz no, en ese caso, el humano está eligiendo dónde colocar las rocas, por lo que es el sistema combinado de humano + rocas lo que se está completando. En el ejemplo de CSS anterior, la tecla de tabulación + espacio es un proceso simple de repetición, similar a un circuito de retroalimentación. Entonces, si C ++ se está completando usando hardware de computadora para ejecutar instrucciones, entonces no es

difícil

Aquí hay un CodePen de la Regla 110 que usa la misma solución, más anotaciones y algunos Sass para ayudar a SECAR: codepen.io/laras126/pen/OYvGZj Escribí una publicación de blog que explica los conceptos aquí: notlaura.com/is-css -turing-complete

notlaura

89

Un aspecto de la integridad de Turing es el problema de la detención .

Esto significa que, si CSS está completando Turing, entonces no hay un algoritmo general para determinar si un programa 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 alguno animation-iteration-countes infinite, y que contiene el selector está adaptada en el HTML, entonces no se detenga.
- De lo contrario, se detendrá.

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

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

Daniel Wagner trajo a colación un punto que no entendí en la respuesta original. Señala que si bien he cubierto animaciones , otras partes del motor de estilo, como la coincidencia de selector o el diseño, también pueden conducir a la integridad de Turing. Si bien es difícil argumentar formalmente sobre esto, intentaré describir por qué la integridad de Turing aún es poco probable.

Primero: los idiomas completos de Turing tienen alguna forma de retroalimentar los datos , ya sea a través de la recursión o el bucle. Pero el diseño del lenguaje CSS es hostil a esta retroalimentación:

@medialas consultas solo pueden verificar las propiedades del navegador en sí, como el tamaño de la ventana gráfica o la resolución de píxeles. Estas propiedades pueden cambiar mediante la interacción del usuario o el código JavaScript (por ejemplo, cambiar el tamaño de la ventana del navegador), pero no solo a través de CSS.
::beforey los ::afterpseudoelementos no se consideran parte del DOM y no se pueden combinar de ninguna otra manera.
Los combinadores 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 pasa el mouse sobre él , pero la posición solo se actualiza cuando mueve el mouse.

Eso debería ser suficiente para convencerte de que la coincidencia del selector, por sí sola, no puede completarse con Turing . ¿Pero qué hay del diseño?

El algoritmo de diseño CSS moderno es muy complejo, con características como Flexbox y Grid que enturbian las aguas. Pero incluso si fuera posible activar un bucle infinito con diseño, sería difícil aprovechar esto para realizar cálculos útiles. Esto se debe a que los selectores de CSS inspeccionan solo la estructura interna del DOM, no cómo se presentan estos elementos en la pantalla. Por lo tanto, cualquier prueba de integridad de Turing que use el sistema de diseño 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 CSS completo y no Turing 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 una granja de servidores completa a la búsqueda de errores en Chrome. Si hubiera una manera de escribir un bucle infinito usando CSS, entonces probablemente ya lo habrían encontrado 😉

Hada lambda
fuente

44

Cuando la gente dice "CSS se está completando" se refieren a "CSS, que admite animaciones es Turing completo". Puede restringir los lenguajes de programación y concluir que no están completando Turing usando su lógica, pero tendría que especificar las restricciones.

philix

36

Creo que esta respuesta está usando una definición divertida de "alto", ciertamente no la que me gustaría si estuviera haciendo la pregunta, al menos. Parece que usa "detener" para significar "hay un momento en que las propiedades calculadas para cada elemento dejan de cambiar"; pero me gustaría "detener" para significar "el algoritmo que transforma CSS declarativo en las propiedades calculadas de todos los elementos termina de ejecutarse". Con la última definición, parece que debe haber mucho más argumento que simplemente "no hay animaciones".

Daniel Wagner

44

Tu lógica está al revés aquí. La integridad de Turing implica que la detención es indecidible no significa que la detención sea indecidible implica la integridad de Turing.

asmeurer

3

@LambdaFairy ¿Cuál es el problema de detención de CSS ? No creo que tal cosa exista. El problema de detención solo es relevante para las máquinas. El modelo computacional más poderoso que tenemos hoy son las máquinas de Turing. Su computadora es tan poderosa como una máquina de Turing (sin memoria infinita). CSS solo no se puede definir como una máquina. Quizás pueda definir el motor CSS de un navegador como una máquina, pero incluso así solo puede ser tan poderoso como una TM. La afirmación "problema de detención para CSS " simplemente no tiene ningún sentido, a menos que CSS se haya convertido en un nuevo autómata en la jerarquía de Chomsky.

Mike Shi

3

@LambdaFairy No estás entendiendo cómo sería una prueba de incompletitud. Sabemos que el problema de detención es indecidible por una TM. La prueba original parece hacer la afirmación porque CSS puede resolver el problema de detención que no está completo. Si CSS realmente podría resolver el problema de detención, entonces CSS es más fuerte que una máquina de Turing porque podría calcular algo que un TM no puede. Sabemos (por la tesis de Church-Turing) que no se puede construir una máquina que sea más fuerte que un TM / The Lambda Calculus. Por lo tanto, esto es una contradicción, y su declaración original no es correcta.

Isaac Diamond

32

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:

Por lo tanto, no creo que CSS se esté completando. No hay capacidad para definir una función en CSS. Para que un sistema esté completo, tiene que ser posible escribir un intérprete: una función que interpreta expresiones que denotan programas 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 programa que se interpretará en CSS.

DVK
fuente

44

CSS no es ejecutable de ninguna manera. La persona que escribió el comentario citado no parece entender eso. : - \

Ryan Prior

33

CSS es un conjunto de instrucciones para un procesador (motor de diseño). ¿Qué es lo que no es "ejecutable" al respecto?

DVK

47

La integridad de Turing no se trata solo de si puedes escribir programas de la manera que quieras o crees. Es una propiedad matemática sobre la calculabilidad. Por lo tanto, no puede creer o no que CSS esté completando Turing, necesita una prueba. En este caso, debido a la regla 110, CSS es Turing-complete.

Mikaël Mayer

15

@ MikaëlMayer: como se señala en muchos comentarios en la respuesta "110", eso requiere que el usuario realice una acción. Si se requieren acciones del usuario, CSS sin el usuario NO se está completando

DVK

1

@DVK las pulsaciones repetidas de teclas requeridas por el ejemplo CSS 110 no son una "acción" del usuario, sino que pueden realizarse mediante un circuito digital repetitivo. Las máquinas de turing reales requieren algún tipo de hardware eléctrico para impulsar la ejecución, por lo que no veo cómo esto es diferente

woojoo666

6

La integridad de Turing no se trata solo de "definir funciones" o "tener ifs / loops / etc". Por ejemplo, Haskell no tiene "bucle", el cálculo lambda no tiene "ifs", etc.

Por ejemplo, este sitio: http://experthuman.com/programming-with-nothing . El autor usa Ruby y crea un programa "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 tipos

Entonces, sí, en mi opinión, CSS3 + HTML está completo (incluso si no puedes hacer ningún cálculo real sin volverte loco)

Maurício Szabo
fuente

11

Haskell y lambda-caclculus tienen recurrencia. ¿CSS? Tienes que estar loco para hacer cualquier cálculo real en Malbolge; en CSS, no importa lo loco que estés: no funcionará, CSS no está completo, y eso no es una cuestión de opinión.

JMCF125

11

Lo sentimos, no pude encontrar ningún otro comentario tuyo en esta página. Pero como se señala en la respuesta aceptada, es Turing completo "(...) siempre y cuando considere (...) las interacciones del usuario como parte de la" ejecución "de CSS". Y yo no.

JMCF125

20

Sin pretender ser ofensivo, la integridad de turing no responde a la opinión de nadie.

trisweb

55

@ MaurícioSzabo No, CSS3 más HTML más un ser humano que continuamente avanza en la simulación es Turing completo.

Lambda Fairy

44

@LambdaFairy Eso también es cierto para todas las máquinas físicas.

Miles Rout

5

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

Henrik Sommerland
fuente

1

No veo en qué parte de los requisitos de Turing Machine se especifica la capacidad de procesar bucles infinitos. Su segundo punto no parece ser válido. Si bien Turing usó su Máquina de Turing para probar problemas de computabilidad, estas reglas, como el problema de detención, no determinan si una máquina es una máquina de Turing o no. Si la Máquina de Turing incluyera estas hipótesis como requisitos, no podría haber usado la máquina de Turing para probarlas.

Adam Davis

44

@AdamDavis Es un argumento totalmente válido: si existe un algoritmo que resuelve el problema de detención para un formalismo completo de Turing, eso es equivalente a resolver el problema de detención en general. Por supuesto, esto se ha demostrado imposible, lo que significa que si el problema de detención puede resolverse para un formalismo dado, entonces ese formalismo no debe ser completo de Turing. Por lo tanto, todos los formalismos que solo pueden evaluar un número finito de pasos no pueden completarse con Turing, incluido CSS.

00dani

3

Es no si B entonces A! ¡Si no es B, entonces no es A ! Lo primero es afirmar lo consecuente , lo cual usted señala correctamente que está mal. El último, argumento por contrapositivo , es lo que uso y es válido. Tenga en cuenta el uso cuidadoso de la negación en mi último comentario: lo construí específicamente para evitar esa falacia.

Lambda Fairy

1

@ woojoo666 No. Tener la capacidad de transformar el estado de acuerdo con un conjunto de reglas no es lo mismo que estar Turing completo. Nada que solo pueda para un número finito de pasos puede estar completo. Si el conjunto de reglas de transformación solo se puede aplicar un número finito de veces, la pregunta "¿Alguna vez el sistema alcanzará el estado H?" siempre es decidible y, por lo tanto, no está completo. Una implementación de un autómata celular que solo puede hacer un número finito de iteraciones nunca puede completarse.

Henrik Sommerland

1

"Y, sí, también CSS se está completando" [cita requerida]

Andrea Lazzarotto

4

Esta respuesta no es precisa porque combina la descripción de UTM y UTM (Universal Turing Machine).

Tenemos una buena respuesta pero desde una perspectiva diferente y no muestra fallas directas en la respuesta principal actual.

En primer lugar, podemos estar de acuerdo en que los humanos pueden funcionar como UTM. Esto significa que si lo hacemos

CSS + Human == UTM

Entonces CSSparte es inútil porque todo el trabajo puede ser realizado porHuman quién hará la parte 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 resultados será lo mismo. Esto significa este texto UTM? No, esto es solo una entrada (descripción) que otros UTM (humanos o computadoras) pueden leer y ejecutar. Hacer clic es suficiente para ejecutar cualquier UTM.

La parte crítica de la que carece CSS es la capacidad de cambiar su propio estado de manera arbitraria, si CSS pudiera generar clics, entonces sería UTM. El argumento de que sus clics son "inestables" para CSS no es exacto porque el verdadero "inestable" para CSS es Layout Engine que lo ejecuta y debería ser suficiente para demostrar que CSS es UTM.

Yankees
fuente

La regla 110 es un UTM. Su texto es una descripción (probablemente un poco insuficiente) de la Regla 110, por lo que sí, ese texto es una (representación de a) UTM.

OrangeDog

"Si CSS pudiera generar clics", uso muchos microcontroladores AVR en mis proyectos. Puede usar un reloj interno, que está limitado a 8MHz. Alternativamente, puede conectar un cristal externo y subir hasta 20MHz. Alternativamente, también podría suministrar un reloj completamente externo para que ni siquiera el hardware de la CPU esté impulsando el cristal. Lo que significa que en realidad puedo conectar un interruptor y un trozo de circuito para eliminar el rebote, y literalmente usarlo como un reloj presionando el botón. ¿Eso significa que deja de estar completa si hago eso?

Cedric Mamo

1

@CedricMamo Pero sus clics cambian de estado, y solo necesita hacer clic en los lugares correctos, de lo contrario no funcionaría. Mire exactamente en eli.fox-epste.in/rule110-full.html Puedo hacer clic en CUALQUIER celda, si CSS está deshabilitado, aún hago clic en las celdas correctas y tengo UTM. Si todo lo que hiciera sería hacer clic en un botón "siguiente", entonces CSS sería UTM, pero para tener algo así necesitaría algo de JS que se llame por clic de botón, y como sabemos JS IS UTM. Para CSS necesita tener algo que interprete correctamente el resultado y el estado de actualización.

Yankees

1

@CedricMamo algún enlace a él? En este momento miro un par de ejemplos a partir de ahí, pero no me funciona. En general, si entiendo correctamente, CSS cambia la visibilidad de algunas casillas de verificación y usa pestañas para navegar a la siguiente, y aquí tenemos nuevamente UTM oculto que no es CSS, porque cuando tabula, le pide al navegador que calcule la siguiente posición válida para navegar, y De hecho, hace MUCHO código complejo, esto usa CSS pero es mucho más. Esto significa que demuestra que su navegador es UTM, no CSS.

Yankees

1

@CedricMamo Pero los autómatas celulares tienen en su propia definición un bucle, cuando se realiza la transición de estado, se ejecuta nuevamente, y nuevamente, etc. Si lo eliminamos y dejamos solo esta transición de estado, este autómata ya no será UTM. Esta será exactamente la misma situación que CSS. Podemos definir dos pasos en CA, R- estado de lectura, y W- estado de escritura, CA normal, secuencia infinita RWRWRWRW...en el caso de CSS que solo tenemos R, y no tenemos Wporque modifica cosas que no puede leer, solo si agregamos B- acción del navegador que podríamos tener, RBRBRBR...pero luego BBBBBBestá en su propio UTM.

Yankees

-28

CSS no es un lenguaje de programación, por lo que la cuestión de la integridad de turing no tiene sentido. Si se agregan extensiones de programación a CSS, como fue el caso en IE6, entonces esa nueva síntesis es algo completamente diferente.

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

Ryan Prior
fuente

1

Además (IIRC), existe cierta ambigüedad sobre qué estilos tienen prioridad cuando se utilizan múltiples estilos en conflicto (duplicados). Y luego están las formas ligeramente diferentes con las que diferentes navegadores implementan / interpretan estilos de marcado para tratar.

David R Tribble

70

"CSS no es un lenguaje de programación, por lo que la cuestión de la integridad de turing no tiene sentido". Las oraciones tautológicas son tautológicas.

Adam Davis

3

Eche un vistazo al lenguaje de programación Prolog si se pregunta por qué su respuesta es rechazada tanto.

edwin

¿Está completo CSS Turing?

Respuestas: