CSS Тьюринг завершен?

297

Насколько я знаю, CSS не завершен. Но мои знания CSS очень ограничены.

  • CSS Тьюринг завершен?
  • Рассматривает ли какой-либо из существующих проектов или комитетов языковые функции, которые могли бы обеспечить полноту Тьюринга, если это не сейчас?
css turing-complete Адам Дэвис
источник
28
Это уже сделано, если вы используете ie6. Они называются CSS-выражениями, и, по общему мнению, они ужасно сломаны и опасны. JS встроен в CSS ...
kibibu
13
@ Кибибу - Yikes! Пожалуйста, сотри эту идею из моего мозга, пока она не свалилась на себя!
ДВК
Как мог CSS , возможно , будет Тьюринг?
Слакс
1
@DVK: на самом деле вы могли бы сделать с ними несколько классных вещей - особенно в отношении независимого от разрешения макета - которые все еще хитры или причудливы в CSS, не прибегая к таблицам. Я думаю, что если бы они ограничили его использованием языка декларативных выражений без каких-либо побочных эффектов, вместо того, чтобы позволить полный доступ к скриптовому движку, это было бы лучше получить (и, возможно, также, если бы webkit сначала придумал его)
kibibu
5
@SLaks: не стоит недооценивать силу HTML5 / CSS3 :)
Никлас Б.

Ответы:

385

Вы можете закодировать Правило 110 в CSS3, так что оно завершено по Тьюрингу, если вы считаете, что соответствующий сопровождающий файл HTML и взаимодействие с пользователем являются частью «исполнения» CSS. Довольно хорошая реализация доступна, а другая реализация включена здесь:

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"/>
Развернуть фрагмент

Adam Davis
источник
2
Формальное определение (самое простое) машины Тьюринга - это просто набор состояний, набор символов, начальное состояние, набор принимающих состояний и функция перехода. Там нет кривошипа в этом. Под вычислениями мы подразумеваем, что кто-то должен верно применить функцию перехода к ленте, что в точности соответствует щелчку в этом случае. Более формально модель вычисления может рассматриваться как набор правил, которым нужно следовать, чтобы выполнять вычисления. В этом смысле я думаю, что CSS завершен по Тьюрингу.
Джон
2
Этот фрагмент не работает (Firefox 61). Я вижу сетку пустых флажков - ничего не произойдет, если вы проверите их.
OrangeDog
2
@John "CSS завершается", я чувствую себя неловко, но у меня нет проблем с "CSS такой же полный, как пара камней на пляже ". Будет ли последнее утверждение правильным?
Рафаэль Шмитц
1
@ R.Schmitz нет, в этом случае человек выбирает, куда положить камни, так что комплексная система человек + камни завершается. В вышеприведенном примере CSS нажатия клавиш Tab + Space - это простой повторяющийся процесс, похожий на схему обратной связи. Так что, если C ++ завершает тестирование с использованием компьютерного оборудования для выполнения инструкций, то не
сложно
Вот CodePen Правила 110, использующего то же решение, плюс аннотации и немного Sass, чтобы помочь СУХОЙ вещи: codepen.io/laras126/pen/OYvGZj Я написал сопроводительное сообщение в блоге, объясняющее концепции здесь: notlaura.com/is-css -Turing-полная
Notlaura
89

Одним из аспектов полноты по Тьюрингу является проблема остановки .

Это означает, что, если CSS завершен по Тьюрингу, тогда не существует общего алгоритма для определения того, будет ли программа CSS завершена или цикл будет длиться вечно.

Но мы можем вывести такой алгоритм для CSS! Вот:

  • Если таблица стилей не объявляет анимацию , она остановится.

  • Если у него есть анимация, то:

    • Если таковое animation-iteration-countесть infinite, и содержащийся селектор сопоставлен в HTML, то он не остановится.

    • В противном случае он остановится.

Вот и все. Поскольку мы только что решили проблему остановки для CSS, из этого следует, что CSS не является полным по Тьюрингу .

(Другие люди упоминали IE 6, который позволяет встраивать произвольные выражения JavaScript в CSS; это, очевидно, добавит полноту Тьюринга. Но эта функция нестандартна, и никто в здравом уме не использует ее в любом случае.)

Даниэль Вагнер поднял вопрос, который я упустил в первоначальном ответе. Он отмечает, что, хотя я рассмотрел анимацию , другие части движка стилей, такие как подбор селектора или макет, также могут привести к полноте Тьюринга. Хотя трудно привести формальные аргументы по этому поводу, я попытаюсь обрисовать, почему полнота по Тьюрингу все еще вряд ли произойдет.

Во-первых: у полных языков Turing есть некоторый способ вернуть данные обратно в себя , будь то через рекурсию или зацикливание. Но дизайн языка CSS враждебен этой обратной связи:

  • @mediaзапросы могут проверять только свойства самого браузера, такие как размер области просмотра или разрешение в пикселях. Эти свойства могут изменяться с помощью взаимодействия с пользователем или кода JavaScript (например, изменение размера окна браузера), но не только с помощью CSS.

  • ::beforeи ::afterпсевдоэлементы не считаются частью DOM и не могут быть сопоставлены другим способом.

  • Комбинаторы селекторов могут проверять только элементы выше и перед текущим элементом, поэтому их нельзя использовать для создания циклов зависимости.

  • Можно сместить элемент, когда вы наводите на него курсор , но положение обновляется только при перемещении мыши.

Этого должно быть достаточно, чтобы убедить вас, что сопоставление селектора само по себе не может быть завершено по Тьюрингу . Но как насчет макета?

Современный алгоритм верстки CSS очень сложен, с такими функциями, как Flexbox и Grid, которые мутят воду. Но даже если бы можно было запустить бесконечный цикл с компоновкой, было бы трудно использовать это для выполнения полезных вычислений. Это потому, что CSS-селекторы проверяют только внутреннюю структуру DOM, а не то, как эти элементы расположены на экране. Поэтому любое доказательство полноты по Тьюрингу с использованием системы макетов должно зависеть только от макета .

Наконец - и это, пожалуй, самая важная причина - производители браузеров заинтересованы в том, чтобы CSS не был завершен по Тьюрингу . Ограничивая язык, поставщики допускают умные оптимизации, которые делают Интернет быстрее для всех. Кроме того, Google выделяет целую ферму серверов для поиска ошибок в Chrome. Если бы был способ написать бесконечный цикл с использованием CSS, то они, вероятно, нашли бы его уже 😉

Лямбда Фея
источник
4
Когда люди говорят «CSS завершен, Тьюринг завершен», они имеют в виду «CSS, который поддерживает анимацию, - это Turing Complete» Вы можете ограничить языки программирования и сделать вывод, что они не являются Turing Complete, используя вашу логику, но вам придется указать ограничения.
Philix
36
Я думаю, что в этом ответе используется забавное определение «остановка» - конечно, не то, которое я хотел бы, если бы я задавал вопрос, по крайней мере. Вы, кажется, используете «останов» для обозначения «есть время, когда вычисленные свойства для каждого элемента перестают изменяться»; но я бы хотел, чтобы «остановка» означала «алгоритм, который преобразует декларативный CSS в вычисляемые свойства всех элементов, заканчивает работу». С последним определением, похоже, должно быть значительно больше аргументов, чем просто «нет анимации».
Даниэль Вагнер
4
Ваша логика здесь обратная. Полнота Тьюринга подразумевает, что остановка неразрешима, не означает, что остановка неразрешима, подразумевает полноту Тьюринга.
asmeurer
3
@LambdaFairy что такое проблема остановки для CSS ? Я не верю, что такая вещь существует. Проблема остановки относится только к машинам. Самая мощная вычислительная модель, которую мы имеем сегодня, - это машины Тьюринга. Ваш компьютер такой же мощный, как машина Тьюринга (без бесконечной памяти). Один только CSS не может быть определен как машина. Возможно, вы можете определить движок CSS браузера как машину, но даже тогда он может быть таким же мощным, как TM. Утверждение «проблема остановки для CSS » просто не имеет никакого смысла, если только CSS не стал новым автоматом в иерархии Хомского.
Майк Ши
3
@LambdaFairy Вы не понимаете, как будет выглядеть доказательство неполноты Тьюринга. Мы знаем, что проблема остановки неразрешима ТМ. Оригинальное доказательство, кажется, делает утверждение, потому что CSS может решить проблему остановки, которую он не решает полностью. Если CSS действительно может решить проблему остановки, тогда CSS сильнее, чем машина Тьюринга, потому что он может вычислять то, что ТМ не может. Мы знаем (по тезису Черча-Тьюринга), что машина не может быть построена сильнее, чем ТМ / Лямбда-исчисление. Следовательно, это противоречие, и ваше первоначальное утверждение неверно.
Исаак Даймонд
32

Согласно этой статье это не так . В статье также утверждается, что это не очень хорошая идея.

Цитировать из одного из комментариев:

Поэтому я не верю, что CSS завершен. Нет возможности определить функцию в CSS. Для того чтобы система была завершена по Тьюрингу, должна быть возможность написать интерпретатор: функцию, которая интерпретирует выражения, которые обозначают программы для выполнения. CSS не имеет переменных, которые непосредственно доступны пользователю; поэтому вы даже не можете смоделировать структуру, которая представляет программу для интерпретации в CSS.

DVK
источник
4
CSS не исполняется никоим образом. Человек, который написал цитируемый комментарий, похоже, не понимает этого. : - \
Райан Приор
33
CSS - это набор инструкций для процессора (движка компоновки). Что такого не исполняемого в этом?
ДВК
47
Полнота Тьюринга - это не только возможность писать программы так, как вы хотите, или убеждения. Это математическое свойство вычислимости. Таким образом, вы не можете поверить или нет, что CSS завершен по Тьюрингу, вам нужно доказательство. В этом случае, из-за правила 110, CSS завершается по Тьюрингу.
Микаэль Майер
15
@ MikaëlMayer - как отмечается во многих комментариях в ответе «110», это требует от пользователя выполнения действия. Если пользовательские действия требуются, CSS без пользователя НЕ завершается по Тьюрингу
DVK
1
@DVK повторяющиеся нажатия клавиш, требуемые примером CSS 110, не совсем пользовательское «действие», они могут выполняться повторяющейся цифровой схемой. Для настоящих машин Тьюринга требуется какое-то электрическое оборудование, чтобы управлять исполнением, поэтому я не понимаю, чем это отличается
woojoo666
6

Полнота Тьюринга заключается не только в «определении функций» или «иметь ifs / loops / etc». Например, в Haskell нет «цикла», в лямбда-исчислении нет «ifs» и т. Д.

Например, этот сайт: http://experthuman.com/programming-with-nothing . Автор использует Ruby и создает программу «FizzBuzz» только с замыканиями (без строк, чисел или чего-то в этом роде) ...

Есть примеры, когда люди вычисляют некоторые арифметические функции в Scala, используя только систему типов

Так что, да, по моему мнению, CSS3 + HTML завершен по принципу Тьюринга (даже если вы не можете сделать какие-либо реальные вычисления, не сходя с ума)

Маурисио Сабо
источник
11
У Haskell и Lambda-Caclculus есть рекурсия. Есть ли CSS? Вы должны быть сумасшедшими, чтобы делать какие-либо реальные вычисления в Malbolge; в CSS не имеет значения, насколько вы сумасшедшие: это не сработает, CSS не завершен по Тьюрингу, и это не вопрос мнения.
JMCF125
11
Извините, я не нашел других ваших комментариев на этой странице. Но, как отмечено в принятом ответе, он завершается по Тьюрингу "(...), если вы считаете (...) взаимодействие с пользователем частью" выполнения "CSS". А я нет.
JMCF125
20
Не желая быть оскорбительным, полная полнота не отвечает ни на чье мнение.
trisweb
5
@ MaurícioSzabo Нет, CSS3 плюс HTML, а также человек, постоянно следящий за симуляцией, завершены по Тьюрингу.
Лямбда Фея
4
@LambdaFairy Это также верно для каждой физической машины Тьюринга.
Майлз Рут
5

Фундаментальная проблема здесь заключается в том, что любая машина, написанная на HTML + CSS, не может оценивать бесконечно много шагов (т. Е. Не может быть «реальной» рекурсии), если код не бесконечно длинный. И вопрос, будет ли эта машина достигать конфигурации Hза nэтапы или меньше, всегда отвечает, если nон конечен.

Хенрик Соммерланд
источник
1
Я не вижу, где в требованиях машины Тьюринга указана способность обрабатывать бесконечные циклы. Ваш второй пункт не является действительным. Хотя Тьюринг использовал свою машину Тьюринга для доказательства проблем вычислимости, эти правила, такие как проблема остановки, не определяют, является ли машина машиной Тьюринга или нет. Если бы машина Тьюринга включала эти гипотезы в качестве требований, он не мог бы использовать машину Тьюринга для их доказательства.
Адам Дэвис
4
@AdamDavis Это абсолютно верный аргумент: если существует алгоритм, который решает проблему остановки для полного по Тьюрингу формализма, это эквивалентно решению проблемы остановки в целом. Конечно, это оказалось невозможным, а это означает, что если проблема остановки может быть решена для данного формализма, то этот формализм не должен быть полным по Тьюрингу. Следовательно, все формализмы, которые могут оценить только конечное число шагов, не могут быть полными по Тьюрингу, включая CSS.
00дня
3
Это не если B, то A! Это если не B, то не A ! Первое подтверждает последующее , что вы правильно указали, неверно. Последнее, аргумент от контраположительного , это то, что я использую и является действительным. Обратите внимание на осторожное использование отрицания в моем последнем комментарии - я создал его специально, чтобы избежать этой ошибки.
Лямбда Фея
1
@ woojoo666 Нет. Возможность преобразовывать состояние в соответствии с набором правил - это не то же самое, что быть завершенным по Тьюрингу. Ничто из того, что может быть выполнено только за конечное число шагов, никогда не будет полным. Если набор правил преобразований может применяться только конечное число раз, вопрос «Достигнет ли когда-либо система состояния H?» всегда разрешима, и поэтому она не является полной по Тьюрингу. Реализация клеточного автомата, который может выполнять только конечное число итераций, никогда не будет полной.
Хенрик
1
«И, да, CSS также завершены» [цитата нужна]
Андреа
4

Этот ответ не является точным, потому что он смешивает описание UTM и самого UTM (универсальной машины Тьюринга).

У нас есть хороший ответ, но с другой точки зрения, и он не показывает прямых недостатков в текущем топ-ответе.

Прежде всего мы можем согласиться, что человек может работать как UTM. Это значит, что если мы сделаем

CSS + Human == UTM

Тогда CSSчасть бесполезна, потому что всю работу может выполнять тот, Humanкто будет выполнять UTM. Акт нажатия может быть UTM, потому что вы нажимаете не случайно, а только в определенных местах.

Вместо CSS я мог бы использовать этот текст ( Правило 110 ):

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

Направлять мои действия и результат будет таким же. Это значит этот текст UTM? Нет, это только ввод (описание), который может прочитать и запустить другой UTM (человек или компьютер). Нажатие достаточно для запуска любого UTM.

Критическая часть, которой не хватает в CSS, - это возможность произвольного изменения своего состояния, если бы CSS мог генерировать щелчки, то это было бы UTM. Аргумент, что ваши щелчки являются «провальными» для CSS, не является точным, потому что реальным «провалом» для CSS является Layout Engine, который его запускает, и этого должно быть достаточно, чтобы доказать, что CSS является UTM.

Yankes
источник
Правило 110 является UTM. Ваш текст является (вероятно, немного недостаточным) описанием правила 110, так что да, этот текст является (представлением) UTM.
OrangeDog
«Если CSS может генерировать клики», я использую много микроконтроллеров AVR в своих проектах. Вы можете использовать либо внутренние часы, которые ограничены 8 МГц. Кроме того, вы можете подключить внешний кристалл и поднять до 20 МГц. В качестве альтернативы я мог бы также просто поставить полностью внешние часы, чтобы кристалл не управлял даже аппаратным обеспечением процессора. Это означает, что я действительно могу подключить переключатель и кусок схемы, чтобы отменить его, и буквально использовать это как часы, когда я нажимаю кнопку. Означает ли это, что я перестаю быть полным, если я это сделаю?
Седрик Мамо
1
@CedricMamo Но ваши клики меняют состояние, и вам нужно нажимать только правильные места, иначе это не сработает. Посмотрите точно на eli.fox-epste.in/rule110-full.html Я могу щелкнуть ЛЮБУЮ ячейку, если CSS отключен, я все еще нажимаю на правильные ячейки и имею UTM. Если все, что вы делаете, - это нажимаете одну кнопку «далее», то на самом деле CSS будет UTM, но для того, чтобы что-то подобное, вам понадобится JS - вызов на нажатие кнопки, и, как мы знаем, JS IS UTM. Для CSS вам нужно что-то, что будет правильно интерпретировать результат и состояние обновления.
Янки
1
@CedricMamo какая-нибудь ссылка на это? Прямо сейчас я смотрю на пару примеров оттуда, но у меня это не работает. В целом, если я правильно понимаю, CSS изменяет видимость некоторых флажков, и вы используете вкладки для перехода к следующему, и здесь мы снова скрыли UTM, который не является CSS, потому что, когда вы вкладываете, вы просите браузер рассчитать следующую действительную позицию для навигации, и Это делает МНОГО сложного кода, это использует CSS, но его гораздо больше. Это означает, что вы доказываете, что ваш браузер UTM, а не CSS.
Янки
1
@CedricMamo Но сотовые автоматы имеют в своем собственном определении цикл, когда переход состояния выполняется, затем он запускается снова и снова и т. Д. Если мы удалим его и оставим только этот переход состояния, то эти автоматы больше не будут UTM. Это будет точно такая же ситуация, как CSS. Мы можем определить два шага в CA, R- состояние чтения и W- состояние записи, нормальный CA делает бесконечную последовательность RWRWRWRW...в случае, если у нас есть только CSS R, а у нас его нет, Wпотому что он изменяет вещи, которые он не может прочитать, только если мы добавим B- Действие браузера, то мы могли бы иметь, RBRBRBR...но тогда BBBBBBэто само по себе UTM.
Янки
-28

CSS не является языком программирования, поэтому вопрос о полноте Тьюринга не имеет смысла. Если программные расширения добавляются в CSS, как это было в IE6, тогда этот новый синтез - это совсем другое.

CSS это просто описание стилей; у него нет никакой логики, и его структура плоская.

Райан Приор
источник
1
Также (IIRC) существует некоторая двусмысленность в отношении того, какие стили имеют приоритет при использовании нескольких конфликтующих (дублирующих) стилей. Кроме того, есть несколько разных способов, с помощью которых разные браузеры реализуют / интерпретируют стили разметки для работы.
Дэвид Р. Триббл
70
«CSS не является языком программирования, поэтому вопрос о полноте Тьюринга не имеет смысла». Тавтологические предложения тавтологические.
Адам Дэвис
3
Посмотрите на язык программирования Prolog, если вы удивляетесь, почему ваш ответ так недооценивается.
Эдвин