Mesin Turing

Mesin Turing

Sejarah Mesin Turing

Mesin turing diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer. Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer (general-purpose) Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function). Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa- pembatasan (non-restricted language),yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).

Alan Mathison Turing (23 Juni 1912 - 7 Juni 1954), adalah seorang peneliti matematika dan komputer, dan pahlawan perang Inggris. Dia adalah dari peneliti-peneliti komputer modern digital pertama. Selain itu dia adalah orang pertama yang berpikir menggunakan komputer untuk berbagai keperluan. Dia mengatakan bahwa komputer dapat menjalankan berbagai program. Dia juga memberikan ide tentang mesin Turing, mesin yang dapat menjalankan sekumpulan perintah. Turing juga yang mencetuskan tes Turing. Namanya diabadikan dalam nama Penghargaan Turing.




Model Mesin Turing

Sebuah mesin Turing terdiri dari komponen-komponen:

1. Pengendali berhingga (finite control)
2. Pita masukan dengan sifat:

• Panjangnya tidak berhingga (ujung kiri terbatas, ujung kanan tidak terbatas)
• Dapat dibaca maupun ditulis
• Sel yang tidak berisi simbol masukan akan berisi simbol kosong (blank = B)

Perbedaan mesin turing dengan FSA dan PDA

Aksi Mesin Turing

Perilaku mesin turing bergantung pada simbol masukan yang berada pada posisi head baca/tulis dan status dari Finite Control. Dalam setiap gerakannya, mesin turing dapat melakukan salah satu dari aksi berikut:

1. Berubah status
2. Menuliskan simbol pada pita masukan. Aksi penulisan ini mengubah simbol yang sebelumnya berada pada sel tersebut
3. Menggerakan head ke kiri atau ke kanan

Daftar Pustaka

Munir, Rinaldi. 2014. Mesin Turing (Bagian 1), diakses dari https://informatika.stei.itb.ac.id/~rinaldi.munir/TeoriKomputasi/2014-2015/IF5110%20-%20Mesin%20Turing%20(Bagian%201).pdf, pada 5 Maret 2020.