Mesin Turing

Mesin Turing adalah mesin abstrak yang diciptakan Alan Turing pada tahun 1936. Mesin ini tidak dimaksudkan untuk dibangun sebagai mesin yang dapat dipakai manusia, melainkan hanya sebagai model abstrak untuk mengetahui kemampuan mesin untuk melakukan proses yang disebut sebagai komputasi.

Hari ini kita menggunakan komputer untuk berbagai hal. Salah satu hal yang penting dilakukan komputer adalah menjawab pertanyaan-pertanyaan kita. Seorang pengemudi Gojek akan menanyakan pada komputer arah untuk menuju ke rumah kita. Kamu bertanya kepada browser mengenai film Marvel terbaru yang akan segera tayang. Seorang bapak yang berjualan TV di Mangga Dua bertanya kepada kalkulatornya harga TV Samsung setelah diskon.

Komputer menjawab pertanyaan kita berdasarkan informasi yang ia ketahui sebelumnya yang diolah dengan aturan tertentu. Aturan yang digunakan bisa berbeda-beda untuk kasus yang berbeda.

Tentunya Alan Turing pada waktu itu belum berpikir untuk memesan GoFood ketika bekerja di Bletchley Park. Pertanyaan-pertanyaan yang dapat diajukan kepada mesin yang ada dalam pikiran Alan Turing kira-kira seperti ini:

• Apakah \sqrt{2} bilangan rasional?
• Apakah hipotesis kekontinuan benar?
• Apakah semua bilangan genap dapat dinyatakan sebagai jumlah dua bilangan prima?

Komputasi

Seluruh proses mengolah informasi ini disebut sebagai komputasi. Komputasi inilah yang dimodelkan secara abstrak menggunakan mesin Turing. Jadi mesin Turing bukan dipakai untuk alasan praktis melainkan filosofis. Dengan mesin Turing kita dapat melihat potensi dan batas kemampuan komputer dalam melakukan komputasi. Mesin atau konsep apapun yang dapat kita buat, jika dapat dibuktikan ekivalen dengan mesin Turing, akan dapat ditentukan potensi dan batas kemampuannya.

Komponen-komponen mesin Turing

Pita yang panjangnya tak berhingga

Bagian utama mesin Turing adalah pita yang memiliki sel-sel yang dapat ditulisi dengan simbol-simbol. Untuk penyederhanaan, sering simbol yang diizinkan untuk ditulis pada pita ini dibatasi hanya 0 dan 1. Sel yang belum ditulisi berada dalam keadaan kosong. Sel yang sudah ditulisi dapat dihapus kembali. Pita ini panjangnya tidak dibatasi, diasumsikan memiliki panjang tak berhingga.

Head - Kepala baca/tulis

Untuk melakukan baca tulis pada pita ini, terdapat sebuah head yang dapat digerakkan maju mundur sepanjang pita tersebut. Sel yang dikunjungi head tersebut dapat ditulisi 0 atau 1, atau dihapus isinya.

Status

Kemudian terdapat yang disebut status. Dalam contoh di atas, mesin tersebut memiliki empat macam status yang mungkin, yaitu MULAI, JALAN, BERHENTI, dan ERROR. Status yang sedang berlaku ditunjukkan di bawah pitanya. Tergantung dari mesin Turing seperti apa yang diinginkan, banyaknya status dapat berbeda-beda.

Program dalam mesin Turing

Mesin Turing bekerja dengan program. Program adalah rangkaian instruksi yang kita berikan untuk dijalankan oleh mesin Turing. Sebuah baris program merupakan instruksi yang sangat sederhana. Walaupun sederhana, dengan mengkombinasikan sejumlah instruksi yang berbeda-beda kita dapat memerintahkan mesin untuk melakukan hal yang sangat kompleks.

Kondisi

Instruksi yang diberikan bergantung pada status mesin dan simbol yang dibaca pada pita. Jadi setiap instruksi selalu berbentuk:

Jika status adalah ... dan simbol terbaca adalah ..., lakukan ...

Misalnya, kita ingin mesin melakukan sesuatu ketika statusnya adalah JALAN dan simbol yang dibaca head adalah 0, maka kita mengatakan:

Jika status adalah JALAN dan simbol terbaca adalah 0, lakukan ...

Apa yang bisa dilakukan?

Dalam setiap kondisi, mesin Turing dapat diinstruksikan untuk melakukan sesuatu. Instruksi tersebut selalu merupakan rangkaian tiga hal berikut:

1. Tulis 0 atau tulis 1 atau hapus sel.
2. Maju atau mundur atau tetap di tempat.
3. Ganti status ke status tertentu.

Berikutnya: Contoh-contoh mesin Turing