O CSS Turing está completo?

297

O CSS não é, na medida em que sei, Turing completo. Mas meu conhecimento de CSS é muito limitado.

O CSS Turing está completo?
Algum dos rascunhos ou comitês existentes está considerando recursos de linguagem que podem permitir a integridade de Turing, se não estiver no momento?

css turing-complete Adam Davis
fonte

28

Já foi feito, se você usar o ie6. Eles são chamados de expressões CSS, e o consenso é que eles são terrivelmente quebrados e perigosos. JS embutido em CSS ...

kibibu

13

@Kibibu - Yikes! Por favor, apague essa ideia do meu cérebro antes que ela se dobre!

DVK

Como o CSS poderia ser completo para Turing?

SLaks

1

@ DVD: você pode realmente fazer algumas coisas legais com eles - principalmente no que diz respeito ao layout independente da resolução - que ainda são complicados ou peculiares no CSS sem recorrer a tabelas. Eu acho que se eles limitassem que fosse estritamente uma linguagem de expressão declarativa sem efeitos colaterais, em vez de permitir acesso total ao mecanismo de script, teria sido melhor recebido (e talvez também se o webkit tivesse surgido primeiro)

kibibu

5

@SLaks: Não subestime o poder do HTML5 / CSS3 :)

Niklas B.

385

Você pode codificar a Regra 110 no CSS3, para que seja concluída com Turing, desde que considere que um arquivo HTML que acompanha o produto e as interações do usuário sejam parte da "execução" do CSS. Uma implementação muito boa está disponível e outra implementação está incluída aqui:

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"/>

Expandir snippet

Adam Davis
fonte

2

A definição formal (mais simples) de Turing Machine é simplesmente uma tupla de conjunto de estados, conjunto de símbolos, estado inicial, conjunto de estados aceitantes e uma função de transição. Não há manivela nele. Por computação, queremos dizer que alguém precisa aplicar fielmente a função de transição na fita, exatamente como o clique neste caso. Mais formalmente, um modelo de computação pode ser visto como um conjunto de regras que alguém precisa seguir para fazer a computação. Nesse sentido, acho que CSS é Turing-Complete.

John

2

Este trecho não parece funcionar (Firefox 61). Vejo uma grade de caixas vazias - nada acontece se você as marcar.

OrangeDog 3/09/18

2

@John "CSS está completo" me deixa desconfortável, mas não tenho nenhum problema com "CSS está tão completo quanto algumas pedras na praia ". A última afirmação estaria correta?

Raphael Schmitz

1

@ R.Schmitz não, nesse caso, o humano está escolhendo onde colocar as rochas, por isso é o sistema combinado de humano + rochas que está completo. No exemplo de CSS acima, as teclas pressionadas tab + espaço são um processo simples de repetição, semelhante a um circuito de feedback. Então, se C ++ é turing completo utilizando hardware do computador para executar instruções, então não é um exagero dizer CSS é turing completa usando teclas pressionadas repetindo para executar instruções

woojoo666

Aqui está um CodePen da Regra 110 usando a mesma solução, além de anotações e alguns Sass para ajudar a secar as coisas: codepen.io/laras126/pen/OYvGZj Escrevi um post no blog explicando os conceitos aqui: notlaura.com/is-css -turing-complete

notlaura 16/06/19

89

Um aspecto da integridade de Turing é o problema da parada .

Isso significa que, se o CSS for Turing completo, não haverá algoritmo geral para determinar se um programa CSS terminará a execução ou o loop para sempre.

Mas podemos derivar esse algoritmo para CSS! Aqui está:

Se a folha de estilo não declarar nenhuma animação , ela será interrompida.
Se houver animações, então:
- Se qualquer um animation-iteration-counté infinite, e o seletor contendo é correspondida no HTML, então ele irá não parar.
- Caso contrário, ele será interrompido.

É isso aí. Como acabamos de resolver o problema de interrupção do CSS, segue-se que o CSS não é Turing completo .

(Outras pessoas mencionaram o IE 6, que permite incorporar expressões arbitrárias em JavaScript no CSS; isso obviamente adicionará a integridade de Turing. Mas esse recurso não é padrão e ninguém em sã consciência o usa de qualquer maneira.)

Daniel Wagner levantou um ponto que eu perdi na resposta original. Ele observa que, enquanto eu abordei animações , outras partes do mecanismo de estilo, como a correspondência de seletores ou o layout, também podem levar à perfeição de Turing. Embora seja difícil argumentar formalmente sobre isso, tentarei descrever por que é improvável que a integridade de Turing ocorra.

Primeiro: Turing linguagens completas têm alguma maneira de alimentar dados de volta , seja através de recursão ou loop. Mas o design da linguagem CSS é hostil a esse feedback:

@mediaas consultas podem apenas verificar as propriedades do próprio navegador, como tamanho da janela de exibição ou resolução de pixels. Essas propriedades podem mudar através da interação do usuário ou código JavaScript (por exemplo, redimensionando a janela do navegador), mas não apenas através do CSS.
::beforee ::afterpseudoelementos não são considerados parte do DOM e não podem ser correspondidos de nenhuma outra maneira.
Os combinadores de seletor podem inspecionar apenas os elementos acima e antes do elemento atual, portanto, eles não podem ser usados para criar ciclos de dependência.
É possível afastar um elemento quando você passa o mouse sobre ele , mas a posição só é atualizada quando você move o mouse.

Isso deve ser suficiente para convencê-lo de que a correspondência de seletor, por si só, não pode ser Turing completa . Mas e o layout?

O moderno algoritmo de layout CSS é muito complexo, com recursos como Flexbox e Grid turvando as águas. Mas mesmo que fosse possível disparar um loop infinito com layout, seria difícil aproveitar isso para executar cálculos úteis. Isso ocorre porque os seletores de CSS inspecionam apenas a estrutura interna do DOM, não como esses elementos são dispostos na tela. Portanto, qualquer prova de completude de Turing usando o sistema de layout deve depender apenas do layout .

Finalmente - e talvez este seja o motivo mais importante - os fornecedores de navegadores têm interesse em manter o CSS não Turing completo . Ao restringir o idioma, os fornecedores permitem otimizações inteligentes que tornam a web mais rápida para todos. Além disso, o Google dedica todo um farm de servidores à pesquisa de bugs no Chrome. Se houvesse uma maneira de escrever um loop infinito usando CSS, eles provavelmente já o teriam encontrado.

Lambda Fairy
fonte

4

Quando as pessoas dizem que "CSS está completo", elas significam "CSS, que suporta animações é Turing Complete". Você pode restringir as linguagens de programação e concluir que elas não são o Turing Complete usando sua lógica, mas seria necessário especificar as restrições.

philix

36

Acho que essa resposta está usando uma definição engraçada de "parada" - certamente não a que eu gostaria se estivesse fazendo a pergunta, pelo menos. Você parece usar "parar" para significar "há um momento em que as propriedades calculadas para cada elemento param de mudar"; mas eu gostaria que "halt" significasse "o algoritmo que transforma CSS declarativo nas propriedades calculadas de todos os elementos termina a execução". Com a última definição, parece que precisa haver muito mais argumentos do que apenas "não há animações".

9119 Daniel Wagner #

4

Sua lógica está ao contrário aqui. A integridade de Turing implica que a interrupção é indecidível não significa que a interrupção é indecidível implica a integridade de Turing.

precisa saber é

3

@LambdaFairy qual é o problema de interrupção do CSS ? Não acredito que isso exista. O problema da parada é relevante apenas para as máquinas. O modelo computacional mais poderoso que temos hoje são as Máquinas de Turing. Seu computador é tão poderoso quanto uma máquina de Turing (sem memória infinita). CSS sozinho não pode ser definido como uma máquina. Talvez você possa definir o mecanismo CSS de um navegador como uma máquina, mas mesmo assim ele pode ser tão poderoso quanto uma TM. A declaração "travando o problema do CSS " simplesmente não faz sentido, a menos que o CSS se torne um novo autômato na hierarquia de Chomsky.

Mike Shi

3

@LambdaFairy Você está entendendo mal como seria uma prova de incompletude. Sabemos que o problema da parada é indecidível por uma MT. A prova original parece fazer a reivindicação, porque o CSS pode resolver o problema de parada que não está completo. Se o CSS pode realmente resolver o problema de parada, o CSS é mais forte que uma Máquina de Turing, porque poderia calcular algo que uma TM não pode. Sabemos (pela tese de Church-Turing), que uma máquina não pode ser construída mais forte que um TM / The Lambda Calculus. Portanto, isso é uma contradição e sua declaração original não está correta.

Isaac Diamante

32

De acordo com este artigo, não é . O artigo também argumenta que não é uma boa ideia torná-lo um.

Para citar um dos comentários:

Portanto, não acredito que o CSS esteja completo. Não há capacidade para definir uma função no CSS. Para que um sistema seja completo, é necessário escrever um intérprete: uma função que interpreta expressões que indicam os programas a serem executados. CSS não possui variáveis diretamente acessíveis ao usuário; portanto, você não pode nem modelar a estrutura que representa o programa a ser interpretado em CSS.

DVK
fonte

4

CSS não é executável de forma alguma. A pessoa que escreveu o comentário citado não parece entender isso. : - \

Ryan Prior

33

CSS é um conjunto de instruções para um processador (mecanismo de layout). O que há de tão "executável" nisso?

DVK

47

Turing-completeness não é apenas se você pode escrever programas do jeito que você quer ou uma crença. É uma propriedade matemática sobre calculabilidade. Portanto, você não pode acreditar ou não que o CSS está completo em Turing, você precisa de uma prova. Nesse caso, devido à regra 110, o CSS é Turing-complete.

Mikaël Mayer

15

@ MikaëlMayer - como observado em muitos comentários na resposta "110", que exige que o usuário execute uma ação. Se as ações do usuário são requred, CSS sem que o usuário não é Turing completa

DVK

1

@DVK, as teclas repetidas exigidas pelo exemplo do CSS 110 não são uma "ação" do usuário, elas podem ser executadas por um circuito digital repetido. Máquinas de Turing reais exigir algum tipo de hardware elétrica para execução de carro, então eu não vejo como isso é diferente

woojoo666

6

Turing-completeness não é apenas "definir funções" ou "ter ifs / loops / etc". Por exemplo, Haskell não possui "loop", lambda-calculus não possui "ifs", etc ...

Por exemplo, este site: http://experthuman.com/programming-with-nothing . O autor usa Ruby e cria um programa "FizzBuzz" com apenas fechamentos (sem strings, números ou qualquer coisa assim) ...

Existem exemplos em que as pessoas calculam algumas funções aritméticas no Scala usando apenas o sistema de tipos

Então, sim, na minha opinião, CSS3 + HTML está completo (mesmo que você não possa fazer exatamente nenhum cálculo real sem ficar louco)

Maurício Szabo
fonte

11

Haskell e lambda-caclculus têm recursão. CSS? Você precisa ser louco para fazer qualquer cálculo real em Malbolge; em CSS, não importa o quão louco você seja: não funcionará, o CSS não está completo e isso não é uma questão de opinião.

JMCF125

11

Desculpe, não encontrei nenhum outro comentário seu nesta página. Mas, como observado na resposta aceita, é Turing-completo "(...) desde que você considere (...) as interações do usuário como parte da" execução "do CSS". E eu não.

JMCF125

20

Sem pretender ser ofensivo, a perfeição turing não responde à opinião de ninguém.

trisweb

5

@ MaurícioSzabo Não, CSS3 mais HTML e um ser humano continuamente avançando na simulação é Turing completo.

Fada Lambda

4

@LambdaFairy Isso também se aplica a todas as máquinas de turing físicas.

Miles Rout

5

A questão fundamental aqui é que qualquer máquina escrita em HTML + CSS não pode avaliar infinitamente muitas etapas (ou seja, não pode haver recursão "real"), a menos que o código seja infinitamente longo. E a questão de esta máquina alcançar a configuração Hem netapas ou menos é sempre responsável se nfor finita.

Henrik Sommerland
fonte

1

Não vejo onde nos requisitos da Máquina de Turing é especificada a capacidade de processar loops infinitos. Seu segundo ponto não parece ser válido. Enquanto Turing usou sua Máquina de Turing para provar questões de computabilidade, essas regras, como o problema da parada, não determinam se uma máquina é uma máquina de torção ou não. Se a Máquina de Turing incluísse essas hipóteses como requisitos, ele não poderia ter usado a máquina de turing para prová-las.

Adam Davis

4

@AdamDavis É um argumento totalmente válido: se existe um algoritmo que resolve o problema de parada para um formalismo completo de Turing, isso é equivalente a resolver o problema de parada em geral. Obviamente, isso foi provado impossível, o que significa que, se o problema da parada puder ser resolvido para um determinado formalismo, esse formalismo não deverá ser Turing completo. Portanto, todos os formalismos que apenas podem avaliar um número finito de etapas não podem ser completos para Turing, incluindo CSS.

00dani

3

É não se B então A! É se não B, então não A ! O primeiro está afirmando o conseqüente , que você corretamente indica que está errado. O último, argumento por contrapositivo , é o que eu uso e é válido. Observe o uso cuidadoso da negação no meu último comentário - eu a construí especificamente para evitar essa falácia.

Fada Lambda

1

@ woojoo666 Não. Ser capaz de transformar o estado de acordo com um conjunto de regras não é o mesmo que estar completo com Turing. Nada que possa apenas por um número finito de etapas pode estar completo. Se o conjunto de regras de transformações puder ser aplicado apenas um número finito de vezes a pergunta "O sistema atingirá algum estado H?" é sempre decidível e, portanto, não é Turing completo. Uma implementação de um autômato celular que só pode executar um número finito de iterações nunca pode ser concluída.

Henrik Sommerland

1

“E, sim, também as CSS estão completas” [citação necessário]

Andrea Lazzarotto

4

Esta resposta não é precisa porque combina a descrição do UTM e do próprio UTM (Universal Turing Machine).

Temos uma boa resposta, mas sob uma perspectiva diferente e ela não mostra falhas diretamente na resposta atual atual.

Antes de tudo, podemos concordar que humanos podem funcionar como UTM. Isso significa que se fizermos

CSS + Human == UTM

Então CSSparte é inútil, porque todo o trabalho pode ser feito por Humanquem fará a parte UTM. O ato de clicar pode ser UTM, porque você não clica aleatoriamente, mas apenas em locais específicos.

Em vez de CSS, eu poderia usar este texto ( Regra 110 ):

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

Orientar minhas ações e resultados será o mesmo. Isso significa esse texto UTM? Não, isso é apenas uma entrada (descrição) que outro UTM (humano ou computador) pode ler e executar. Clicar é suficiente para executar qualquer UTM.

Parte crítica que falta ao CSS é a capacidade de alterar seu próprio estado de maneira arbitrária; se o CSS gerar cliques, seria UTM. O argumento de que seus cliques são "crank" para CSS não é preciso, porque o "crank" real para CSS é o Layout Engine que o executa e deve ser suficiente para provar que CSS é UTM.

Yankes
fonte

A regra 110 é uma UTM. Seu texto é uma descrição (provavelmente um pouco insuficiente) da Regra 110, portanto, sim, esse texto é um (representação de a) UTM.

OrangeDog

"Se o CSS pode gerar cliques", uso muitos microcontroladores AVR em meus projetos. Você pode usar um relógio interno, limitado a 8MHz. Como alternativa, você pode conectar um cristal externo e subir até 20MHz. Como alternativa, eu também poderia fornecer um relógio completamente externo, para que nem mesmo o hardware da CPU estivesse dirigindo o cristal. Significando que eu posso realmente conectar um interruptor e um pedaço de circuito para rejeitá-lo, e literalmente usá-lo como um relógio comigo pressionando o botão. Isso significa que ele deixa de ser completo se eu fizer isso?

Cedric Mamo

1

@CedricMamo Mas seus cliques mudam de estado e você precisa clicar apenas nos locais corretos, caso contrário, não funcionaria. Olhe exatamente em eli.fox-epste.in/rule110-full.html Posso clicar em QUALQUER célula, se o CSS estiver desativado, ainda clico nas células corretas e tenho UTM. Se tudo o que você fizer fosse clicar em um botão "próximo", na verdade o CSS seria UTM, mas para ter algo assim, você precisaria ter algum JS chamado por clique de botão e, como sabemos, JS IS UTM. Para CSS, você precisa ter algo que interpretará corretamente o resultado e atualize o estado.

Yankes 11/05/19

1

@CedricMamo algum link para ele? No momento, olho para alguns exemplos de lá, mas isso não funciona para mim. No geral, se eu entendi corretamente, o CSS altera a visibilidade de algumas caixas de seleção e você usa guias para navegar para a próxima, e aqui novamente ocultamos o UTM que não é CSS, porque quando você guia, você pede ao navegador para calcular a próxima posição válida para navegar, e Para fazer muito código complexo, isso usa CSS, mas é muito mais. Isso significa que você prova que seu navegador é UTM e não CSS.

Yankes

1

@CedricMamo Mas os autômatos celulares têm, em sua própria definição, um loop, quando a transição de estado é feita, depois é executada novamente e novamente etc. Se removê-lo e deixar apenas essa transição de estado, esse autômato não será mais o UTM. Esta será exatamente a mesma situação que CSS. Podemos definir duas etapas na CA: R- estado de leitura e W- estado de gravação, CA normal: sequência infinita RWRWRWRW...no caso de CSS que temos apenas R, e não o temos Wporque modifica coisas que não pode ler, apenas se adicionarmos B- ação do navegador, então poderíamos ter, RBRBRBR...mas então BBBBBBé por conta própria UTM.

Yankes 17/05/19

-28

O CSS não é uma linguagem de programação; portanto, a questão da perfeição turing é sem sentido. Se extensões de programação são adicionadas ao CSS, como foi o caso no IE6, essa nova síntese é uma coisa totalmente diferente.

CSS é apenas uma descrição de estilos; não possui lógica e sua estrutura é plana.

Ryan Prior
fonte

1

Além disso (IIRC), há alguma ambiguidade sobre quais estilos têm precedência quando vários estilos conflitantes (duplicados) são usados. E há as maneiras ligeiramente diferentes pelas quais diferentes navegadores implementam / interpretam estilos de marcação para lidar.

David R Tribble

70

"O CSS não é uma linguagem de programação; portanto, a questão da perfeição turing é sem sentido". Frases tautológicas são tautológicas.

Adam Davis

3

Dê uma olhada na linguagem de programação Prolog se você se pergunta por que sua resposta é tão prejudicada.

Edwin

O CSS Turing está completo?

Respostas: