Mesin Turing Multi-tape

Mesin Turing Multi-tape memiliki banyak tape dimana setiap tape diakses dengan head terpisah. Setiap kepala dapat bergerak secara independen dari kepala lainnya. Awalnya input ada di tape 1 dan lainnya kosong. Pada awalnya, pita pertama ditempati oleh masukan dan pita lainnya dibiarkan kosong. Selanjutnya, mesin membaca simbol yang berurutan di bawah kepalanya dan TM mencetak simbol pada setiap pita dan menggerakkan kepalanya.

Mesin Turing Multi-tape secara formal dapat digambarkan sebagai 6-tuple (Q, X, B, δ, q ₀ , F) di mana -

• Q adalah sekumpulan negara yang terbatas

• X adalah alfabet tape

• B adalah simbol kosong

• δ adalah hubungan negara bagian dan simbol di mana

  δ: Q × X ^k → Q × (X × {Left_shift, Right_shift, No_shift}) ^k

  dimana ada k jumlah kaset

• q₀ adalah keadaan awal

• F adalah himpunan keadaan akhir

Note - Setiap mesin Turing Pita Ganda memiliki mesin Turing pita tunggal yang setara.