Aplikasi Simulator Mesin Turing Pita Tunggal

Aplikasi Simulator Mesin Turing Pita Tunggal Nuludin Saepudin / NIM 23515063 Program Magister Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia [email protected]

Abstract—Mesin Turing adalah model komputasi teoritis yang dikemukakan oleh alan turing, secara ensensial, mesin turing adalah sebuah finite automaton yang memiliki sebuah tape dengan panjang tak terhingga yang dapat membaca dan menulis data, Mesin Turing mempunyai prilaku atau aturan-aturan cara berjalannya sembuah mesin ini. Penggambaran cara bekerja Mesin Turing dapat dibuat sebuah aplikasi simulator. Index Terms—mesin, turing, aplikasi simulasi, komputasi.

I. MESIN TURING Mesin Turing adalah model komputasi teoritis yang dikemukakan oleh alan turing, secara ensensial, mesin turing adalah sebuah finite automaton yang memiliki sebuah pita dengan panjang tak terhingga yang dapat membaca dan menulis data. Mesin Turing menggunakan notasi seperti instantaneous descriptions (ID) pada Push Down Automata (PDA) untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses. Elemen yang dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori akan berupa suatu pita yang pada dasarnya merupakan sebuah array dari sel-sel penyimpanan.

A. Notasi Pada Mesin Turing Visualisasi dari sebuah mesin turing pada gambar 1 dibawah ini.

Gambar 1: Visualisasi Mesin Turing[1] Mesin terdiri dari finite control yang dapat berada dalam sebuah himpunan berhingga state. Terdapat sebuah pita yang dibagi ke dalam kotak-kotak atau selsel. Setiap sel dapat menampung sebuah dari sejumlah

berhingga dari simbol. Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada pita. Selsel pita yang lain, perluasan secara infinite ke kiri dan kanan. Pada awalnya menampung simbol khusus yang dinamakan blank. Blank bukan sebuah input simbol dan mungkin terdapat simbol pita yang lain disamping input simbol dan blank. Terdapat sebuah pita head yang selalu ditempatkan pada satu dari sel-sel pita. Mesin turing dikatakan membaca sel tersebut. Pada awalnya head berada pada sel paling kiri yang menampung input. Sebuah pergerakan mesin turing adalah fungsi state dari finite control dan pita simbol yang dibaca. Operasi-operasi mesin turing dalam satu pergerakan: o Merubah state. Next state dapat sama dengan current state o Menulis sebuah simbol pada pita dalam sel yang dibaca. Simbol pada pita ini mengganti simbol apapun yang ada dalam sel tersebut. Secara opsional, simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam pita. o Memindahkan head ke kiri dan kanan Notasi formal pada mesin turing sama dengan finite automata atau PDA. Terdiri dari 7 tuple M = (Q, Ʃ, , , q0, B, F) Komponen-komponennya adalah: Q: Himpunan berhingga dari state dari finite control. Ʃ: Himpunan berhingga dari simbol-simbol input. : Himpunan dari simbol pada pita. Ʃ merupakan subset dari . : Fungsi transisi. Argumen (q, X) adalah sebuah state q dan sebuah simbol pada pita X. Nilai dari (q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana: o p adalah next state dalam Q o Y adalah simbol, dalam , ditulis dalam sel yang sedang dibaca, menggantikan simbol apapun yang ada dalam sel tersebut. o D adalah arah, berupa L atau R, berturut-turut menyatakan kiri atau kanan, dan menyatakan arah dimana head bergerak. q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.

Makalah IF5110 Teori Komputasi – Sem. I Tahun 2015/2016

B:

simbol blank. Simbol ini ada dalam tapi tidak dalam Ʃ, yaitu B bukan sebuah simbol input. Himpunan dari final state, subset dari Q.

F:

B. Diagram Transisi untuk Mesin Turing Diagram transisi terdiri dari sebuah himpunan dari node–node yang menyatakan state–state dari Mesin Turing. sebuah arc dari state q ke state p diberi label oleh satu atau lebih item dengan bentuk X/Y D, dimana X dan Y adalah simbol pada pita, dan D adalah arah, kiri (L) atau kanan (R). Bahwa bila (q, X) = (p, Y, D) diperoleh label X/Y D pada arc dari q ke p. Dalam diagram arah D dinyatakan dengan tanda ← untuk “left” dan → untuk “right”. Start state ditandai dengan kata “start” dan sebuah panah yang masuk ke dalam state tersebut. Final state ditandai dengan putaran ganda. Contoh: ada bahasa L dengan string bit ‘0’ dan ‘1’ yang sama banyaknya, contoh string di dalam L misalnya “01”, “10”, “011001”, “100110”, dst. Bahasa tersebut dapat dikenali oleh mesin turing, proses yang dilakukan akan dijelaskan pada bagian berikut[2]. M = ({q0, q1, … , q4}, {0, 1, B}, {0, 1, X, Y, B}, , q0, B,q4) Aturan fungsi transisi 0 (q1, X, R) (q1, 0, R) (q3, Y, L) (q3, 0, L) -

Q q0 q1 q2 q3 q4

tertera pada tabel 1 dibawah ini

1 (q2, X, R) (q3, Y, L) (q2, 1, R) (q3, 1, L) -

X (q0, X, R) -

Y (q0, Y, R) (q1, Y, R) (q2, Y, R) (q3, Y, L) -

B (q4, B, R) -

Tabel 1: fungsi transisi Dari fungsi transisi diatas dapat digambarkan diagram transisi dari mesin turing M:

B/B R

0/X R

q0

Gambar 3: Rancangan Simulator Rancangan aplikasi simulator mempunyai komponenkomponen yang dibutuhkan untuk mensimulasikan sebuah mesin turing, yaitu sebagai berikut: 1. Tape adalah pita yang berisikan sel-sel suatu simbol. 2. Posisi Head adalah posisi sel pita yang ditunjuk oleh head. 3. Rules adalah fungsi transisi dari mesin turing yang terdiri atas state atau status prilaku yang akan dibuat seperti proses read, write, direction dan new state. State Read Write Direction New State (q0..qx) Simbol Simbol (R, L) (q0…qx) …. ….. …. ….. …… Tabel 2: fungsi transisi pada simulator 4.

Y/Y R 0/0 R

Y/Y R

q4

kelakuan sistem fisik atau sistem yang abstrak tertentu Simulasi dari sebuah mesin turing atau disebut simulator mesin turing adalah proses peniruan cara kerja dan fungsi yang ada pada mesin turing seperti komponen pita, posisi head, fungsi transisi, setingan input dan state awal fungsi transisi. Pembuatan aplikasi simulator mempunyai tiga garis besar tape yang birisikan sel-sel pita dan head, fungsi transisi dan pengaturan mesin seperti pada gambar 3.

1/X R

Pengaturan adalah setingan yang terdapat pada mesin turing seperti inputan simbol, state awal dan run control.

q1

1/Y L X/X R

q2

0/Y L

q3

1/1 R Y/Y R

Gambar 4: Pengaturan Mesin Turing 0/0 L 1/1 L Y/Y L

Gambar 2: Diagram Transisi dari Mesin Turing M

II. RANCANGAN APLIKASI SIMULATOR Simulasi adalah suatu proses peniruan dari sesuatu yang nyata beserta keadaan sekelilingnya (state of affairs). Aksi melakukan simulasi ini secara umum menggambarkan sifat-sifat karakteristik kunci dari

Cara kerja dari simulator ini cukup mudah dimulai state pertama yang telah ditentukan pada pengaturan mesin kemudian membaca setiap rules/fungsi transisi yang telah dibuat lalu melakukan sebuah aksi dari rules tersebut seperti mengerakan posisi head ke kiri atau ke kanan, menulis dan membaca pita sampai pada state akhir atau mesin turing berhenti sebagai contoh mengisikan fungsi transisi sebagai berikut State = q0, Read = 0, Write = X, Direction = R, New State = q1

Makalah IF5110 Teori Komputasi – Sem. I Tahun 2015/2016

maka fungsi transisi state q0 bila membaca “0” pada pita yang sedang ditunjuk oleh head maka sel pita tersebut akan diisikan oleh X, lalu bergerak posisi head ke arah kanan (right) setelah itu pindah ke rules state q1.

III. Implementasi dan testing simulator Pembuatan aplikasi simulator ini menggunakan tagtag html sebagai standar web sedangan untuk mempercantik halaman menggunakan css bootstrap. Dalam melakukan transisi dan proses simulasi mesin turing menggunakan sebuah bahasa javascript. Interface simulator sesuai dengan rancangan aplikasi pada poin sebelumnya yang mempunyai komponen tape, rules dan setting ditunjukan pada Gambar 5.

Gambar 5: Interface Simulator Untuk menguji aplikasi simulator bisa mensimulasikan sebuah mesin turing maka dibutuhkan sebuah prilaku mesin turing misalnya ada bahasa L dengan string bit ‘0’ dan ‘1’ yang sama banyaknya, contoh string di dalam L misalnya “01”, “10”, “011001”, “100110”, dst. Bahasa tersebut dapat dikenali oleh mesin turing. Cara kerja mesin turing untuk mengenali bahasa L dinyatakan dengan algoritma berikut. 1. Jika simbol paling kiri adalah ‘0’ maka ke langkah 2 dan bila ‘1’ maka ke langkah 8. 2. Ganti simbol ‘0’ paling kiri dengan simbol ‘X’. 3. Gerakkan head ke kanan hingga dijumpai simbol ‘1’. 4. Ganti simbol ‘1’ paling kiri dengan simbol ‘Y’ 5. Gerakkan head ke kiri hingga dijumpai simbol ‘X’ 6. Geser head ke kanan (akan diperoleh ‘0’ paling kiri). 7. Kembali ke langkah 2 8. Ganti simbol ‘1’ paling kiri dengan simbol ‘X’. 9. Gerakkan head ke kanan hingga dijumpai simbol ‘0’. 10. Ganti simbol ‘0’ paling kiri dengan simbol ‘Y’ 11. Geser head ke kanan (akan diperoleh ‘1’ paling kiri). 12. Kembali ke langkah 8. Ada beberapa aturan dari langkah-langkah diatas 1. Untuk simbol paling kiri adalah ‘0’ sebelum langkah algoritma dilakukan a. Jika pada saat bergerak ke kanan untuk mencari ‘1’, mesin turing M menjumpai simbol B, maka berarti banyaknya ‘0’ lebih dari banyaknya ‘1’.

Kesimpulannya, string masukkan tidak dikenali. Jika pada saat bergerak ke kiri M tidak menjumpai lagi ‘0’, maka M memeriksa apakah masih ada ‘1’, bila habis maka string diterima (dikenali) 2. Untuk simbol paling kiri adalah ‘1’ sebelum langkah algoritma dilakukan a. Jika pada saat bergerak ke kanan untuk mencari ‘0’, mesin turing M menjumpai simbol B, maka berarti banyaknya ‘1’ lebih dari banyaknya ‘0’. Kesimpulannya, string masukkan tidak dikenali. b. Jika pada saat bergerak ke kiri M tidak menjumpai lagi ‘1’, maka M memeriksa apakah masih ada ‘0’, bila habis maka string diterima (dikenali) c. Jika sebuah string diterima (dikenali), maka mesin turing M berhenti. Untuk string yang tidak dikenali (ditolak) ada kemungkinan M tidak berhenti (looping) Dari cara kerja mesin turing untuk mengenali bahasa L maka fungsi transisi yang dimasukan kedalam aplikasi simulator yaitu sebagai berikut State Read Write Direction New State q0 0 X R q1 q0 1 X R q2 q0 Y Y R q0 q0 blank blank R q4 q1 0 0 R q1 q1 1 Y L q3 q1 Y Y R q1 q2 0 Y L q3 q2 1 1 R q2 q2 Y Y R q2 q3 0 0 L q3 q3 1 1 L q3 q3 Y Y L q3 q3 X X R q0 Tabel 3: fungsi transisi bahasa L Pengaturan mesin pada aplikasi simulator diset state awal pada q0 dan q4 sebagai state akhir (final state) selanjutnya untuk menguji mesin turing pada simulator ini dengan memberikan inputan string “101100” maka saat aplikasi simulator dijalakan pada fungsi transisi state awal akan berwarna biru seperti pada Gambar 6. b.

Gambar 6: Fungsi transisi state awal bahasa L State awal (q0, 1, X, R, q2) membaca string “1” pada sel pita pertama maka proses yang dilakukan adalah menggantikan sting “1” menjadi “x”, posisi head pada pita akan bergerak ke arah kanan dan melanjutkan ke state berikutnya yaitu q2.

Makalah IF5110 Teori Komputasi – Sem. I Tahun 2015/2016

Gambar 7: Hasil Langkah Pertama

Langkah berikutnya ditunjukan sebagai berikut: Langkah kedua (q2, 0, Y, L, q3)

Langkah kelimabelas (q0, Y, Y, R, q0)

Langkah keenambelas (q0, Y, Y, R, q0) Langkah ketiga (q3, X, X, R, q0) Langkah ketujuhbelas (q3, blank, blank, R, q4) Langkah ke empat (q0, Y, Y, R, q0)

Langkah kelima (q0, 1, X, R, q2)

Langkah keenam (q2, 1, 1, R, q2)

Langkah ketujuh (q2, 0, Y, L, q3)

Langkah kedelapan (q3, 1, 1, L, q3)

Hasil simulasi dengan prilaku atau transisi pada tabel 3 maka bahasa L dengan inputan string “101100” dinyatakan diterima dan sesuai dengan prilaku string bit ‘0’ dan ‘1’ yang sama banyaknya. Apabila inputan string nya diubah dengan string “0011110” maka pada pita seperti dibawah ini.

Berikut ini hasil dari simulator yang dijalakan dengan fungsi transisi di tabel 3. Langkah pertama (q0, 0, X, R, q1)

Langkah kesembilan (q3, X, X, R, q0) Langkah kedua (q1, 0, 0, R, q1) Langkah kesepuluh (q0, 1, X, R, q2) Langkah ketiga (q1, 1, Y, L, q3) Langkah kesebelas (q2, Y, Y, R, q2) Langkah keempat (q3, 0, 0, L, q3)

Langkah keduabelas (q2, 0, Y, L, q3) Langkah kelima (q3, X, X, R, q0)

Langkah ketigabelas (q3, Y, Y, L, q3) Langkah keenam (q0, 0, X, R, q1)

Langkah keempatbelas (q3, X, X, R, q0)

Langkah ketujuh (q1, Y, Y, R, q1)

Langkah kedelapan (q1, 1, Y, L, q3) Makalah IF5110 Teori Komputasi – Sem. I Tahun 2015/2016

IV KESIMPULAN

Langkah kesepuluh (q3, X, X, R, q0)

Berdasarkan pada perancangan dan hasil uji coba prilaku bahasa L dengan transisi yang telah ditetapkan dapat ditarik kesimpulan bahwa aplikasi simulator pada mesin turing berpita tunggal dapat digunakan dengan baik sesuai harapan mensimulasikan sifat dan prilaku dari sebuah mesin turing.

Langkah kesebelas (q0, Y, Y, R, q0)

REFERENCES

Langkah kesembilan (q3, Y, Y, L, q3)

[1]

Langkah keduabelas (q0, 1, X, R, q2)

[2]

Hopcroft John E, Motwani Rajeev, Ullman Jeffrey D, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-wesley, 2001, pp. 317–325. Munir Rinaldi, Diktat Kuliah IF5110 – Mesin Turing (Bagian 1). Program Studi Teknik Informatika, Sekolah Tinggi Elektro dan Informatika, ITB, 2015.

Langkah ketigabelas (q2, 1, 1, R, q2)

PERNYATAAN Langkah keempatbelas (q2, 0, Y, L, q3)

Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 21 Desember 2015

Langkah kelimabelas (q3, 1, 1, L, q3)

Langkah keenambelas (q3, X, X, R, q0)

X Langkah ketujuhbelas (q0, 1, X, R, q2)

Langkah kedelapanbelas (q2, Y, Y, R, q2)

Langkah kesembilanbelas loop

Dari notifikasi tersebut bahwa bahasa L dengan diberi inputan string “0011110” tidak diterima atau tidak dikenali.

Makalah IF5110 Teori Komputasi – Sem. I Tahun 2015/2016

Nuludin Saepudin NIM 23515063