Является ли CSS Turing полным?

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

  • Является ли CSS Turing полным?
  • Являются ли какие-либо из существующих проектов или комитетов рассмотрением языковых особенностей, которые могли бы обеспечить полноту Тьюринга, если он не сейчас?

    Вы можете кодировать правило 110 в CSS3, так что это завершение Turing, если вы считаете, что соответствующий сопровождающий 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; } 
     

    Rule 110 in (webkit) CSS, proving Turing-completeness.

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

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

    Но мы можем получить такой алгоритм для CSS! Вот:

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

    Чтобы процитировать один из комментариев:

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

    Тьюринга – полнота не только о «определяющих функциях» или «имеет ifs / loops / etc». Например, у Haskell нет «цикла», lambda-исчисление не имеет «ifs» и т. Д. …

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

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

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

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

    Этот ответ не является точным, потому что он смешивает описание UTM и UTM (Universal Turing Machine).

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


    Прежде всего, мы можем согласиться с тем, что человек может работать как 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 – это механизм макета, который его запускает, и этого должно быть достаточно, чтобы доказать, что CSS – это UTM.

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

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

    Давайте будем гением компьютера.