CSS Turing est-il complet?

297

CSS n'est pas, pour autant que je sache, Turing complet. Mais ma connaissance de CSS est très limitée.

  • CSS Turing est-il complet?
  • Est-ce que certains projets ou comités existants envisagent des fonctionnalités linguistiques qui pourraient permettre l'exhaustivité de Turing si ce n'est pas le cas actuellement?
css turing-complete Adam Davis
la source
28
C'est déjà fait, si vous utilisez ie6. On les appelle des expressions CSS, et le consensus est qu'elles sont horriblement brisées et dangereuses. JS intégré dans CSS ...
kibibu
13
@Kibibu - Yikes! Veuillez effacer cette idée de mon cerveau avant qu'elle ne se replie sur elle-même!
DVK
Comment CSS pourrait -il être Turing-complet?
SLaks
1
@DVK: vous pourriez en fait faire des choses intéressantes avec eux - en particulier en ce qui concerne la mise en page indépendante de la résolution - qui sont toujours délicates ou excentriques en CSS sans recourir à des tableaux. Je pense que s'ils l'avaient limité à être strictement un langage d'expression déclarative sans effets secondaires au lieu de permettre un accès complet au moteur de script, il aurait été mieux reçu (et peut-être aussi si le webkit l'avait
proposé en
5
@SLaks: Ne sous-estimez pas la puissance de HTML5 / CSS3 :)
Niklas B.

Réponses:

385

Vous pouvez coder la règle 110 dans CSS3, c'est donc Turing-complete tant que vous considérez qu'un fichier HTML d'accompagnement approprié et les interactions utilisateur font partie de l '«exécution» de CSS. Une assez bonne implémentation est disponible, et une autre implémentation est incluse ici:

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"/>
Développer l'extrait

Adam Davis
la source
2
La définition formelle (la plus simple) de Turing Machine est simplement un ensemble d'états, un jeu de symboles, un état initial, un jeu d'acceptation d'états et une fonction de transition. Il n'y a pas de manivelle dedans. Par calcul, nous voulons dire que quelqu'un doit appliquer fidèlement la fonction de transition sur la bande, ce qui est exactement comme le clic dans ce cas. Plus formellement, un modèle de calcul peut être considéré comme un ensemble de règles que quelqu'un doit suivre pour effectuer le calcul. En ce sens, je pense que CSS est Turing-Complete.
John
2
Cet extrait ne semble pas fonctionner (Firefox 61). Je vois une grille de cases à cocher vides - rien ne se passe si vous les cochez.
OrangeDog
2
@John "CSS est complet" me met mal à l'aise, mais je n'ai aucun problème avec "CSS est aussi complet que quelques rochers sur la plage ". Cette dernière affirmation serait-elle correcte?
Raphael Schmitz
1
@ R.Schmitz non, dans ce cas, l'humain choisit où mettre les roches, c'est donc le système combiné humain + roches qui est complet. Dans l'exemple CSS ci-dessus, les touches tab + espace sont un processus de répétition simple, similaire à un circuit de rétroaction. Donc, si C ++ est complet en utilisant du matériel informatique pour exécuter des instructions, alors ce n'est pas exagéré de dire que CSS est complet en utilisant des touches répétitives pour exécuter des instructions
woojoo666
Voici un CodePen de la règle 110 utilisant la même solution, plus des annotations et quelques Sass pour aider les choses SECHES : codepen.io/laras126/pen/OYvGZj J'ai écrit un article de blog accompagnant expliquant les concepts ici: notlaura.com/is-cssss -turing-complete
notlaura
89

Un aspect de l'exhaustivité de Turing est le problème de l' arrêt .

Cela signifie que, si CSS est Turing complet, il n'y a pas d' algorithme général pour déterminer si un programme CSS finira de s'exécuter ou de boucler indéfiniment.

Mais nous pouvons dériver un tel algorithme pour CSS! C'est ici:

  • Si la feuille de style ne déclare aucune animation , elle s'arrêtera.

  • S'il a des animations, alors:

    • Si animation-iteration-countc'est le cas infinite, et que le sélecteur contenant correspond au code HTML, il ne s'arrêtera pas .

    • Sinon, cela s'arrêtera.

C'est tout. Puisque nous venons de résoudre le problème d'arrêt pour CSS, il s'ensuit que CSS n'est pas Turing complet .

(D'autres personnes ont mentionné IE 6, qui permet d'incorporer des expressions JavaScript arbitraires dans CSS; cela ajoutera évidemment l'intégralité de Turing. Mais cette fonctionnalité n'est pas standard, et personne de bon sens ne l'utilise de toute façon.)

Daniel Wagner a soulevé un point que j'ai manqué dans la réponse originale. Il note que même si j'ai couvert les animations , d'autres parties du moteur de style telles que la mise en correspondance des sélecteurs ou la mise en page peuvent également conduire à l'exhaustivité de Turing. Bien qu'il soit difficile de faire un argument formel à ce sujet, je vais essayer de souligner pourquoi il est peu probable que l'exhaustivité de Turing se produise.

Premièrement: les langages complets de Turing ont un moyen de réinjecter des données en eux-mêmes , que ce soit par récursivité ou en boucle. Mais la conception du langage CSS est hostile à ces retours:

  • @mediales requêtes peuvent uniquement vérifier les propriétés du navigateur lui-même, telles que la taille de la fenêtre d'affichage ou la résolution en pixels. Ces propriétés peuvent changer via l'interaction de l'utilisateur ou le code JavaScript (par exemple, le redimensionnement de la fenêtre du navigateur), mais pas uniquement via CSS.

  • ::beforeet les ::afterpseudo-éléments ne sont pas considérés comme faisant partie du DOM et ne peuvent être mis en correspondance d'aucune autre manière.

  • Les combinateurs de sélecteur peuvent uniquement inspecter les éléments au - dessus et avant l'élément en cours, ils ne peuvent donc pas être utilisés pour créer des cycles de dépendance.

  • Il est possible de déplacer un élément lorsque vous le survolez , mais la position ne se met à jour que lorsque vous déplacez la souris.

Cela devrait suffire à vous convaincre que l' appariement des sélecteurs, à lui seul, ne peut pas être complet . Mais qu'en est-il de la mise en page?

L'algorithme de mise en page CSS moderne est très complexe, avec des fonctionnalités telles que Flexbox et Grid brouillant les eaux. Mais même s'il était possible de déclencher une boucle infinie avec mise en page, il serait difficile d'en tirer parti pour effectuer un calcul utile. C'est parce que les sélecteurs CSS inspectent uniquement la structure interne du DOM, pas la façon dont ces éléments sont disposés à l'écran. Ainsi, toute preuve d'exhaustivité de Turing utilisant le système de mise en page doit dépendre de la mise en page seule .

Enfin - et c'est peut-être la raison la plus importante - les fournisseurs de navigateurs ont intérêt à garder CSS non Turing complet . En restreignant la langue, les fournisseurs permettent des optimisations intelligentes qui accélèrent le Web pour tout le monde. De plus, Google consacre toute une batterie de serveurs à la recherche de bogues dans Chrome. S'il y avait un moyen d'écrire une boucle infinie en utilisant CSS, alors ils l'auraient probablement déjà trouvé 😉

Fée lambda
la source
4
Lorsque les gens disent que "CSS est complet", ils veulent dire "CSS, qui prend en charge les animations est Turing complet". Vous pouvez restreindre les langages de programmation et conclure qu'ils ne sont pas Turing Complete en utilisant votre logique, mais vous devrez spécifier les restrictions.
philix
36
Je pense que cette réponse utilise une définition amusante de «arrêter» - certainement pas celle que je voudrais si je posais la question, au moins. Vous semblez utiliser "stop" pour signifier "il y a un moment où les propriétés calculées pour chaque élément cessent de changer"; mais je voudrais que "stopper" signifie "l'algorithme qui transforme le CSS déclaratif en propriétés calculées de tous les éléments se termine". Avec cette dernière définition, il semble qu'il doit y avoir beaucoup plus d'arguments que simplement "il n'y a pas d'animations".
Daniel Wagner
4
Votre logique est à l'envers ici. L'exhaustivité de Turing implique que l'arrêt est indécidable ne signifie pas que l'arrêt est indécidable implique l'exhaustivité de Turing.
asmeurer
3
@LambdaFairy quel est le problème d'arrêt pour CSS ? Je ne crois pas qu'une telle chose existe. Le problème d'arrêt ne concerne que les machines. Le modèle de calcul le plus puissant que nous ayons aujourd'hui est Turing Machines. Votre ordinateur est aussi puissant qu'une machine de Turing (sans mémoire infinie). CSS seul ne peut pas être défini comme une machine. Vous pouvez peut-être définir le moteur CSS d'un navigateur comme une machine, mais même alors, il ne peut être aussi puissant qu'une MT. La déclaration «arrêter le problème pour CSS » n'a tout simplement aucun sens, à moins que CSS ne soit devenu un nouvel automate dans la hiérarchie de Chomsky.
Mike Shi
3
@LambdaFairy Vous ne comprenez pas à quoi ressemblerait une preuve d'incomplétude turing. Nous savons que le problème d'arrêt est indécidable par une MT. La preuve originale semble faire la réclamation car CSS peut résoudre le problème d'arrêt qu'il n'est pas complet. Si CSS pouvait vraiment résoudre le problème de l'arrêt, alors CSS est plus fort qu'une machine de Turing car il pourrait calculer quelque chose qu'une MT ne peut pas. Nous savons (par la thèse de Church-Turing), qu'une machine ne peut pas être construite qui est plus forte qu'une TM / The Lambda Calculus. Par conséquent, c'est une contradiction et votre déclaration d'origine n'est pas correcte.
Isaac Diamond
32

Selon cet article, ce n'est pas le cas . L'article soutient également que ce n'est pas une bonne idée d'en faire un.

Pour citer un des commentaires:

Donc, je ne pense pas que CSS soit complet. Il n'y a aucune possibilité de définir une fonction en CSS. Pour qu'un système soit complet, il doit être possible d'écrire un interpréteur: une fonction qui interprète des expressions qui dénotent des programmes à exécuter. CSS n'a pas de variables directement accessibles à l'utilisateur; vous ne pouvez donc même pas modéliser la structure qui représente le programme à interpréter en CSS.

DVK
la source
4
CSS n'est en aucun cas exécutable. La personne qui a écrit le commentaire cité ne semble pas comprendre cela. : - \
Ryan Prior
33
CSS est un ensemble d'instructions à un processeur (moteur de mise en page). Qu'est-ce qui n'est pas "exécutable" à ce sujet?
DVK
47
L'exhaustivité n'est pas seulement une question de savoir si vous pouvez écrire des programmes comme vous le souhaitez ou selon une conviction. C'est une propriété mathématique de la calculabilité. Donc, vous ne pouvez pas croire ou non que CSS est complet de Turing, vous avez besoin d'une preuve. Dans ce cas, en raison de la règle 110, CSS est Turing-complete.
Mikaël Mayer
15
@ MikaëlMayer - comme indiqué dans de nombreux commentaires dans la réponse "110", qui oblige l'utilisateur à effectuer une action. Si les actions de l'utilisateur sont requises, CSS sans l'utilisateur n'est PAS Turing complet
DVK
1
@DVK les frappes répétitives requises par l'exemple CSS 110 ne sont pas tout à fait une "action" utilisateur, elles peuvent être effectuées par un circuit numérique répétitif. Les machines de turing réelles nécessitent une sorte de matériel électrique pour conduire l'exécution, donc je ne vois pas comment cela est différent
woojoo666
6

L'exhaustivité n'est pas seulement une question de "définition de fonctions" ou de "présence d'if / boucles / etc". Par exemple, Haskell n'a pas de "boucle", lambda-calcul n'a pas de "ifs", etc ...

Par exemple, ce site: http://experthuman.com/programming-with-nothing . L'auteur utilise Ruby et crée un programme "FizzBuzz" avec seulement des fermetures (pas de chaînes, de nombres, ou quelque chose comme ça) ...

Il y a des exemples où les gens calculent certaines fonctions arithmétiques sur Scala en utilisant uniquement le système de type

Donc, oui, à mon avis, CSS3 + HTML est complet (même si vous ne pouvez pas exactement faire de calcul réel sans devenir fou)

Maurício Szabo
la source
11
Haskell et lambda-caclculus ont une récursivité. Est-ce que CSS? Il faut être fou pour faire un vrai calcul dans Malbolge; en CSS, peu importe à quel point vous êtes fou: cela ne fonctionnera pas, CSS n'est pas complet, et ce n'est pas une question d'opinion.
JMCF125
11
Désolé, je n'ai trouvé aucun autre commentaire sur cette page. Mais comme indiqué dans la réponse acceptée, c'est Turing-complete "(...) tant que vous considérez (...) les interactions des utilisateurs comme faisant partie de l '" exécution "de CSS". Et moi non.
JMCF125
20
Sans vouloir être offensant, l'exhaustivité ne répond à l'opinion de personne.
trisweb
5
@ MaurícioSzabo Non, CSS3 plus HTML plus un être humain continuellement en train de faire la simulation est Turing complet.
Lambda Fairy
4
@LambdaFairy C'est également vrai pour toutes les machines de turing physiques.
Miles Rout
5

Le problème fondamental ici est que toute machine écrite en HTML + CSS ne peut pas évaluer un nombre infini d'étapes (c'est-à-dire qu'il ne peut pas y avoir de "vraie" récursivité) à moins que le code ne soit infiniment long. Et la question de savoir si cette machine atteindra la configuration Hpar nétapes ou moins est toujours répondable si elle nest finie.

Henrik Sommerland
la source
1
Je ne vois pas où dans les exigences de Turing Machine la capacité de traiter des boucles infinies est spécifiée. Votre deuxième point ne semble pas être valide. Alors que Turing a utilisé sa machine de Turing pour prouver des problèmes de calculabilité, ces règles, comme le problème d'arrêt, ne déterminent pas si une machine est une machine de Turing ou non. Si la machine de Turing incluait ces hypothèses comme exigences, il n'aurait pas pu utiliser la machine de Turing pour les prouver.
Adam Davis
4
@AdamDavis C'est un argument tout à fait valable: s'il existe un algorithme qui résout le problème d'arrêt pour un formalisme Turing-complet, cela équivaut à résoudre le problème d'arrêt en général. Bien sûr, cela s'est avéré impossible, ce qui signifie que si le problème d'arrêt peut être résolu pour un formalisme donné, ce formalisme ne doit pas être complet. Par conséquent, tous les formalismes qui ne peuvent évaluer qu'un nombre fini d'étapes ne peuvent pas être Turing-complete, CSS inclus.
00dani
3
Ce n'est pas si B alors A! C'est sinon B alors pas A ! Le premier affirme le conséquent , que vous signalez correctement comme faux. Ce dernier, argument par contrapositif , est ce que j'utilise et est valable. Notez l'utilisation prudente de la négation dans mon dernier commentaire - je l'ai construite spécifiquement pour éviter cette erreur.
Lambda Fairy
1
@ woojoo666 Non. Avoir la capacité de transformer l'état selon un ensemble de règles n'est pas la même chose qu'être Turing complet. Rien de ce qui ne peut que pour un nombre fini d'étapes ne peut jamais être complet. Si l'ensemble des règles de transformations ne peut être appliqué qu'un nombre fini de fois, la question "Le système atteindra-t-il jamais l'état H?" est toujours décidable et il n'est donc pas Turing complet. Une implémentation d'un automate cellulaire qui ne peut effectuer qu'un nombre fini d'itérations ne peut jamais être complète.
Henrik Sommerland
1
«Et, oui, CSS est également complet» [citation nécessaire]
Andrea Lazzarotto
4

Cette réponse n'est pas exacte car elle mélange la description de l'UTM et de l'UTM elle-même (Universal Turing Machine).

Nous avons une bonne réponse, mais d'un point de vue différent et elle ne montre pas directement de défauts dans la première réponse actuelle.

Tout d'abord, nous pouvons convenir que l'homme peut fonctionner comme UTM. Cela signifie que si nous le faisons

CSS + Human == UTM

Ensuite, la CSSpartie est inutile car tout le travail peut être effectué par Humanqui fera la partie UTM. Le fait de cliquer peut être UTM, car vous ne cliquez pas au hasard, mais uniquement à des endroits spécifiques.

Au lieu de CSS, je pouvais utiliser ce texte ( règle 110 ):

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

Pour guider mes actions et le résultat sera le même. Cela signifie ce texte UTM? Non, ce n'est qu'une entrée (description) que d'autres UTM (humains ou informatiques) peuvent lire et exécuter. Il suffit de cliquer pour exécuter une UTM.

La partie critique que CSS manque est la capacité de changer son propre état de manière arbitraire, si CSS pouvait générer des clics, ce serait UTM. L'argument selon lequel vos clics sont "excentriques" pour CSS n'est pas précis car le véritable "excentrique" pour CSS est le moteur de mise en page qui l'exécute et cela devrait suffire pour prouver que CSS est UTM.

Yankes
la source
La règle 110 est un UTM. Votre texte est une description (probablement légèrement insuffisante) de la règle 110, alors oui, ce texte est une (représentation d'un) UTM.
OrangeDog
"Si CSS pouvait générer des clics" j'utilise beaucoup de microcontrôleurs AVR dans mes projets. Vous pouvez soit utiliser une horloge interne, limitée à 8 MHz. Alternativement, vous pouvez connecter un cristal externe et monter jusqu'à 20 MHz. Alternativement, je pourrais également fournir une horloge complètement externe, donc ce n'est même pas du matériel de processeur qui pilote le cristal. Cela signifie que je peux réellement câbler un interrupteur et un morceau de circuit pour le rebondir, et l'utiliser littéralement comme une horloge avec moi en appuyant sur le bouton. Est-ce à dire que cela cesse d'être complet si je le fais?
Cedric Mamo
1
@CedricMamo Mais vos clics changent d'état, et vous n'avez besoin de cliquer que sur les bons endroits, sinon cela ne fonctionnerait pas. Regardez exactement sur eli.fox-epste.in/rule110-full.html Je peux cliquer sur N'IMPORTE QUELLE cellule, si CSS est désactivé, je clique toujours sur les cellules correctes et j'ai UTM. Si tout ce que vous faites serait de cliquer sur un bouton "suivant", alors CSS serait UTM, mais pour avoir quelque chose comme ça, vous auriez besoin d'avoir un JS qui est appelé par clic de bouton, et comme nous le savons JS IS UTM. Pour CSS, vous devez avoir quelque chose qui interprétera correctement le résultat et l'état de mise à jour.
Yankes
1
@CedricMamo un lien vers celui-ci? En ce moment, je regarde quelques exemples à partir de là, mais cela ne fonctionne pas pour moi. Dans l'ensemble, si je comprends bien, CSS modifie la visibilité de certaines cases à cocher et que vous utilisez des onglets pour naviguer vers la suivante, et ici nous avons à nouveau caché UTM qui n'est pas CSS, car lorsque vous tabulez, vous demandez au navigateur de calculer la prochaine position valide pour naviguer, et pour l'amincir, il fait BEAUCOUP de code complexe, cela utilise CSS mais c'est beaucoup plus. Cela signifie que vous prouvez que votre navigateur est UTM et non CSS.
Yankes
1
@CedricMamo Mais les automates cellulaires ont dans leur propre définition une boucle, lorsque la transition d'état est effectuée, puis son exécution à nouveau, etc. Si nous la supprimons et ne laissons que cette transition d'état, ces automates ne seront plus UTM. Ce sera exactement la même situation que CSS. Nous pouvons définir deux étapes dans CA, R- l'état de lecture et W- l'état d'écriture, l'autorité de certification normale fait une séquence infinie RWRWRWRW...dans le cas de CSS que nous avons seulement R, et nous n'en avons pas Wparce qu'elle modifie des choses qu'elle ne peut pas lire, seulement si nous ajoutons B- l'action du navigateur alors nous pourrions avoir RBRBRBR...mais BBBBBBest alors sur son propre UTM.
Yankes
-28

CSS n'est pas un langage de programmation, donc la question de la complétude de turing est vide de sens. Si des extensions de programmation sont ajoutées à CSS comme c'était le cas dans IE6, cette nouvelle synthèse est une toute autre chose.

CSS n'est qu'une description des styles; il n'a pas de logique et sa structure est plate.

Ryan Prior
la source
1
De plus (IIRC), il existe une certaine ambiguïté quant aux styles qui ont priorité lorsque plusieurs styles en conflit (en double) sont utilisés. Et puis, il y a les façons légèrement différentes dont les différents navigateurs implémentent / interprètent les styles de balisage.
David R Tribble
70
"CSS n'est pas un langage de programmation, donc la question de l'intégralité du turing est vide de sens." Les phrases tautologiques sont tautologiques.
Adam Davis
3
Jetez un coup d'œil au langage de programmation Prolog si vous vous demandez pourquoi votre réponse est tellement sous-estimée.
edwin