Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."
Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu M = (Q, Σ, Γ, δ, S, F, b)
dimana :Q = himpunan state
Σ = himpunan simbol input
Γ = simbol pada pita (meliputi pula blank)
δ = fungsi transisi
S = state awal, S ∈ Q
F = himpunan state akhir, F⊆ Q
b = simbol kosong (blank) bukan bagian dari Σ, b .Σ
Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)
STUDI KASUS
A. Buatlah transisi masing-masing state seperti pada gambar berikut
B. Pseudocode Mesin Turing
Deklarasi:
Integer q0=0, q1=1, q2=2, q3=3, q4=4, q5=5, q6=6;
Boolean state_akhir = {false,false,false,false,false,false,true}
Integer state, i;
String Uji;
Char c;
Deskripsi:
Input (uji)
state = 0
i = 0;
if i < uji.length then
for i=0;i<uji.length;i++
c = uji.charAt(i)
case q0; switch(c)
case c = ‘a’ return q1
‘a’ = ‘x’
case c = ‘y’ return q4
case c=’ ’ return q6
case q1; switch(c)
case c = ‘a’ return q1
case c = ‘y’ return q1
case c = ‘b’ return q2
‘b’ = ‘y’
case q2; switch(c)
case c = ‘b’ return q2
case c = ‘z’ return q 2
case c = ‘c’ return q3
‘c’ = ‘z’
for i=0;i<uji.length;i--
c = uji.charAt(i)
case q3; switch(c)
case c = ‘a’ return q3
case c = ‘b; return q3
case c = ‘z’ return q3
case c = ‘y’ return q3
case q4; switch(c)
case c = ‘x’ return q4
case c = ‘ ‘ return q5
for i=0;i<uji.length;i++
c = uji.charAt(i)
case q5; switch(c)
case c = ‘x’ return q5
case c = ‘y’ return q5
case c = ‘z’ return q5
case c = ‘ ’ return q6
default (state_akhir = q0);
else
state_akhir{state}
output (state_akhir{state})
C. Flowchart Mesin Turing
D. Langkah Kerja
1. Buka program aplikasi JFLAP.
2. Klik tabPushdown Automaton pada kotak dialog menu
3. Buatlah 6 buah state dengan transisi dan input masing-masing state seperti dibawah ini :
4. Klik menu input lalu pilih Step by BuildingBlock, kemudian masukan “aabbcc” kemudian klik OK dan enter
5. Klik Step untuk melakukan simulasi transisi langkah-demi langkah.
6. Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut
KESIMPULAN
1. Pada mesin turing memori berupa pita yang dasarnya berupa array
2. Pada mesin turing terdapat sebuah head yang menunjukan posisi yang diakses pada pita
ConversionConversion EmoticonEmoticon