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.

a1c-pemikiran-godel-turing-media-image45-png

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.

Komponen utama mesin turing adalah pita yang panjangnya tak berhingga, yang dibagi dalam sel-sel. Masing-masing sel dapat ditulisi 0 atau 1. Silakan coba klik salah satu sel untuk mencoba menulisinya. Untuk menghapus isi sel, gunakan space bar. Untuk memindahkan head-nya, gunakan atau .

Untuk mengganti status, klik pada statusnya, kemudian pilih status lainnya.

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.

Mesin pencari 1 terakhir - Mesin ini akan menelusuri dari kiri ke kanan untuk mencari angka 1 terakhir dalam rangkaian angka 1. Untuk mencarinya, letakkan head pada salah satu angka 1, set status menjadi MULAI, kemudian tekan tombol . Kondisi yang tidak sesuai akan menghasilkan status ERROR.

Berikutnya: Contoh-contoh mesin Turing

Ditulis oleh
Pak Ari
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
sejarah pemikiran tokoh