Contoh Soal Mesin Turing Beserta Pembahasan Lengkap untuk Pemula

artikel contoh soal

Dunia teori komputasi tidak akan lengkap tanpa membahas Mesin Turing. Dianggap sebagai fondasi dari komputer modern yang kita gunakan saat ini, Mesin Turing adalah model matematika yang mendefinisikan mesin abstrak yang memanipulasi simbol pada sepotong pita sesuai dengan tabel aturan. Bagi mahasiswa informatika atau peminat ilmu komputer, memahami cara kerja Mesin Turing adalah langkah krusial untuk memahami batasan apa yang bisa dan tidak bisa dihitung oleh mesin.

Artikel ini akan mengupas tuntas konsep dasar, cara kerja, hingga kumpulan contoh soal Mesin Turing beserta pembahasannya yang disajikan secara sistematis.

Baca juga: 20+ Contoh Soal Ayat Jurnal Penutup Perusahaan Jasa dan Dagang: Lengkap dengan Pembahasan

Apa Itu Mesin Turing?

Ditemukan oleh Alan Turing pada tahun 1936, Mesin Turing (Turing Machine) bukan merupakan mesin fisik, melainkan model teoritis. Jika sebuah masalah dapat diselesaikan dengan algoritma, maka masalah tersebut dapat diselesaikan oleh Mesin Turing.

Komponen Utama Mesin Turing

Sebelum masuk ke contoh soal, Anda harus memahami elemen-elemen yang membentuk Mesin Turing:

🔖 Baca juga:
Analisis Perubahan Aturan Pajak THR dari Masa ke Masa Hingga Tahun 2026
  1. Pita (Tape): Berupa sel-sel tak terbatas yang berisi simbol dari alfabet tertentu.
  2. Head: Alat untuk membaca dan menulis simbol pada pita serta dapat bergerak ke kiri (L) atau ke kanan (R).
  3. State Register: Menyimpan status mesin saat ini.
  4. Tabel Transisi: Instruksi yang memberi tahu mesin apa yang harus dilakukan (tulis simbol, gerakkan head, atau pindah state) berdasarkan simbol yang dibaca.

Secara formal, Mesin Turing dinyatakan dalam 7-tupel: $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$.

  • $Q$: Himpunan state.
  • $\Sigma$: Alfabet input.
  • $\Gamma$: Alfabet pita (termasuk simbol blank).
  • $\delta$: Fungsi transisi.
  • $q_0$: State awal.
  • $B$: Simbol blank/kosong.
  • $F$: Himpunan state akhir/penerima.

Cara Kerja Mesin Turing

Mesin bekerja dengan membaca simbol di bawah head. Berdasarkan simbol tersebut dan state saat ini, mesin akan:

  1. Menulis simbol baru di sel tersebut (bisa simbol yang sama).
  2. Mengubah state.
  3. Menggerakkan head satu langkah ke kiri (Left) atau ke kanan (Right).

Proses ini berlanjut sampai mesin mencapai “Halt” atau masuk ke state akhir ($F$).

Contoh Soal 1: Pengenalan Bahasa $L = \{0^n 1^n | n \geq 1\}$

Ini adalah soal klasik. Kita diminta membuat Mesin Turing yang menerima string dengan jumlah angka 0 diikuti dengan jumlah angka 1 yang sama. Contoh: 01, 0011, 000111.

Strategi Penyelesaian

  1. Ganti angka 0 paling kiri dengan simbol X.
  2. Gerakkan head ke kanan mencari angka 1 pertama, lalu ganti dengan simbol Y.
  3. Kembali ke kiri mencari angka 0 berikutnya yang belum diganti (di sebelah kanan X terakhir).
  4. Ulangi proses sampai semua 0 dan 1 habis berpasangan.

Tabel Transisi

Misalkan:

  • State $q_0$: Mencari 0 untuk diganti X.
  • State $q_1$: Mencari 1 untuk diganti Y.
  • State $q_2$: Kembali ke kiri mencari X.
  • State $q_3$: Verifikasi apakah semua sudah menjadi Y.
  • State $q_4$: State akhir (Accept).

Pembahasan Langkah demi Langkah untuk Input “0011”

  1. (q0, 0) -> (q1, X, R): 0 pertama diganti X. Pita: X011. State jadi q1.
  2. (q1, 0) -> (q1, 0, R): Lewati 0.
  3. (q1, 1) -> (q2, Y, L): Ketemu 1 pertama, ganti Y. Pita: X0Y1. State jadi q2.
  4. (q2, 0) -> (q2, 0, L): Kembali ke kiri melewati 0.
  5. (q2, X) -> (q0, X, R): Ketemu X, geser kanan untuk cari 0 lagi.
  6. (q0, 0) -> (q1, X, R): 0 kedua diganti X. Pita: XXY1.
  7. (q1, Y) -> (q1, Y, R): Lewati Y.
  8. (q1, 1) -> (q2, Y, L): 1 kedua diganti Y. Pita: XXYY.
  9. (q2, Y) -> (q2, Y, L): Kembali ke kiri.
  10. (q2, X) -> (q0, X, R): Ketemu X, geser kanan.
  11. (q0, Y) -> (q3, Y, R): Tidak ada 0 lagi, hanya ada Y. Cek sisa pita.
  12. (q3, Y) -> (q3, Y, R): Lewati semua Y.
  13. (q3, B) -> (q4, B, R): Ketemu Blank. String diterima!

Contoh Soal 2: Penjumlahan Unary (1 + 2)

Dalam sistem unary, angka $n$ direpresentasikan dengan simbol ‘1’ sebanyak $n$ kali. Jadi, 1 + 2 ditulis sebagai 1 + 11. Kita ingin hasilnya menjadi 111.

Strategi Penyelesaian

Cukup dengan menghapus tanda tambah (+) dan menggantinya dengan angka 1, lalu menghapus satu angka 1 di bagian paling akhir untuk menjaga jumlah tetap benar.

Detail Transisi

  1. State $q_0$: Bergerak ke kanan mencari simbol +.
  2. (q0, 1) -> (q0, 1, R): Lewati angka 1.
  3. (q0, +) -> (q1, 1, R): Ubah + menjadi 1, pindah ke $q_1$.
  4. State $q_1$: Bergerak ke kanan sampai menemukan ujung string (Blank).
  5. (q1, 1) -> (q1, 1, R): Lewati angka 1.
  6. (q1, B) -> (q2, B, L): Ketemu Blank, geser kiri sekali.
  7. State $q_2$: Hapus satu angka 1 terakhir.
  8. (q2, 1) -> (q3, B, L): Ubah 1 terakhir jadi Blank. Selesai (Halt).

Contoh Soal 3: Fungsi Komplemen (Inverter)

Buatlah Mesin Turing yang mengubah semua angka 0 menjadi 1 dan angka 1 menjadi 0 pada pita biner. Contoh input: 1011, hasil: 0100.

Pembahasan

Ini adalah soal yang sangat sederhana untuk pemula guna memahami mutasi simbol.

  • State $q_0$: State utama pemrosesan.
  • Transisi:
    • Jika baca 0: Tulis 1, gerak Kanan.
    • Jika baca 1: Tulis 0, gerak Kanan.
    • Jika baca Blank (B): Berhenti (Halt).

Tabel Transisi:

$\delta(q_0, 0) = (q_0, 1, R)$

$\delta(q_0, 1) = (q_0, 0, R)$

$\delta(q_0, B) = (q_{halt}, B, L)$

Contoh Soal 4: Menyalin String (Copying String)

Diberikan input w (misal: 110), buatlah Mesin Turing yang menghasilkan w#w (110#110).

Pembahasan Strategi

  1. Tandai simbol pertama (0 atau 1) dengan menggantinya menjadi simbol sementara (misal: 0 jadi X, 1 jadi Y).
  2. Gerak ke kanan melewati tanda pembatas # sampai menemukan sel kosong pertama.
  3. Tuliskan simbol yang sama dengan yang ditandai tadi.
  4. Kembali ke kiri mencari simbol asli berikutnya.
  5. Setelah semua selesai, ubah kembali X dan Y menjadi 0 dan 1.

Tips Mengerjakan Soal Mesin Turing bagi Pemula

Agar mahir mengerjakan soal-soal ujian atau tugas Mesin Turing, perhatikan beberapa tips berikut:

  1. Visualisasikan Pita: Selalu gambar kondisi pita di setiap langkah transisi. Ini membantu Anda melihat apakah head tertinggal atau salah posisi.
  2. Gunakan Simbol Penanda: Jangan ragu menggunakan alfabet tambahan seperti X, Y, atau Z untuk menandai sel yang sudah diproses agar tidak dibaca dua kali.
  3. Definisikan State dengan Jelas: Beri nama state berdasarkan fungsinya, misalnya $q_{cari\_ujung}$ atau $q_{kembali}$.
  4. Uji Kasus Ekstrim: Tes mesin Anda dengan input kosong atau input minimal (seperti satu karakter saja) untuk memastikan tidak ada infinite loop.

Mengapa Belajar Mesin Turing Itu Penting?

Mesin Turing bukan sekadar sejarah. Memahami model ini memberikan kita wawasan tentang:

  • Limitasi Komputasi: Ada masalah yang “Undecidable” atau tidak bisa diselesaikan oleh komputer mana pun (seperti Halting Problem).
  • Kompleksitas Algoritma: Membantu memahami perbedaan kelas masalah P dan NP.
  • Arsitektur Komputer: Arsitektur Von Neumann yang kita gunakan saat ini secara fundamental mengikuti prinsip Mesin Turing.

Baca juga: Mahasiswa Universitas Teknokrat Indonesia Laksanakan Kunjungan Proyek Untuk Mata Kuliah K3 di Pembangunan New WTP Krenceng Tahap 2, Cilegon

Kesimpulan

Mesin Turing mungkin terlihat mengintimidasi pada awalnya karena sifatnya yang sangat teknis dan teoritis. Namun, dengan banyak berlatih menggunakan contoh soal seperti di atas, Anda akan mulai melihat pola logis di balik setiap pergerakan head dan transisi state.

Kunci utama dalam menguasai Mesin Turing adalah ketelitian dalam menyusun fungsi transisi. Setiap pergerakan kecil dari head (L atau R) sangat menentukan apakah sebuah string akan diterima atau ditolak.

Semoga pembahasan contoh soal Mesin Turing ini membantu Anda dalam memahami mata kuliah Teori Bahasa dan Automata atau sekadar memuaskan rasa ingin tahu Anda tentang bagaimana cara kerja “otak” komputer yang sebenarnya.

Apakah Anda ingin saya membuatkan tabel transisi yang lebih d

Penulis: Aripin

Tag

Related Posts

Post Comment

You May Have Missed