Pertemuan 14

Pretest

• Apa perbedaan memori TM dibanding PDA?
• Apa itu pita (tape) pada Mesin Turing?
• Mesin Moore menghasilkan output berdasarkan apa?

Modul (Ringkasan Materi)

Mesin Turing (TM) adalah model komputasi paling kuat yang menjadi dasar teori komputabilitas. TM memiliki pita (tape) sebagai memori tak terbatas (secara konsep), kepala baca/tulis, dan aturan transisi.

• TM membaca simbol di tape, bisa menulis simbol baru, lalu bergerak kiri/kanan.
• TM dapat mengenali bahasa yang lebih kompleks daripada FA dan PDA.
• TM digunakan untuk membahas konsep: decidable, undecidable, dan batas komputasi.

Mesin Moore adalah jenis finite state machine yang menghasilkan output berdasarkan state saat ini (berbeda dengan Mealy yang output-nya bergantung state dan input).

• Output Moore: ditentukan oleh state, jadi lebih stabil (output berubah saat state berubah).
• Digunakan pada sistem kontrol, rangkaian digital, dan desain automasi sederhana.

Posttest

• Jelaskan 3 komponen penting Mesin Turing.
• Apa bedanya Moore vs Mealy (output)?
• Kenapa TM disebut model komputasi paling umum?

Tugas

• Buat contoh sederhana Mesin Moore (3 state) untuk output “ON/OFF” berdasarkan state.
• (Opsional) Jelaskan langkah TM untuk mengubah semua 0 menjadi 1 pada tape.

Referensi

• Rachmatika, Rinna, S.Kom., M.Kom. Modul Teori Bahasa dan Automata. Universitas Pamulang.