VARIASI DAN KOMBINASI PADA MESIN TURING
Variasi-Variasi Mesin Turing
- Terdapat beberapa variasi mesin Turing. Meskipun terdapat lebih dari satu variasi, namun tidak ada peningkatan kemampuan pengenalan bahasa dari masing-masing varian.
- Dengan kata lain, variasi-variasi mesin Turing tersebut merupakan mesin yang ekivalen.
- Beberapa variasi mesin Turing:
Mesin Turing ini memiliki pita simbol yang tidak terbatas pada kedua ujungnya. Pada mesin Turing biasa, head tidak dapat bergerak lebih kiri dari sisi pita.
Multitrack
Mesin Turing ini memiliki sebuah pita yang memiliki lebih dari satu jalur (track) penulisan atau pembacaan simbol. Simbol-simbol yang berada pada “kolom” yang sama akan dibaca sekaligus oleh sebuah head tunggal.
Mesin Turing ini memiliki sebuah pita yang memiliki lebih dari satu jalur (track) penulisan atau pembacaan simbol. Simbol-simbol yang berada pada “kolom” yang sama akan dibaca sekaligus oleh sebuah head tunggal.
Multitape
Mesin Turing ini memiliki beberapa pita yang masing-masing dapat dibaca oleh head yang saling bebas. Setiap pita memiliki head tersendiri. Aksi yang dilakukan salah satu head pada pitanya tidak bergantung dari aksi head yang lain.
Non-deterministic
Mesin Turing ini memiliki satu pita yang terbatas pada salah satu ujungnya. Untuk setiap kombinasi status dan simbol pita yang sedang dibaca, mesin ini dapat memiliki sejumlah gerakan berikutnya.
Multi-dimensional tape
Mesin Turing ini memiliki pita yang multi dimensi. Mesin Turing biasa memiliki pita yang berdimensi satu. Untuk pita dua dimensi berarti head dapat berpindah dari satu sel ke sel lain yang terletak pada suatu bidang datar.
Multihead
Mesin Turing ini mirip dengan mesin Turing multitape, hanya bedanya mesin Turing multihead hanya satu pita. Setiap head pada pita tersebut dapat beraksi saling bebas satu sama lainnya.
Bentuk representasi diagram transisi lain
dari Mesin Turing yaitu persilangan
antara mesin Mealy dan Moore.
Kombinasi Mesin Turing
- Kombinasi Mesin Turing akan menghasilkan bentuk yang lebih kompleks.
- Kedua mesin mendapat masukan dan pita yang sama (∑ dan Γ sama).
- Ketika salah satu mengakhiri eksekusinya, maka mesin yang ke dua akan memulai bekerja.
- Mesin ke dua akan memulai pekerjaannya dari posisi yang ditinggalkan oleh mesin pertama.
Contoh ;
M1 = (Q1
, Ʃ, Γ, δ1
, S1
, B, F1
)
M2 = (Q2
, Ʃ, Γ, δ2
, S2
, B, F2
)
akan dibentuk M3 yang merupakan
kombinasi dari M1 dan M2 atau
M3 = M1M2 dengan konfigurasi
M3 = (Q3
, Ʃ, Γ, δ3
, S3
, B, F3
)
dimana:
Q3 = Q1 U Q2 (diketahui Q1 ∩ Q2 = Ф)
S3 = S1 dan F3 = F2
Fungsi transisi dari M3 dibentuk sbb.:
- Semua transisi δ2
- Transisi-transisi δ1 yang tidak menuju F1
- Transisi-transisi δ1 yang menuju F1 diganti menuju S2
M1 = ({q1, q2, q3, q4}, {a}, {a, B}, {q1}, B,
{q4})
dengan fungsi transisi:
δ(q1, a) = (q2, a, R)
δ(q1, B) = (q2, B, R)
δ(q2, a) = (q3, a, R)
δ(q2, B) = (q3, B, L)
δ(q3, a) = (q4, a, R)
δ(q3, B) = (q4, B, R)
M2 = ({p1, p2}, {a}, {a, B}, {p1}, B, {p2})
dengan fungsi transisi:
δ(p1, a) = (p2, a, R)
δ(p1, B) = (p2, a, R)
akan dibentuk M3 yang merupakan
kombinasi dari M1 dan M2 atau
M3 = M1M2 dengan konfigurasi
M3 = ({q1, q2, q3, q4, p1, p2}, {a}, {a, B},
{q1}, B, {p2})
dengan fungsi transisi:
δ(q1, a) = (q2, a, R)
δ(q1, B) = (q2, B, R)
δ(q2, a) = (q3, a, R)
δ(q2, B) = (q3, B, L)
δ(q3, a) = (p1, a, R)
δ(q3, B) = (p1, B, R)
δ(p1, a) = (p2, a, R)
δ(p1, B) = (p2, a, R)
Referensi :
