Ist CSS Turing abgeschlossen?

297

CSS ist, soweit ich weiß, nicht vollständig. Meine Kenntnisse in CSS sind jedoch sehr begrenzt.

  • Ist CSS Turing abgeschlossen?
  • Berücksichtigt einer der vorhandenen Entwürfe oder Ausschüsse Sprachfunktionen, die die Vollständigkeit von Turing ermöglichen könnten, wenn dies nicht der Fall ist?
css turing-complete Adam Davis
quelle
28
Es ist bereits erledigt, wenn Sie ie6 verwenden. Sie werden CSS-Ausdrücke genannt, und Konsens ist, dass sie schrecklich gebrochen und gefährlich sind. JS eingebettet in CSS ...
Kibibu
13
@ Kibibu - Huch! Bitte löschen Sie diese Idee aus meinem Gehirn, bevor sie sich auf sich selbst faltet!
DVK
Wie könnte CSS möglicherweise Turing-vollständig sein?
SLaks
1
@DVK: Sie könnten tatsächlich einige coole Dinge damit machen - insbesondere im Hinblick auf das auflösungsunabhängige Layout - die in CSS immer noch schwierig oder eigenartig sind, ohne auf Tabellen zurückzugreifen. Ich denke, wenn sie es auf eine streng deklarative Ausdruckssprache ohne Nebenwirkungen beschränkt hätten, anstatt vollen Zugriff auf die Skript-Engine zu gewähren, wäre sie besser aufgenommen worden (und vielleicht auch, wenn das Webkit sie zuerst entwickelt hätte)
kibibu
5
@ Slaks: Unterschätzen Sie nicht die Leistung von HTML5 / CSS3 :)
Niklas B.

Antworten:

385

Sie können Regel 110 in CSS3 codieren , sodass sie vollständig ist, solange Sie eine geeignete begleitende HTML-Datei und Benutzerinteraktionen als Teil der „Ausführung“ von CSS betrachten. Eine ziemlich gute Implementierung ist verfügbar, und eine andere Implementierung ist hier enthalten:

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"/>
Erweitern Sie das Snippet

Adam Davis
quelle
2
Die formale Definition (am einfachsten) von Turing Machine ist einfach ein Tupel von gesetzten Zuständen, Symbolsätzen, Anfangszuständen, akzeptierten Zuständen und einer Übergangsfunktion. Es ist keine Kurbel drin. Mit Berechnung meinen wir, dass jemand die Übergangsfunktion genau auf das Band anwenden muss, was in diesem Fall genau dem Klicken entspricht. Formal kann ein Berechnungsmodell als ein Satz von Regeln angesehen werden, denen jemand folgen muss, um die Berechnung durchzuführen. In diesem Sinne denke ich, dass CSS Turing-Complete ist.
John
2
Dieses Snippet scheint nicht zu funktionieren (Firefox 61). Ich sehe ein Raster mit leeren Kontrollkästchen - nichts passiert, wenn Sie sie aktivieren.
OrangeDog
2
@ John "CSS ist komplett" macht mich unruhig, aber ich habe kein Problem mit "CSS ist so komplett wie ein paar Felsen am Strand ". Wäre die letztere Aussage richtig?
Raphael Schmitz
1
@ R.Schmitz nein, in diesem Fall wählt der Mensch, wo die Steine ​​platziert werden sollen, also ist es das kombinierte System von Mensch + Steinen, das vollständig ist. Im obigen CSS-Beispiel ist das Drücken der Tabulatortaste + der Leertaste ein einfacher Wiederholungsprozess, ähnlich einer Rückkopplungsschaltung. Wenn also C ++ mit Computerhardware zum Ausführen von Anweisungen vollständig ist, ist es nicht
schwer
Hier ist ein CodePen von Regel 110, der dieselbe Lösung verwendet, plus Anmerkungen und etwas Sass, um DRY zu helfen: codepen.io/laras126/pen/OYvGZj Ich habe einen begleitenden Blog-Beitrag geschrieben, in dem die Konzepte hier erläutert werden: notlaura.com/is-css -turing-complete
notlaura
89

Ein Aspekt der Vollständigkeit von Turing ist das Problem des Anhaltens .

Dies bedeutet, dass es keinen allgemeinen Algorithmus gibt, um zu bestimmen, ob ein CSS-Programm für immer beendet wird oder eine Schleife ausführt , wenn CSS abgeschlossen ist .

Aber wir können einen solchen Algorithmus für CSS ableiten! Hier ist es:

  • Wenn das Stylesheet keine Animationen deklariert , wird es angehalten.

  • Wenn es Animationen gibt, dann:

    • Wenn dies der Fall animation-iteration-countist infiniteund der enthaltende Selektor im HTML-Code übereinstimmt, wird er nicht angehalten.

    • Andernfalls wird es angehalten.

Das ist es. Da wir gerade das Stoppproblem für CSS gelöst haben, ist CSS nicht vollständig .

(Andere Leute haben IE 6 erwähnt, mit dem beliebige JavaScript-Ausdrücke in CSS eingebettet werden können. Dies erhöht natürlich die Vollständigkeit von Turing. Diese Funktion ist jedoch nicht Standard, und niemand, der bei klarem Verstand ist, verwendet sie trotzdem.)

Daniel Wagner brachte einen Punkt vor, den ich in der ursprünglichen Antwort übersehen habe. Er merkt an, dass, während ich Animationen behandelt habe , andere Teile der Style-Engine wie Selector Matching oder Layout ebenfalls zur Vollständigkeit von Turing führen können. Obwohl es schwierig ist, ein formelles Argument dafür zu liefern, werde ich versuchen zu skizzieren, warum die Vollständigkeit von Turing immer noch unwahrscheinlich ist.

Erstens: Turing vollständige Sprachen haben eine Möglichkeit , Daten in sich selbst zurückzugeben , sei es durch Rekursion oder Schleife. Das Design der CSS-Sprache widerspricht jedoch diesem Feedback:

  • @mediaAbfragen können nur die Eigenschaften des Browsers selbst überprüfen, z. B. die Größe des Ansichtsfensters oder die Pixelauflösung. Diese Eigenschaften können sich über Benutzerinteraktion oder JavaScript-Code (z. B. Ändern der Größe des Browserfensters) ändern, jedoch nicht nur über CSS.

  • ::beforeund ::afterPseudoelemente werden nicht als Teil des DOM betrachtet und können auf keine andere Weise abgeglichen werden.

  • Selektorkombinatoren können nur Elemente über und vor dem aktuellen Element untersuchen, sodass sie nicht zum Erstellen von Abhängigkeitszyklen verwendet werden können.

  • Es ist möglich, ein Element wegzuschieben, wenn Sie mit der Maus darüber fahren , aber die Position wird nur aktualisiert, wenn Sie die Maus bewegen.

Das sollte ausreichen, um Sie davon zu überzeugen, dass die Auswahl der Selektoren allein nicht vollständig sein kann . Aber was ist mit dem Layout?

Der moderne CSS-Layout-Algorithmus ist sehr komplex und bietet Funktionen wie Flexbox und Grid, die das Wasser trüben. Aber selbst wenn es möglich wäre, eine Endlosschleife mit Layout auszulösen, wäre es schwierig, dies zu nutzen, um nützliche Berechnungen durchzuführen. Dies liegt daran, dass CSS-Selektoren nur die interne Struktur des DOM überprüfen und nicht, wie diese Elemente auf dem Bildschirm angeordnet sind. Daher muss jeder Turing-Vollständigkeitsnachweis, der das Layoutsystem verwendet, nur vom Layout abhängen .

Schließlich - und dies ist vielleicht der wichtigste Grund - haben Browser-Anbieter ein Interesse daran, CSS nicht vollständig zu halten . Durch die Einschränkung der Sprache ermöglichen Anbieter clevere Optimierungen , die das Web für alle schneller machen. Darüber hinaus widmet Google eine ganze Serverfarm der Suche nach Fehlern in Chrome. Wenn es eine Möglichkeit gäbe, eine Endlosschleife mit CSS zu schreiben, hätten sie sie wahrscheinlich bereits gefunden 😉

Lambda-Fee
quelle
4
Wenn Leute sagen "CSS ist vollständig", meinen sie "CSS, das Animationen unterstützt, ist vollständig". Sie können Programmiersprachen einschränken und daraus schließen, dass sie mit Ihrer Logik nicht Turing Complete sind, aber Sie müssten die Einschränkungen angeben.
Philix
36
Ich denke, diese Antwort verwendet eine lustige Definition von "Halt" - sicherlich nicht die, die ich mir wünschen würde, wenn ich zumindest die Frage stellen würde. Sie scheinen "halt" zu verwenden, um zu bedeuten, dass sich die berechneten Eigenschaften für jedes Element nicht mehr ändern. aber ich möchte, dass "halt" "der Algorithmus bedeutet, der deklaratives CSS in die berechneten Eigenschaften aller Elemente umwandelt, die ausgeführt werden". Bei der letztgenannten Definition scheint es deutlich mehr Argumente zu geben als nur "es gibt keine Animationen".
Daniel Wagner
4
Ihre Logik ist hier rückwärts. Die Vollständigkeit von Turing impliziert, dass das Anhalten unentscheidbar ist. Dies bedeutet nicht, dass das Anhalten von Unentscheidbarkeit nicht impliziert.
Asmeurer
3
@ LambdaFairy Was ist das Halteproblem für CSS ? Ich glaube nicht, dass so etwas existiert. Das Halteproblem ist nur für Maschinen relevant. Das leistungsfähigste Rechenmodell, das wir heute haben, sind Turing-Maschinen. Ihr Computer ist so leistungsfähig wie eine Turing-Maschine (ohne unendlichen Speicher). CSS allein kann nicht als Maschine definiert werden. Vielleicht können Sie die CSS-Engine eines Browsers als Maschine definieren, aber selbst dann kann sie nur so leistungsfähig sein wie ein TM. Die Aussage "Problem für CSS stoppen " macht einfach keinen Sinn, es sei denn, CSS ist zu einem neuen Automaten in Chomskys Hierarchie geworden.
Mike Shi
3
@LambdaFairy Sie verstehen falsch, wie ein Beweis für Unvollständigkeit aussehen würde. Wir wissen, dass das Problem des Anhaltens von einem TM nicht entschieden werden kann. Der ursprüngliche Beweis scheint die Behauptung aufzustellen, da CSS das Stoppproblem lösen kann, das nicht vollständig ist. Wenn CSS das Problem des Anhaltens wirklich lösen könnte, wäre CSS stärker als eine Turing-Maschine, da es etwas berechnen könnte, was ein TM nicht kann. Wir wissen (aus der Church-Turing-These), dass keine Maschine gebaut werden kann, die stärker ist als ein TM / The Lambda Calculus. Daher ist dies ein Widerspruch, und Ihre ursprüngliche Aussage ist nicht korrekt.
Isaac Diamond
32

Laut diesem Artikel ist es nicht . Der Artikel argumentiert auch, dass es keine gute Idee ist, es zu einem zu machen.

Um aus einem der Kommentare zu zitieren:

Daher glaube ich nicht, dass CSS vollständig ist. Es gibt keine Möglichkeit, eine Funktion in CSS zu definieren. Damit ein System vollständig ist, muss es möglich sein, einen Interpreter zu schreiben: eine Funktion, die Ausdrücke interpretiert, die auszuführende Programme bezeichnen. CSS enthält keine Variablen, auf die der Benutzer direkt zugreifen kann. Sie können also nicht einmal die Struktur modellieren, die das in CSS zu interpretierende Programm darstellt.

DVK
quelle
4
CSS ist in keiner Weise ausführbar. Die Person, die den zitierten Kommentar geschrieben hat, scheint das nicht zu verstehen. : - \
Ryan Prior
33
CSS ist eine Reihe von Anweisungen an einen Prozessor (Layout-Engine). Was ist daran nicht "ausführbar"?
DVK
47
Bei der Vollständigkeit geht es nicht nur darum, ob Sie Programme so schreiben können, wie Sie es möchten, oder um einen Glauben. Es ist eine mathematische Eigenschaft zur Berechenbarkeit. Sie können also nicht glauben oder nicht, dass CSS vollständig ist. Sie benötigen einen Beweis. In diesem Fall ist CSS aufgrund der Regel 110 Turing-vollständig.
Mikaël Mayer
15
@ MikaëlMayer - Wie in vielen Kommentaren in der Antwort "110" erwähnt, muss der Benutzer eine Aktion ausführen. Wenn Benutzeraktionen erforderlich sind, ist CSS ohne den Benutzer NICHT abgeschlossen
DVK
1
@DVK Die für das CSS 110-Beispiel erforderlichen wiederholten Tastendrücke sind keine Benutzeraktion, sondern können von einer sich wiederholenden digitalen Schaltung ausgeführt werden. Tatsächliche Turingmaschinen benötigen irgendeine Art von elektrischer Hardware, um die Ausführung zu
steuern
6

Bei der Vollständigkeit der Turing geht es nicht nur darum, "Funktionen zu definieren" oder "ifs / loops / etc zu haben". Zum Beispiel hat Haskell keine "Schleife", Lambda-Kalkül keine "Wenns" usw.

Zum Beispiel diese Seite: http://experthuman.com/programming-with-nothing . Der Autor verwendet Ruby und erstellt ein "FizzBuzz" -Programm mit nur Verschlüssen (keine Zeichenfolgen, Zahlen oder ähnliches) ...

Es gibt Beispiele, bei denen Benutzer einige arithmetische Funktionen in Scala nur mit dem Typsystem berechnen

Also, ja, meiner Meinung nach ist CSS3 + HTML vollständig (auch wenn Sie damit keine wirklichen Berechnungen durchführen können, ohne verrückt zu werden).

Maurício Szabo
quelle
11
Haskell und Lambda-Caclculus haben eine Rekursion. Funktioniert CSS? Man muss verrückt sein, um in Malbolge wirklich rechnen zu können. In CSS spielt es keine Rolle, wie verrückt Sie sind: Es wird nicht funktionieren, CSS ist nicht vollständig und das ist keine Ansichtssache.
JMCF125
11
Entschuldigung, ich konnte auf dieser Seite keinen weiteren Kommentar von Ihnen finden. Aber wie in der akzeptierten Antwort angegeben, ist es Turing-vollständig "(...), solange Sie (...) Benutzerinteraktionen als Teil der" Ausführung "von CSS betrachten". Und ich nicht.
JMCF125
20
Ohne die Absicht zu haben, beleidigend zu sein, entspricht die Vollständigkeit nicht der Meinung von irgendjemandem.
Trisweb
5
@ MaurícioSzabo Nein, CSS3 plus HTML plus ein Mensch, der ständig die Simulation durchläuft, ist Turing abgeschlossen.
Lambda Fairy
4
@LambdaFairy Das gilt auch für jede physische Turingmaschine.
Miles Rout
5

Das grundlegende Problem hierbei ist, dass jede in HTML + CSS geschriebene Maschine nicht unendlich viele Schritte auswerten kann (dh es kann keine "echte" Rekursion geben), es sei denn, der Code ist unendlich lang. Und die Frage , ob diese Maschine Hin nSchritten oder weniger die Konfiguration erreicht, ist immer zu beantworten, wenn sie nendlich ist.

Henrik Sommerland
quelle
1
Ich sehe nicht, wo in den Anforderungen der Turing-Maschine die Fähigkeit zur Verarbeitung von Endlosschleifen angegeben ist. Ihr zweiter Punkt scheint nicht gültig zu sein. Während Turing seine Turing-Maschine verwendete, um Probleme der Berechenbarkeit zu beweisen, bestimmen diese Regeln, wie das Stopp-Problem, nicht, ob eine Maschine eine Turing-Maschine ist oder nicht. Wenn die Turingmaschine diese Hypothese als Anforderungen aufgenommen hätte, hätte er die Turingmaschine nicht verwenden können, um sie zu beweisen.
Adam Davis
4
@AdamDavis Es ist ein völlig gültiges Argument: Wenn ein Algorithmus existiert, der das Stoppproblem für einen Turing-vollständigen Formalismus löst, entspricht dies der Lösung des Stoppproblems im Allgemeinen. Dies hat sich natürlich als unmöglich erwiesen, was bedeutet, dass der Formalismus nicht vollständig sein darf, wenn das Halteproblem für einen bestimmten Formalismus gelöst werden kann . Daher können nicht alle Formalismen, die nur eine endliche Anzahl von Schritten bewerten können, Turing-vollständig sein, einschließlich CSS.
00dani
3
Es ist nicht wenn B dann A! Es ist wenn nicht B, dann nicht A ! Ersteres bestätigt die Konsequenz , auf die Sie richtig hinweisen, ist falsch. Letzteres, kontrapositives Argument , verwende ich und ist gültig. Beachten Sie die sorgfältige Verwendung der Negation in meinem letzten Kommentar - ich habe sie speziell konstruiert, um diesen Irrtum zu vermeiden.
Lambda Fairy
1
@ woojoo666 Nein. In der Lage zu sein, den Status nach einer Reihe von Regeln zu transformieren, ist nicht dasselbe wie Turing vollständig zu sein. Nichts, was nur für eine begrenzte Anzahl von Schritten möglich ist, kann jemals vollständig sein. Wenn der Satz von Transformationsregeln nur eine endliche Anzahl von Malen angewendet werden kann, wird die Frage "Wird das System jemals den Zustand erreichen H?" ist immer entscheidbar und damit nicht vollständig. Eine Implementierung eines zellularen Automaten, der nur eine begrenzte Anzahl von Iterationen ausführen kann, kann niemals vollständig sein.
Henrik Sommerland
1
"Und, ja, auch CSS sind komplett" [Zitat erforderlich]
Andrea Lazzarotto
4

Diese Antwort ist nicht korrekt, da sie die Beschreibung von UTM und UTM selbst (Universal Turing Machine) mischt.

Wir haben eine gute Antwort, aber aus einer anderen Perspektive, und es zeigt keine direkten Fehler in der aktuellen Top-Antwort.

Zunächst können wir uns darauf einigen, dass der Mensch als UTM arbeiten kann. Das heißt, wenn wir es tun

CSS + Human == UTM

Dann ist ein CSSTeil nutzlos, da alle Arbeiten von dem erledigt werden können, Humander den UTM-Teil ausführt. Das Klicken kann UTM sein, da Sie nicht zufällig klicken, sondern nur an bestimmten Stellen.

Anstelle von CSS könnte ich diesen Text verwenden ( Regel 110 ):

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

Meine Handlungen und Ergebnisse zu leiten wird gleich sein. Das heißt dieser Text UTM? Nein, dies ist nur eine Eingabe (Beschreibung), die andere UTM (Mensch oder Computer) lesen und ausführen können. Ein Klick reicht aus, um eine UTM auszuführen.

Ein kritischer Teil, der CSS fehlt, ist die Fähigkeit, seinen eigenen Status auf willkürliche Weise zu ändern. Wenn CSS Klicks generieren könnte, wäre es UTM. Das Argument, dass Ihre Klicks für CSS "kurbelig" sind, ist nicht korrekt, da echte "Kurbel" für CSS die Layout-Engine ist, die es ausführt, und es sollte ausreichen, um zu beweisen, dass CSS UTM ist.

Ruckelt
quelle
Regel 110 ist eine UTM. Ihr Text ist eine (wahrscheinlich etwas unzureichende) Beschreibung von Regel 110, also ja, dieser Text ist eine (Darstellung einer) UTM.
OrangeDog
"Wenn CSS Klicks erzeugen könnte" Ich verwende in meinen Projekten viele AVR-Mikrocontroller. Sie können entweder einen internen Takt verwenden, der auf 8 MHz begrenzt ist. Alternativ können Sie einen externen Quarz anschließen und bis zu 20 MHz erreichen. Alternativ könnte ich auch einfach eine komplett externe Uhr liefern, damit nicht einmal die CPU-Hardware den Kristall antreibt. Das bedeutet, dass ich tatsächlich einen Schalter und eine Schaltung verkabeln kann, um sie zu entprellen, und das buchstäblich als Uhr verwenden kann, wenn ich den Knopf drücke. Bedeutet das, dass es nicht mehr vollständig ist, wenn ich das tue?
Cedric Mamo
1
@CedricMamo Aber Ihre Klicks ändern den Status und Sie müssen nur auf die richtigen Stellen klicken, sonst würde es nicht funktionieren. Schauen Sie genau auf eli.fox-epste.in/rule110-full.html. Ich kann auf JEDE Zelle klicken. Wenn CSS deaktiviert ist, klicke ich immer noch auf die richtigen Zellen und habe UTM. Wenn Sie nur auf eine Schaltfläche "Weiter" klicken würden, wäre CSS in der Tat UTM. Um so etwas zu haben, benötigen Sie jedoch JS, das pro Schaltflächenklick aufgerufen wird, und wie wir wissen, ist JS UTM. Für CSS benötigen Sie etwas, das das Ergebnis und den Aktualisierungsstatus korrekt interpretiert.
Yankes
1
@ CedricMamo irgendeinen Link dazu? Im Moment schaue ich mir einige Beispiele von dort an, aber es funktioniert nicht für mich. Wenn ich CSS richtig verstehe, ändern Sie die Sichtbarkeit einiger Kontrollkästchen, und Sie verwenden Registerkarten, um zum nächsten zu navigieren. Hier haben wir erneut UTM ausgeblendet, das kein CSS ist, da Sie den Browser beim Tabulator auffordern, die nächste gültige Position für die Navigation zu berechnen Um es zu verdünnen, macht es viel komplexen Code, dies verwendet CSS, aber es ist viel mehr. Dies bedeutet, dass Sie beweisen, dass Ihr Browser UTM und nicht CSS ist.
Yankes
1
@CedricMamo Aber zelluläre Automaten haben in ihrer eigenen Definition eine Schleife. Wenn der Zustandsübergang abgeschlossen ist, wird sie immer wieder ausgeführt usw. Wenn wir sie entfernen und nur diesen Zustandsübergang belassen, sind diese Automaten keine UTM mehr. Dies ist genau die gleiche Situation wie bei CSS. Wir können zwei Schritte in der Zertifizierungsstelle definieren: R- Lesestatus und W- Schreibstatus, normale Zertifizierungsstelle führt eine unendliche Sequenz RWRWRWRW...aus, wenn wir nur CSS haben R, und wir haben keine, Wweil sie Dinge modifiziert, die sie nicht lesen kann, nur wenn wir hinzufügen B- Browser-Aktion, die wir dann haben könnten, RBRBRBR...aber dann BBBBBBauf ihrer eigenen UTM ist.
Yankes
-28

CSS ist keine Programmiersprache, daher ist die Frage der Vollständigkeit der Bedeutung bedeutungslos. Wenn CSS Programmiererweiterungen hinzugefügt werden, wie dies in IE6 der Fall war, ist diese neue Synthese eine ganz andere Sache.

CSS ist lediglich eine Beschreibung von Stilen. es hat keine Logik und seine Struktur ist flach.

Ryan Prior
quelle
1
Außerdem (IIRC) gibt es einige Unklarheiten darüber, welche Stile Vorrang haben, wenn mehrere widersprüchliche (doppelte) Stile verwendet werden. Und dann gibt es die etwas unterschiedlichen Möglichkeiten, mit denen verschiedene Browser Markup-Stile implementieren / interpretieren, um damit umzugehen.
David R Tribble
70
"CSS ist keine Programmiersprache, daher ist die Frage der Vollständigkeit der Bedeutung bedeutungslos." Tautologische Sätze sind tautologisch.
Adam Davis
3
Schauen Sie sich die Programmiersprache Prolog an, wenn Sie sich fragen, warum Ihre Antwort so schlecht bewertet wird.
Edwin