Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Luckas-bot (bicara | kontrib) k r2.7.1) (bot Menambah: en:Cook–Levin theorem |
k Bot: Penggantian teks otomatis (-diantara +di antara) |
||
Baris 44:
* cell[i,j] : cell dengan lokasi baris ke-i dan kolom ke -j
* Suatu Tableau tanpa aturan tertentu dapat berisi konfigurasi yang invaild, misal : cell berisi ''multiple symbols'' , tidak dimulai dengan input w dan state q<sub>0</sub> , konfigurasi neighbour tidak berkorespondensi dengan aturan transisi, dan sebagainya. Sehingga harus dihasilkan formula Boolean yang memaksa tableau agar valid dan menghasilkan result pada accet state.
* Sebuah cell dapat berisi tepat 1 symbol
* Konfigurasi pertama harus berhubungan dengan input w dan state awal q. (φ <sub>start</sub>)
* Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φ<sub>move</sub>)
| |||