Apakah CSS Turing lengkap?

297

CSS tidak, sejauh yang saya tahu, Turing selesai. Tetapi pengetahuan saya tentang CSS sangat terbatas.

  • Apakah CSS Turing lengkap?
  • Apakah ada draf atau komite yang ada yang mempertimbangkan fitur bahasa yang memungkinkan kelengkapan Turing jika tidak sekarang?
css turing-complete Adam Davis
sumber
28
Sudah dilakukan, jika Anda menggunakan ie6. Mereka disebut ekspresi CSS, dan konsensus adalah mereka sangat rusak dan berbahaya. JS tertanam dalam CSS ...
kibibu
13
@Kibibu - Astaga! Harap hapus ide itu dari otak saya sebelum terlipat dengan sendirinya!
DVK
Bagaimana mungkin CSS mungkin menjadi Turing-lengkap?
SLaks
1
@DVK: Anda benar-benar dapat melakukan beberapa hal keren dengan mereka - terutama berkaitan dengan resolusi tata letak independen - yang masih rumit atau aneh di CSS tanpa menggunakan tabel. Saya pikir jika mereka membatasinya hanya sebagai bahasa ekspresi deklaratif tanpa efek samping daripada memungkinkan akses penuh ke mesin skrip, itu akan lebih baik diterima (dan mungkin juga jika webkit datang dengan itu terlebih dahulu)
kibibu
5
@SLaks: Jangan meremehkan kekuatan HTML5 / CSS3 :)
Niklas B.

Jawaban:

385

Anda dapat menyandikan Aturan 110 dalam CSS3, jadi Turing-complete selama Anda menganggap file HTML yang sesuai dan interaksi pengguna sebagai bagian dari "eksekusi" CSS. Sebuah implementasi yang cukup baik tersedia, dan implementasi lain termasuk di sini:

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

Adam Davis
sumber
2
Definisi formal (paling sederhana) dari Turing Machine hanyalah sebuah tuple dari state set, simbol set, state awal, state set yang menerima dan fungsi transisi. Tidak ada engkol di dalamnya. Dengan perhitungan kami maksudkan seseorang harus menerapkan fungsi transisi dengan setia pada rekaman yang persis seperti mengklik dalam kasus ini. Secara lebih formal, model perhitungan dapat dilihat sebagai seperangkat aturan yang harus diikuti seseorang untuk melakukan perhitungan. Dalam hal itu, saya pikir CSS Turing-Complete.
John
2
Cuplikan ini sepertinya tidak berfungsi (Firefox 61). Saya melihat kotak centang kotak kosong - tidak ada yang terjadi jika Anda memeriksanya.
OrangeDog
2
@ John "CSS is turing complete" membuat saya tidak nyaman, tapi saya tidak punya masalah dengan "CSS sama turingnya dengan beberapa batu di pantai ". Apakah pernyataan yang terakhir itu benar?
Raphael Schmitz
1
@ R.Schmitz tidak, dalam hal ini manusia memilih di mana meletakkan batu, jadi itu adalah sistem gabungan batu + manusia yang turing lengkap. Dalam contoh CSS di atas, tab + spasi penekanan tombol adalah proses berulang sederhana, mirip dengan mengatakan, rangkaian umpan balik. Jadi jika C + + turing lengkap menggunakan perangkat keras komputer untuk menjalankan instruksi, maka itu tidak
berlebihan
Berikut adalah CodePen dari Aturan 110 yang menggunakan solusi yang sama, ditambah penjelasan dan beberapa Sass untuk membantu hal-hal KERING: codepen.io/laras126/pen/OYvGZj Saya menulis posting blog yang menyertai menjelaskan konsep-konsep di sini: notlaura.com/is-css -turing-complete
notlaura
89

Salah satu aspek dari kelengkapan Turing adalah masalah penghentian .

Ini berarti bahwa, jika CSS sudah selesai, maka tidak ada algoritma umum untuk menentukan apakah program CSS akan selesai berjalan atau berulang selamanya.

Tapi kita bisa mendapatkan algoritma untuk CSS! Ini dia:

  • Jika stylesheet tidak menyatakan animasi apa pun , maka itu akan berhenti.

  • Jika memang memiliki animasi, maka:

    • Jika ada animation-iteration-countadalah infinite, dan pemilih yang mengandung cocok di HTML, maka akan tidak menghentikan.

    • Kalau tidak, itu akan berhenti.

Itu dia. Karena kami baru saja menyelesaikan masalah penghentian untuk CSS, itu berarti bahwa CSS tidak Turing lengkap .

(Orang lain telah menyebutkan IE 6, yang memungkinkan untuk menanamkan ekspresi JavaScript sewenang-wenang dalam CSS; yang jelas akan menambah kelengkapan Turing. Tetapi fitur itu tidak standar, dan toh tidak ada orang waras yang menggunakannya).

Daniel Wagner mengemukakan satu hal yang saya lewatkan dalam jawaban aslinya. Dia mencatat bahwa sementara saya sudah membahas animasi , bagian lain dari mesin gaya seperti pencocokan pemilih atau tata letak dapat menyebabkan kelengkapan Turing juga. Meskipun sulit untuk membuat argumen formal tentang ini, saya akan mencoba untuk menguraikan mengapa kelengkapan Turing masih tidak mungkin terjadi.

Pertama: Turing bahasa lengkap memiliki beberapa cara untuk memasukkan data kembali ke dalam dirinya sendiri , apakah itu melalui rekursi atau perulangan. Tetapi desain bahasa CSS memusuhi umpan balik ini:

  • @mediakueri hanya dapat memeriksa properti browser itu sendiri, seperti ukuran viewport atau resolusi piksel. Properti ini dapat berubah melalui interaksi pengguna atau kode JavaScript (misalnya mengubah ukuran jendela browser), tetapi tidak melalui CSS saja.

  • ::beforedan ::afterpseudo-elemen tidak dianggap sebagai bagian dari DOM , dan tidak dapat dicocokkan dengan cara lain.

  • Combinator pemilih hanya dapat memeriksa elemen di atas dan sebelum elemen saat ini, sehingga mereka tidak dapat digunakan untuk membuat siklus ketergantungan.

  • Dimungkinkan untuk menggeser elemen ketika Anda mengarahkan mouse ke atasnya , tetapi posisinya hanya diperbarui ketika Anda menggerakkan mouse.

Itu seharusnya cukup untuk meyakinkan Anda bahwa pencocokan pemilih, sendiri, tidak bisa Turing lengkap . Tapi bagaimana dengan tata letak?

Algoritma tata letak CSS modern sangat kompleks, dengan fitur-fitur seperti Flexbox dan Grid memperkeruh perairan. Tetapi bahkan jika itu mungkin untuk memicu loop tak terbatas dengan tata letak, akan sulit untuk memanfaatkan ini untuk melakukan perhitungan yang bermanfaat. Itu karena penyeleksi CSS hanya memeriksa struktur internal DOM, bukan bagaimana elemen-elemen ini diletakkan di layar. Jadi setiap bukti kelengkapan Turing menggunakan sistem tata letak harus bergantung pada tata letak saja .

Akhirnya - dan ini mungkin alasan paling penting - vendor browser tertarik untuk menjaga agar CSS tidak lengkap . Dengan membatasi bahasa, vendor memungkinkan untuk optimasi pintar yang membuat web lebih cepat untuk semua orang. Selain itu, Google mendedikasikan seluruh server pertanian untuk mencari bug di Chrome. Jika ada cara untuk menulis infinite loop menggunakan CSS, maka mereka mungkin sudah menemukannya 😉

Lambda Fairy
sumber
4
Ketika orang mengatakan "CSS sudah selesai" mereka berarti "CSS, yang mendukung animasi adalah Lengkap". Anda dapat membatasi bahasa pemrograman dan menyimpulkan mereka tidak Turing Lengkap menggunakan logika Anda, tetapi Anda harus menentukan batasannya.
philix
36
Saya pikir jawaban ini menggunakan definisi lucu "berhenti" - tentu saja bukan yang saya inginkan jika saya mengajukan pertanyaan, setidaknya. Anda tampaknya menggunakan "berhenti" untuk berarti "ada waktu di mana properti yang dihitung untuk setiap elemen berhenti berubah"; tapi saya ingin "menghentikan" berarti "algoritma yang mengubah CSS deklaratif menjadi properti yang dikomputasi dari semua elemen yang selesai berjalan". Dengan definisi yang terakhir, tampaknya perlu ada lebih banyak argumen daripada sekadar "tidak ada animasi".
Daniel Wagner
4
Logika Anda mundur di sini. Kelengkapan Turing menyiratkan bahwa penghentian tidak dapat diputuskan tidak berarti bahwa penghentian itu diputuskan menyiratkan kelengkapan Turing.
penanggung jawab
3
@LambdaFairy apa masalah penghentian untuk CSS ? Saya tidak percaya hal seperti itu ada. Masalah penghentian hanya relevan untuk mesin. Model komputasi paling kuat yang kita miliki saat ini adalah Turing Machines. Komputer Anda sekuat Mesin Turing (tanpa memori tak terbatas). CSS saja tidak bisa didefinisikan sebagai mesin. Mungkin Anda bisa mendefinisikan mesin CSS dari browser sebagai mesin, tetapi meskipun begitu ia hanya bisa sekuat TM. Pernyataan "menghentikan masalah untuk CSS " sama sekali tidak masuk akal, kecuali CSS telah menjadi otomat baru dalam hierarki Chomsky.
Mike Shi
3
@LambdaFairy Anda salah paham akan terlihat seperti apa bukti dari ketidaklengkapan nantinya. Kita tahu bahwa masalah penghentian tidak dapat diputuskan oleh TM. Bukti asli tampaknya membuat klaim karena CSS dapat menyelesaikan masalah penghentian yang belum selesai. Jika CSS benar-benar dapat memecahkan masalah penghentian, maka CSS lebih kuat daripada Mesin Turing karena dapat menghitung sesuatu yang tidak dapat dilakukan TM. Kita tahu (oleh Tesis Gereja-Turing), bahwa mesin tidak dapat dibangun yang lebih kuat dari TM / The Lambda Calculus. Oleh karena itu, ini adalah kontradiksi, dan pernyataan asli Anda tidak benar.
Isaac Diamond
32

Sesuai artikel ini, tidak . Artikel itu juga berpendapat bahwa bukan ide yang baik untuk membuatnya.

Mengutip dari salah satu komentar:

Jadi, saya tidak percaya bahwa CSS sudah selesai. Tidak ada kemampuan untuk mendefinisikan suatu fungsi dalam CSS. Agar suatu sistem dapat menyelesaikan-turing, harus dimungkinkan untuk menulis seorang juru bahasa: suatu fungsi yang menginterpretasikan ekspresi yang menunjukkan program untuk dieksekusi. CSS tidak memiliki variabel yang dapat diakses langsung oleh pengguna; jadi Anda bahkan tidak dapat memodelkan struktur yang mewakili program untuk ditafsirkan dalam CSS.

DVK
sumber
4
CSS tidak dapat dieksekusi dengan cara apa pun. Orang yang menulis komentar yang dikutip sepertinya tidak mengerti itu. : - \
Ryan Sebelum
33
CSS adalah seperangkat instruksi untuk prosesor (layout engine). Apa yang tidak bisa "dieksekusi" tentang itu?
DVK
47
Kelengkapan Turing bukan hanya tentang apakah Anda dapat menulis program seperti yang Anda inginkan atau keyakinan. Ini adalah properti matematika tentang kalkulasi. Jadi Anda tidak percaya atau tidak bahwa CSS itu Turing-complete, Anda perlu bukti. Dalam hal ini, karena aturan 110, CSS adalah Turing-complete.
Mikaël Mayer
15
@ MikaëlMayer - sebagaimana dicatat dalam banyak komentar di jawaban "110", yang mengharuskan pengguna untuk melakukan suatu tindakan. Jika tindakan pengguna diperlukan, CSS tanpa pengguna TIDAK Turing selesai
DVK
1
@DVK penekanan tombol berulang yang diperlukan oleh contoh CSS 110 tidak cukup "aksi" pengguna, mereka dapat dilakukan oleh sirkuit digital berulang. Mesin turing yang sebenarnya membutuhkan semacam perangkat keras listrik untuk mendorong eksekusi, jadi saya tidak melihat bagaimana ini berbeda
woojoo666
6

Kelengkapan Turing tidak hanya tentang "mendefinisikan fungsi" atau "memiliki ifs / loop / etc". Misalnya, Haskell tidak memiliki "loop", lambda-calculus tidak memiliki "seandainya", dll ...

Misalnya, situs ini: http://experthuman.com/programming-with-nothing . Penulis menggunakan Ruby dan membuat program "FizzBuzz" dengan hanya penutupan (tanpa string, angka, atau apa pun seperti itu) ...

Ada contoh ketika orang menghitung beberapa fungsi aritmatika pada Scala hanya menggunakan sistem tipe

Jadi, ya, menurut saya, CSS3 + HTML sudah selesai-turing (bahkan jika Anda tidak bisa melakukan perhitungan nyata dengan itu tanpa menjadi gila)

Maurício Szabo
sumber
11
Haskell dan lambda-caclculus mengalami rekursi. Apakah CSS? Anda harus gila untuk melakukan perhitungan nyata di Malbolge; di CSS, tidak masalah seberapa gila Anda: itu tidak akan berhasil, CSS tidak turing-lengkap, dan itu bukan masalah pendapat.
JMCF125
11
Maaf, saya tidak dapat menemukan komentar Anda di halaman ini. Tetapi seperti yang disebutkan dalam jawaban yang diterima, Turing-complete "(...) asalkan Anda menganggap (...) interaksi pengguna sebagai bagian dari" eksekusi "CSS". Dan saya tidak.
JMCF125
20
Tanpa bermaksud menyinggung, turing kelengkapan tidak menanggapi pendapat siapa pun.
trisweb
5
@ MaurícioSzabo Tidak, CSS3 plus HTML plus manusia yang terus melangkah simulasi adalah Turing selesai.
Lambda Fairy
4
@LambdaFairy Itu juga berlaku untuk setiap mesin turing fisik.
Miles Rout
5

Masalah mendasar di sini adalah bahwa mesin apa pun yang ditulis dalam HTML + CSS tidak dapat mengevaluasi banyak langkah tanpa batas (yaitu tidak ada rekursi "nyata") kecuali kodenya panjang tak terhingga. Dan pertanyaannya apakah mesin ini akan mencapai konfigurasi Hdalam beberapa nlangkah atau kurang selalu dapat dijawab jika nterbatas.

Henrik Sommerland
sumber
1
Saya tidak melihat di mana dalam Persyaratan Mesin Turing kemampuan untuk memproses loop tak terbatas ditentukan. Poin kedua Anda tampaknya tidak valid. Sementara Turing menggunakan Mesin Turing untuk membuktikan masalah kemampuan komputasi, aturan-aturan ini, seperti masalah penghentian, tidak menentukan apakah suatu mesin adalah mesin turing atau tidak. Jika Mesin Turing memasukkan hipotesis ini sebagai persyaratan, ia tidak mungkin menggunakan mesin turing untuk membuktikannya.
Adam Davis
4
@AdamDavis Ini adalah argumen yang benar-benar valid: jika ada algoritma yang memecahkan masalah penghentian untuk formalisme lengkap Turing, itu setara dengan memecahkan masalah penghentian secara umum. Tentu saja, ini terbukti tidak mungkin, yang berarti bahwa jika masalah penghentian dapat diselesaikan untuk formalisme yang diberikan, maka formalisme itu tidak boleh Turing-lengkap. Oleh karena itu, semua formalisme yang hanya dapat mengevaluasi sejumlah langkah hingga tidak dapat diselesaikan Turing, termasuk CSS.
00dani
3
Ini bukan jika B maka A! Jika bukan B maka bukan A ! Yang pertama menegaskan konsekuensinya , yang Anda benar menunjukkan salah. Yang terakhir, argumen oleh kontrapositif , adalah apa yang saya gunakan dan valid. Perhatikan penggunaan negasi dengan hati-hati dalam komentar terakhir saya - saya membangunnya secara khusus untuk menghindari kesalahan itu.
Lambda Fairy
1
@ woojoo666 Tidak. Memiliki kemampuan untuk mengubah keadaan menurut seperangkat aturan tidak sama dengan menjadi Turing lengkap. Tidak ada yang bisa hanya untuk sejumlah langkah terbatas yang dapat diselesaikan sepenuhnya. Jika seperangkat aturan transformasi hanya dapat diterapkan beberapa kali pertanyaan "Apakah sistem akan pernah mencapai negara H?" selalu decidable dan karenanya Turing tidak lengkap. Implementasi otomat seluler yang hanya dapat melakukan iterasi terbatas hingga tidak pernah dapat dilakukan secara lengkap.
Henrik Sommerland
1
"Dan, ya, juga CSS sedang menyelesaikan lengkap" [rujukan?]
Andrea Lazzarotto
4

Ini jawabannya tidak akurat karena mencampur deskripsi UTM dan UTM sendiri (Universal Turing Machine).

Kami memiliki jawaban yang baik tetapi dari sudut pandang yang berbeda dan tidak menunjukkan kelemahan langsung pada jawaban teratas saat ini.

Pertama-tama kita dapat sepakat bahwa manusia dapat bekerja sebagai UTM. Ini artinya jika kita melakukannya

CSS + Human == UTM

Maka CSSbagian tidak berguna karena semua pekerjaan dapat dilakukan oleh Humansiapa yang akan melakukan bagian UTM. Tindakan mengklik dapat berupa UTM, karena Anda tidak mengklik secara acak tetapi hanya di tempat tertentu.

Alih-alih CSS saya bisa menggunakan teks ini ( Aturan 110 ):

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

Untuk memandu tindakan dan hasil saya akan sama. Ini berarti teks ini UTM? Tidak, ini hanya input (deskripsi) yang dapat dibaca dan dijalankan UTM (manusia atau komputer) lainnya. Mengklik sudah cukup untuk menjalankan UTM apa pun.

Bagian penting yang tidak dimiliki CSS adalah kemampuan untuk mengubah keadaannya sendiri secara sewenang-wenang, jika CSS dapat menghasilkan klik maka itu adalah UTM. Argumen bahwa klik Anda "engkol" untuk CSS tidak akurat karena "engkol" nyata untuk CSS adalah Layout Engine yang menjalankannya dan itu harus cukup untuk membuktikan bahwa CSS adalah UTM.

Yankes
sumber
Aturan 110 adalah UTM. Teks Anda adalah deskripsi (mungkin sedikit tidak mencukupi) dari Aturan 110, jadi ya teks itu adalah (representasi dari a) UTM.
OrangeDog
"Jika CSS dapat menghasilkan klik" Saya menggunakan banyak mikrokontroler AVR dalam proyek saya. Anda dapat menggunakan jam internal, yang terbatas pada 8MHz. Atau, Anda dapat menghubungkan kristal eksternal dan mencapai 20MHz. Atau saya juga bisa menyediakan jam sepenuhnya eksternal sehingga bahkan perangkat keras cpu yang sebenarnya mengemudi kristal. Berarti saya benar-benar dapat memasang saklar dan sepotong sirkuit untuk menghilangkannya, dan secara harfiah menggunakannya sebagai jam dengan saya menekan tombol. Apakah itu berarti itu berhenti menjadi turing lengkap jika saya melakukan itu?
Cedric Mamo
1
@CedricMamo Tapi klik Anda berubah keadaan, dan Anda hanya perlu mengklik tempat yang benar, jika tidak akan berhasil. Lihat persis di eli.fox-epste.in/rule110-full.html Saya dapat mengklik sel APA PUN, jika CSS dinonaktifkan saya masih mengklik sel yang benar dan memiliki UTM. Jika semua yang Anda lakukan akan mengklik satu tombol "berikutnya" maka memang CSS akan menjadi UTM, tetapi untuk memiliki sesuatu seperti itu Anda perlu memiliki beberapa JS yaitu panggilan per klik tombol, dan seperti yang kita ketahui JS IS UTM. Untuk CSS Anda perlu memiliki sesuatu yang akan dengan benar menafsirkan hasil dan memperbarui keadaan.
Yankes
1
@CedricMamo ada tautan ke sana? Saat ini saya melihat beberapa contoh dari sana tetapi tidak berhasil untuk saya. Secara keseluruhan, jika saya mengerti dengan benar perubahan visibilitas CSS dari beberapa kotak centang dan Anda menggunakan tab untuk menavigasi ke yang berikutnya, dan di sini kami telah lagi menyembunyikan UTM yang bukan CSS, karena ketika Anda tab Anda meminta browser untuk menghitung posisi valid berikutnya untuk menavigasi, dan untuk membuat mereka melakukan BANYAK kode kompleks, ini menggunakan CSS tetapi lebih banyak. Ini berarti Anda membuktikan bahwa peramban Anda bukan UTM.
Yankes
1
@CedricMamo Tapi Cellata automata memiliki definisi sendiri loop, ketika transisi keadaan dilakukan kemudian dijalankan lagi, dan lagi dll. Jika kita menghapusnya dan hanya meninggalkan transisi keadaan ini maka automata ini tidak akan menjadi UTM lagi. Ini akan menjadi situasi yang persis sama dengan CSS. Kita dapat mendefinisikan dua langkah dalam CA, R- status baca, dan W- status tulis, CA normal melakukan urutan tak terbatas RWRWRWRW...untuk CSS yang kita miliki saja R, dan kita tidak memilikinya Wkarena memodifikasi hal-hal yang tidak dapat dibaca, hanya jika kita menambahkan B- Tindakan browser maka kita bisa RBRBRBR...tetapi kemudian BBBBBBpada UTM sendiri.
Yankes
-28

CSS bukan bahasa pemrograman, jadi pertanyaan tentang kelengkapan-turing adalah yang tidak berarti. Jika ekstensi pemrograman ditambahkan ke CSS seperti yang terjadi di IE6 maka sintesis baru adalah hal yang sama sekali berbeda.

CSS hanyalah deskripsi gaya; tidak memiliki logika, dan strukturnya datar.

Ryan Prior
sumber
1
Juga (IIRC), ada beberapa ambiguitas tentang gaya mana yang diutamakan ketika banyak gaya yang saling bertentangan (duplikat) digunakan. Dan kemudian ada cara yang sedikit berbeda di mana browser yang berbeda menerapkan / menginterpretasikan gaya markup untuk menangani.
David R Tribble
70
"CSS bukan bahasa pemrograman, jadi pertanyaan tentang kelengkapan-turing adalah yang tidak berarti." Kalimat tautologis bersifat tautologis.
Adam Davis
3
Lihatlah Prolog bahasa pemrograman jika Anda bertanya-tanya mengapa jawaban Anda terlalu banyak dikurung.
edwin