Czy CSS Turing jest kompletny?

297

O ile wiem, CSS nie jest kompletny. Ale moja wiedza na temat CSS jest bardzo ograniczona.

  • Czy CSS Turing jest kompletny?
  • Czy któryś z istniejących projektów lub komitetów rozważa funkcje językowe, które mogłyby umożliwić kompletność Turinga, jeśli nie jest to teraz?
css turing-complete Adam Davis
źródło
28
To już zostało zrobione, jeśli używasz ie6. Nazywa się je wyrażeniami CSS, a konsensus jest taki, że są strasznie złamane i niebezpieczne. JS osadzony w CSS ...
kibibu
13
@Kibibu - Yikes! Proszę, wymaż ten pomysł z mojego mózgu, zanim sam się położy!
DVK
W jaki sposób CSS może być kompletny w Turingu?
SLaks,
1
@DVK: możesz naprawdę robić z nimi fajne rzeczy - szczególnie w odniesieniu do układu niezależnego od rozdzielczości - które są nadal trudne lub dziwaczne w CSS bez uciekania się do tabel. Wydaje mi się, że gdyby ograniczyli go do używania języka deklaratywnego bez żadnych skutków ubocznych, zamiast umożliwić pełny dostęp do silnika skryptowego, lepiej by go odebrano (a być może również, gdyby webkit najpierw go
wymyślił
5
@SLaks: Nie lekceważ potęgi HTML5 / CSS3 :)
Niklas B.,

Odpowiedzi:

385

Możesz zakodować Regułę 110 w CSS3, więc jest ona kompletna Turinga, pod warunkiem, że weźmiesz pod uwagę odpowiedni towarzyszący plik HTML i interakcje użytkownika jako część „wykonania” CSS. Dostępna jest całkiem dobra implementacja , a tutaj znajduje się kolejna implementacja:

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"/>
Rozwiń fragment kodu

Adam Davis
źródło
2
Formalna definicja (najprostsza) maszyny Turinga jest po prostu krotką zestawu stanów, zestawu symboli, stanu początkowego, zestawu stanów akceptujących i funkcji przejścia. Nie ma w tym korby. Przez obliczenia rozumiemy, że ktoś musi wiernie zastosować funkcję przejścia na taśmie, która w tym przypadku jest dokładnie taka jak kliknięcie. Mówiąc bardziej formalnie, model obliczeń można postrzegać jako zbiór zasad, których należy przestrzegać, aby wykonać obliczenia. W tym sensie myślę, że CSS jest Turing-Complete.
John
2
Ten fragment kodu nie działa (Firefox 61). Widzę siatkę pustych pól wyboru - nic się nie stanie, jeśli je zaznaczysz.
OrangeDog,
2
@John „CSS jest kompletny” sprawia, że ​​jestem niespokojny, ale nie mam problemu z „CSS jest tak kompletny jak kilka kamieni na plaży ”. Czy to ostatnie stwierdzenie byłoby prawidłowe?
Raphael Schmitz
1
@ R. Schmitz nie, w takim przypadku człowiek decyduje, gdzie umieścić skały, więc jest to złożony system ludzkich + skał, który jest kompletny. W powyższym przykładzie CSS naciśnięcie klawisza tab + spacja jest prostym powtarzającym się procesem, podobnym do powiedzenia obwodu sprzężenia zwrotnego. Więc jeśli C ++ jest w trakcie wykonywania instrukcji przy użyciu sprzętu komputerowego, to nie jest trudno powiedzieć, że CSS jest w trakcie wykonywania instrukcji przy użyciu powtarzających się naciśnięć klawiszy
woojoo666,
Oto CodePen z reguły 110 używającej tego samego rozwiązania, a także adnotacje i trochę Sassa, które pomagają WYSUSZAĆ rzeczy: codepen.io/laras126/pen/OYvGZj Napisałem towarzyszący post na blogu wyjaśniający pojęcia tutaj: notlaura.com/is-css -turing-complete
notlaura
89

Jednym z aspektów kompletności Turinga jest problem zatrzymania .

Oznacza to, że jeśli CSS jest ukończony przez Turinga, nie ma ogólnego algorytmu określającego, czy program CSS zakończy działanie lub zapętli na zawsze.

Ale możemy uzyskać taki algorytm dla CSS! Oto on:

  • Jeśli arkusz stylów nie deklaruje żadnych animacji , zostanie zatrzymany.

  • Jeśli ma animacje, to:

    • Jeśli jakakolwiek animation-iteration-countjest infinite, a przełącznik zawierający dopasowane w HTML, to będzie nie zatrzyma.

    • W przeciwnym razie się zatrzyma.

Otóż ​​to. Ponieważ właśnie rozwiązaliśmy problem zatrzymania CSS, wynika z tego, że CSS nie jest kompletny w Turingu .

(Inni wspominali o IE 6, która pozwala na osadzanie dowolnych wyrażeń JavaScript w CSS; to oczywiście doda kompletność Turinga. Ale ta funkcja jest niestandardowa i nikt przy zdrowych zmysłach i tak z niej nie korzysta).

Daniel Wagner poruszył kwestię, której mi brakowało w pierwotnej odpowiedzi. Zauważa, że ​​chociaż omówiłem animacje , inne części silnika stylu, takie jak dopasowanie selektora lub układ, mogą również prowadzić do kompletności Turinga. Chociaż trudno o formalny spór na ten temat, postaram się wyjaśnić, dlaczego kompletność Turinga nadal jest mało prawdopodobna.

Po pierwsze: Turing z kompletnymi językami ma jakiś sposób na przekazywanie danych z powrotem do siebie , czy to poprzez rekurencję czy zapętlanie. Ale konstrukcja języka CSS jest wrogo nastawiona do tej opinii:

  • @mediazapytania mogą sprawdzać tylko właściwości samej przeglądarki, takie jak rozmiar rzutni lub rozdzielczość pikseli. Te właściwości można zmienić za pomocą interakcji użytkownika lub kodu JavaScript (np. Zmiana rozmiaru okna przeglądarki), ale nie tylko za pomocą CSS.

  • ::beforea ::afterpseudoelementy nie są uważane za część DOM i nie można ich dopasowywać w żaden inny sposób.

  • Kombinatory selektorów mogą sprawdzać tylko elementy powyżej i przed bieżącym elementem, więc nie można ich używać do tworzenia cykli zależności.

  • Można przesunąć element, gdy najedziesz na niego kursorem , ale pozycja jest aktualizowana tylko po przesunięciu myszy.

To powinno wystarczyć, aby przekonać cię, że samo dopasowanie selektora nie może być zakończone przez Turinga . Ale co z układem?

Nowoczesny algorytm układu CSS jest bardzo złożony, z takimi funkcjami jak Flexbox i Grid mętniącymi wody. Ale nawet gdyby można było uruchomić nieskończoną pętlę z układem, trudno byłoby to wykorzystać do wykonania użytecznego obliczenia. Dzieje się tak, ponieważ selektory CSS sprawdzają tylko wewnętrzną strukturę DOM, a nie to, jak te elementy są rozmieszczone na ekranie. Tak więc każdy dowód kompletności Turinga przy użyciu systemu układu musi zależeć od samego układu .

Wreszcie - i jest to być może najważniejszy powód - producenci przeglądarek mają interes w tym, aby CSS nie był kompletny . Ograniczając język, dostawcy pozwalają na sprytne optymalizacje , dzięki którym internet jest szybszy dla wszystkich. Co więcej, Google poświęca całą farmę serwerów na wyszukiwanie błędów w Chrome. Gdyby istniał sposób na napisanie nieskończonej pętli za pomocą CSS, prawdopodobnie już by ją znaleźli 😉

Lambda Fairy
źródło
4
Kiedy ludzie mówią, że „CSS jest zakończony Turinga”, mają na myśli „CSS, który obsługuje animacje jest zakończony Turinga”. Możesz ograniczyć języki programowania i stwierdzić, że nie są one Turing Complete, używając swojej logiki, ale musisz określić ograniczenia.
philix
36
Myślę, że w tej odpowiedzi użyto zabawnej definicji „zatrzymania” - na pewno nie tej, której chciałbym, gdybym zadawał pytanie. Wydaje się, że używasz „zatrzymania”, aby oznaczać „jest czas, w którym obliczone właściwości dla każdego elementu przestają się zmieniać”; ale chciałbym, aby „halt” oznaczało „algorytm, który przekształca deklaratywny CSS w obliczone właściwości wszystkich elementów, kończy działanie”. W tej drugiej definicji wydaje się, że potrzeba znacznie więcej argumentów niż tylko „nie ma animacji”.
Daniel Wagner,
4
Twoja logika jest tutaj odwrócona. Kompletność Turinga oznacza, że ​​zatrzymanie jest nierozstrzygalne, nie oznacza, że ​​zatrzymanie jest nierozstrzygalne, oznacza kompletność Turinga.
asmeurer
3
@LambdaFairy jaki jest problem z zatrzymaniem CSS ? Nie wierzę, że coś takiego istnieje. Problem zatrzymania dotyczy tylko maszyn. Najpotężniejszym modelem obliczeniowym, jaki mamy dzisiaj, są maszyny Turinga. Twój komputer jest tak potężny jak maszyna Turinga (bez nieskończonej pamięci). Sam CSS nie może być zdefiniowany jako maszyna. Być może możesz zdefiniować silnik CSS przeglądarki jako maszynę, ale nawet wtedy może on być tak potężny jak TM. Stwierdzenie „zatrzymanie problemu dla CSS ” po prostu nie ma sensu, chyba że CSS stał się nowym automatem w hierarchii Chomsky'ego.
Mike Shi
3
@LambdaFairy Nie rozumiesz, jak wyglądałby dowód stwierdzenia niekompletności. Wiemy, że problem zatrzymania jest nierozstrzygalny przez TM. Oryginalny dowód wydaje się uzasadniać, ponieważ CSS może rozwiązać problem zatrzymania, który nie jest kompletny. Jeśli CSS mógłby naprawdę rozwiązać problem zatrzymania, to CSS jest silniejszy niż Maszyna Turinga, ponieważ może obliczyć coś, czego TM nie potrafi. Wiemy (na podstawie tezy Church-Turinga), że nie można zbudować maszyny silniejszej niż TM / The Lambda Calculus. Jest to zatem sprzeczność, a twoje oryginalne stwierdzenie jest nieprawidłowe.
Isaac Diamond
32

Zgodnie z tym artykułem tak nie jest . Artykuł twierdzi również, że nie jest dobrym pomysłem, aby to zrobić.

Aby zacytować jeden z komentarzy:

Nie wierzę więc, że CSS jest w pełni gotowy. Nie ma możliwości zdefiniowania funkcji w CSS. Aby system był kompletny, musi być możliwe napisanie interpretera: funkcji, która interpretuje wyrażenia oznaczające wykonanie programów. CSS nie ma zmiennych, które są bezpośrednio dostępne dla użytkownika; więc nie można nawet modelować struktury reprezentującej program do interpretacji w CSS.

DVK
źródło
4
CSS nie jest w żaden sposób wykonywalny. Osoba, która napisała cytowany komentarz, chyba tego nie rozumie. : - \
Ryan Prior
33
CSS to zestaw instrukcji dla procesora (silnika układu). Co jest w tym takiego „wykonywalnego”?
DVK
47
Kompletność Turinga nie polega tylko na tym, czy możesz pisać programy tak, jak chcesz lub w przekonaniu. Jest to matematyczna właściwość obliczalności. Więc nie możesz uwierzyć, że CSS jest kompletny w Turinga, potrzebujesz dowodu. W tym przypadku, z powodu reguły 110, CSS jest zakończony metodą Turinga.
Mikaël Mayer
15
@ MikaëlMayer - jak zauważono w wielu komentarzach w odpowiedzi „110”, która wymaga od użytkownika wykonania akcji. Jeśli działania użytkownika są wymagane, CSS bez użytkownika NIE jest Turing zakończony
DVK
1
@DVK powtarzające się naciśnięcia klawiszy wymagane w przykładzie CSS 110 nie są „działaniem” użytkownika, można je wykonać za pomocą powtarzalnego obwodu cyfrowego. Rzeczywiste maszyny Turinga wymagają pewnego rodzaju sprzętu elektrycznego do wykonania napędu, więc nie rozumiem, jak to inaczej
wygląda
6

Kompletność Turinga to nie tylko „definiowanie funkcji” lub „mieć ifs / loops / etc”. Na przykład Haskell nie ma „pętli”, rachunek lambda nie ma „ifs” itp.

Na przykład ta strona: http://experthuman.com/programming-with-nothing . Autor używa Ruby i tworzy program „FizzBuzz” z tylko zamknięciami (bez ciągów, liczb ani niczego podobnego) ...

Istnieją przykłady, w których ludzie obliczają niektóre funkcje arytmetyczne na Scali przy użyciu tylko systemu typów

Tak więc, moim zdaniem, CSS3 + HTML jest turing-complete (nawet jeśli nie możesz wykonać żadnego prawdziwego obliczenia, nie wariując)

Maurício Szabo
źródło
11
Haskell i lambda-caclculus mają rekurencję. Czy CSS? Musisz być szalony, aby wykonać prawdziwe obliczenia w Malbolge; w CSS nie ma znaczenia, jak szalony jesteś: nie zadziała, CSS nie jest kompletny, i to nie jest kwestia opinii.
JMCF125,
11
Niestety nie mogłem znaleźć Twojego komentarza na tej stronie. Ale jak zauważono w przyjętej odpowiedzi, jest to Turing-complete „(...), o ile uważasz (...) interakcje użytkownika za część„ wykonania ”CSS”. I ja nie.
JMCF125 16.10.13
20
Bez zamiaru bycia obraźliwym, kompletność nie odpowiada na niczyją opinię.
trisweb
5
@ MaurícioSzabo Nie, CSS3 plus HTML plus człowiek nieustannie wkraczający do symulacji jest w Turingu ukończony.
Lambda Fairy,
4
@LambdaFairy Dotyczy to również każdej fizycznej maszyny do pielęgnacji.
Miles Rout,
5

Podstawową kwestią jest to, że żadna maszyna napisana w HTML + CSS nie może ocenić nieskończenie wielu kroków (tzn. Nie może być „prawdziwej” rekurencji), chyba że kod jest nieskończenie długi. Pytanie, czy ta maszyna osiągnie konfigurację Hw nkrokach lub mniej, zawsze daje odpowiedź, jeśli njest skończona.

Henrik Sommerland
źródło
1
Nie wiem, gdzie w wymaganiach maszyny Turinga określono zdolność do przetwarzania nieskończonych pętli. Twój drugi punkt wydaje się nieważny. Chociaż Turing użył swojej maszyny Turinga do udowodnienia problemów związanych z obliczalnością, zasady te, podobnie jak problem zatrzymania, nie określają, czy maszyna jest maszyną Turinga, czy nie. Gdyby Maszyna Turinga uwzględniła te hipotezy jako wymagania, nie mógłby użyć maszyny Turinga do ich udowodnienia.
Adam Davis,
4
@AdamDavis Jest to całkowicie poprawny argument: jeśli istnieje algorytm, który rozwiązuje problem zatrzymania dla formalizmu pełnego Turinga, jest to równoważne z rozwiązaniem problemu zatrzymania w ogóle. Oczywiście okazało się to niemożliwe, co oznacza, że ​​jeśli problem zatrzymania można rozwiązać dla danego formalizmu, wówczas formalizm ten nie może być kompletny według Turinga. Dlatego wszystkie formalizmy, które mogą ocenić tylko skończoną liczbę kroków, nie mogą być kompletne w Turinga, łącznie z CSS.
00dani,
3
Nie jest tak, jeśli B to A! To jeśli nie B, to nie A ! Ten pierwszy potwierdza konsekwencję , którą, jak słusznie zauważyłeś, jest błędna. Ten drugi, argumentowany przez argument przeciwny , jest tym, czego używam i jest ważny. Zwróć uwagę na ostrożne stosowanie negacji w moim ostatnim komentarzu - zbudowałem ją specjalnie, aby uniknąć tego błędu.
Lambda Fairy
1
@ woojoo666 Nie. Możliwość transformacji stanu zgodnie z zestawem reguł to nie to samo, co ukończenie Turinga. Nic, co może być tylko przy skończonej liczbie kroków, nigdy nie może być kompletne. Jeśli zbiór reguł transformacji można zastosować tylko skończoną liczbę razy pytanie „Czy system kiedykolwiek osiągnie stan H?” jest zawsze rozstrzygalne i dlatego nie jest kompletne w Turingu. Implementacja automatu komórkowego, który może wykonywać tylko skończoną liczbę iteracji, nigdy nie będzie kompletna.
Henrik Sommerland
1
„I tak, również CSS są w pełni ukończone” [potrzebne źródło]
Andrea Lazzarotto,
4

Ta odpowiedź nie jest dokładna, ponieważ łączy opis UTM i samego UTM (Universal Turing Machine).

Mamy dobrą odpowiedź, ale z innej perspektywy i nie pokazuje ona bezpośrednio wad w bieżącej najlepszej odpowiedzi.

Przede wszystkim możemy się zgodzić, że człowiek może działać jako UTM. To znaczy, jeśli to zrobimy

CSS + Human == UTM

Wtedy CSSczęść jest bezużyteczna, ponieważ cała praca może być wykonana przez Humanosobę wykonującą część UTM. Aktem klikania może być UTM, ponieważ nie klikasz losowo, ale tylko w określonych miejscach.

Zamiast CSS mógłbym użyć tego tekstu ( Reguła 110 ):

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

Aby kierować moimi działaniami, a wynik będzie taki sam. Czy to oznacza, że ​​tekst UTM? Nie, to tylko dane wejściowe (opis), które inny UTM (człowiek lub komputer) może odczytać i uruchomić. Kliknięcie wystarczy, aby uruchomić dowolny UTM.

Krytyczną kwestią, której brakuje CSS, jest możliwość zmiany własnego stanu w dowolny sposób, jeśli CSS mógłby generować kliknięcia, byłby to UTM. Argument, że twoje kliknięcia są „korbowe” dla CSS, nie jest dokładny, ponieważ prawdziwy „korbowy” dla CSS to Layout Engine, który je uruchamia i powinno wystarczyć, aby udowodnić, że CSS to UTM.

Jankesi
źródło
Reguła 110 to UTM. Twój tekst to (prawdopodobnie nieco niewystarczający) opis Reguły 110, więc tak, to tekst jest (reprezentacją) UTM.
OrangeDog,
„Jeśli CSS może generować kliknięcia”, w moich projektach korzystam z wielu mikrokontrolerów AVR. Możesz albo użyć wewnętrznego zegara, który jest ograniczony do 8 MHz. Alternatywnie, możesz podłączyć zewnętrzny kryształ i przejść do 20 MHz. Ewentualnie mógłbym również dostarczyć całkowicie zewnętrzny zegar, więc nawet procesor nie napędza kryształu. Oznacza to, że mogę podłączyć przełącznik i obwód, aby go ogłosić, i dosłownie użyć go jako zegara, gdy naciskam przycisk. Czy to oznacza, że ​​przestanie być ukończony, jeśli to zrobię?
Cedric Mamo,
1
@CedricMamo Ale twoje kliknięcia zmieniają stan i musisz klikać tylko poprawne miejsca, w przeciwnym razie nie zadziałałoby. Zajrzyj dokładnie na eli.fox-epste.in/rule110-full.html Mogę kliknąć DOWOLNĄ komórkę, jeśli CSS jest wyłączony, nadal klikam prawidłowe komórki i mam UTM. Jeśli wszystko, co zrobisz, to kliknięcie jednego przycisku „dalej”, to rzeczywiście CSS to UTM, ale aby mieć coś takiego, potrzebujesz trochę JS, czyli połączenia za kliknięciem przycisku, i jak wiemy JS IS UTM. Do CSS potrzebujesz czegoś, co poprawnie zinterpretuje wynik i stan aktualizacji.
Yankes
1
@CedricMamo jakikolwiek link do niego? Teraz patrzę na kilka przykładów, ale to nie działa dla mnie. Ogólnie, jeśli dobrze rozumiem, CSS zmienia widoczność niektórych pól wyboru i używasz kart, aby przejść do następnego, a tutaj znowu mamy ukryty UTM, który nie jest CSS, ponieważ kiedy tabulujesz, pytasz przeglądarkę, aby obliczyła następną prawidłową pozycję do nawigacji, i do tego, że robi dużo skomplikowanego kodu, używa CSS, ale jest o wiele więcej. Oznacza to, że udowadniasz, że Twoja przeglądarka to UTM, a nie CSS.
Yankes
1
@CedricMamo Ale Automaty komórkowe mają w swojej własnej definicji pętlę, gdy przejście stanu jest wykonane, to jest uruchamiane ponownie, i jeszcze raz itd. Jeśli go usuniemy i pozostawimy tylko przejście stanu, automaty te nie będą już UTM. Będzie to dokładnie taka sama sytuacja jak CSS. Możemy zdefiniować dwa kroki w CA, R- stan odczytu i W- stan zapisu, normalny CA robi nieskończoną sekwencję RWRWRWRW...w przypadku CSS, który mamy tylko Ri nie mamy, Wponieważ modyfikuje rzeczy, których nie może odczytać, tylko jeśli dodamy B- akcja przeglądarki może wtedy mieć, RBRBRBR...ale wtedy BBBBBBjest na swoim własnym UTM.
Yankes
-28

CSS nie jest językiem programowania, więc kwestia kompletności jest bez znaczenia. Jeśli rozszerzenia CSS są dodawane do CSS, tak jak miało to miejsce w IE6, nowa synteza jest zupełnie inna.

CSS jest jedynie opisem stylów; nie ma żadnej logiki, a jego struktura jest płaska.

Ryan Prior
źródło
1
Również (IIRC) istnieje pewna dwuznaczność co do tego, które style mają pierwszeństwo, gdy stosuje się wiele sprzecznych (duplikatów) stylów. Są też nieco inne sposoby radzenia sobie z różnymi przeglądarkami, które implementują / interpretują style znaczników.
David R Tribble
70
„CSS nie jest językiem programowania, więc kwestia kompletności Turinga jest bez znaczenia”. Zdania tautologiczne są tautologiczne.
Adam Davis
3
Spójrz na język programowania Prolog, jeśli zastanawiasz się, dlaczego tak bardzo nie doceniasz swojej odpowiedzi.
edwin