Jelaskan Formula: dari Teorema Cook

φcell: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.

φstart: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.

φaccept: minimal 1 cell merupakan accept state

φmove mengecek apakah setiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing.

Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka:

sehingga kumpulan dari window legal adalah finite.