Mesin Turing dijelaskan

Pada tahun 1936, sebelum komputer elektronik ada, matematikawan berusia 24 tahun Alan Turing bertanya apa artinya sebuah perhitungan bersifat mekanis. Jawabannya adalah sebuah mesin khayalan yang begitu sederhana sehingga hampir tidak mungkin melakukan lebih sedikit lagi: ia membaca dan menulis simbol pada pita, satu sel setiap kali, menurut tabel aturan yang tetap. Mesin itu ternyata mendefinisikan komputasi itu sendiri, dan menunjukkan bahwa ada pertanyaan yang sama sekali tidak akan pernah dapat dijawab oleh komputer mana pun.

Pita berisi sel-sel dengan angka 1 dan sel kosong, dengan kepala baca-tulis di atas satu sel yang diberi label keadaannya
Pita berisi sel-sel dengan angka 1 dan sel kosong, dengan kepala baca-tulis di atas satu sel yang diberi label keadaannya

Pertanyaan Turing

Pada tahun 1928 David Hilbert bertanya apakah ada prosedur mekanis yang memutuskan, untuk setiap pernyataan matematika, apakah pernyataan itu dapat dibuktikan: Entscheidungsproblem. Untuk menjawabnya, seseorang harus menyatakan dengan tepat apa itu prosedur mekanis. Dalam makalahnya tahun 1936, On Computable Numbers, Turing membayangkan seorang juru tulis yang bekerja dengan pensil dan kertas, lalu memangkas pekerjaan itu hingga langkah-langkah terkecilnya: lihat satu simbol, ubah simbol itu, pindah ke simbol di sebelahnya, dan ingat sedikit tentang apa yang sedang dikerjakan. Hasilnya adalah mesin Turing.

Mesin Bombe (kiri) dan potret Alan Turing (kanan)
Mesin Bombe (kiri) dan potret Alan Turing (kanan)

Mesinnya

Mesin Turing memiliki pita yang terbagi menjadi sel-sel, tanpa ujung ke dua arah, masing-masing berisi satu simbol, biasanya kosong. Sebuah kepala berada di satu sel dan mesin berada dalam salah satu dari sejumlah hingga keadaan. Tabel aturan memberikan, untuk setiap keadaan dan setiap simbol yang dapat dibaca kepala, simbol yang ditulis, arah gerakan, dan keadaan berikutnya. Mesin menerapkan satu aturan per langkah. Ketika memasuki keadaan berhenti, mesin berhenti, dan apa pun yang tersisa di pita adalah jawabannya.

Program sebagai tabel aturan

Setiap tabel aturan adalah sebuah program. Untuk menambahkan 1 ke bilangan biner, mesin berjalan ke ujung kanan bilangan, lalu bergerak ke kiri sambil mengubah 1 menjadi 0 sampai menemukan 0 atau sel kosong, yang diubahnya menjadi 1. Untuk memeriksa apakah sebuah kata merupakan palindrom, mesin menghapus simbol pertama, mengingatnya dalam keadaannya, berlari ke ujung yang lain dan memeriksa bahwa simbol terakhir cocok, lalu mengulanginya. Program panjang, seperti program yang mengalikan atau mengurutkan, dibangun dari beberapa jenis aturan yang sama.

Mesin universal

Gagasan terpenting Turing adalah bahwa tabel aturan itu sendiri dapat ditulis di pita. Mesin Turing universal membaca deskripsi mesin lain mana pun beserta inputnya, lalu menirunya langkah demi langkah. Dengan demikian satu mesin tetap dapat menjalankan setiap program: inilah prinsip di balik setiap komputer program tersimpan, tempat perangkat lunak hanyalah data di memori. Setiap sistem yang dapat meniru mesin Turing universal disebut Turing-lengkap, termasuk setiap bahasa pemrograman, Permainan Kehidupan Conway, dan automaton seluler Aturan 110.

Tesis Church–Turing

Pada tahun yang sama, Alonzo Church menggambarkan komputasi dengan kalkulus lambda miliknya, dan kedua definisi itu ternyata menghitung fungsi-fungsi yang persis sama. Begitu pula setiap model sesudahnya, dari mesin register hingga prosesor modern. Tesis Church–Turing menyatakan bahwa apa pun yang dapat dihitung dengan prosedur langkah demi langkah dapat dihitung oleh mesin Turing. Tesis ini tidak dapat dibuktikan, karena “prosedur langkah demi langkah” adalah gagasan informal, tetapi belum pernah ada contoh tandingan yang ditemukan.

Masalah perhentian

Turing kemudian menunjukkan bahwa ada pertanyaan yang tidak memiliki jawaban mekanis. Misalkan sebuah mesin dapat memutuskan, untuk setiap program dan input, apakah program itu pada akhirnya berhenti. Buatlah program baru yang menanyakan hal itu kepada si pemutus tentang dirinya sendiri lalu melakukan kebalikannya: jika diberi tahu bahwa ia berhenti, ia berulang selamanya, dan jika diberi tahu bahwa ia berulang, ia berhenti. Jawaban mana pun salah, jadi si pemutus tidak mungkin ada. Masalah perhentian tidak dapat diputuskan, dan bersamanya juga Entscheidungsproblem: tidak ada algoritma yang dapat menyelesaikan setiap pertanyaan matematika.

Berang-berang sibuk

Pada tahun 1962 Tibor Radó mengubah masalah perhentian menjadi sebuah permainan: di antara semua mesin dengan n keadaan dan simbol 0 dan 1 yang berhenti ketika dimulai pada pita kosong, mesin mana yang menulis angka 1 paling banyak, dan berapa langkah yang dapat diambil mesin seperti itu? Bilangan-bilangan ini, nilai berang-berang sibuk, tumbuh lebih cepat daripada fungsi terhitung apa pun, karena cara untuk menghitungnya akan menyelesaikan masalah perhentian. Nilai yang diketahui adalah 6, 21, dan 107 langkah untuk dua, tiga, dan empat keadaan; untuk lima keadaan, juara temuan Heiner Marxen dan Jürgen Buntrock mengambil 47.176.870 langkah, nilai yang dibuktikan pada tahun 2024 oleh kolaborasi daring bbchallenge dengan bukti yang diperiksa komputer. Untuk enam keadaan, diketahui ada mesin yang berjalan lebih banyak langkah daripada yang dapat dituliskan dengan notasi biasa.

Jelajahi

Buka simulator mesin Turing untuk menjalankan delapan program siap pakai atau menulis program Anda sendiri. Ikuti kepala langkah demi langkah dan lihat aturan mana yang dijalankan, saksikan pencacah yang tidak pernah berhenti, periksa palindrom, dan jalankan berang-berang sibuk: 107 langkah juara empat keadaan muat di diagram, dan 47 juta langkah juara lima keadaan hanya memakan beberapa detik pada kecepatan tercepat.

Pertanyaan yang sering diajukan

Apakah mesin Turing pernah dibuat?

Tidak seperti yang digambarkan Turing, karena pitanya tanpa ujung, tetapi gagasan itu segera diikuti oleh komputer program tersimpan yang nyata, yang ikut dirancang oleh Turing sendiri setelah Perang Dunia II. Sejak itu para penghobi telah membuat model yang berfungsi dari kayu, LEGO, bahkan di dalam Permainan Kehidupan, semuanya dengan pita terbatas, yang sudah cukup untuk perhitungan apa pun yang selesai.

Apa perbedaan antara jumlah langkah 14 dan 21 untuk tiga keadaan?

Ada dua pertanyaan berang-berang sibuk: angka 1 terbanyak yang ditulis dan langkah terbanyak yang diambil. Untuk tiga keadaan, mesin di simulator menulis maksimum enam angka 1 dalam 14 langkah, sedangkan mesin tiga keadaan lain mengambil maksimum 21 langkah tetapi hanya menyisakan lima angka 1. Untuk dua, empat, dan lima keadaan, satu mesin memenangkan keduanya.

Apakah Turing-lengkap berarti kuat?

Artinya mampu menghitung apa pun yang dapat dihitung, asalkan waktu dan memorinya cukup, dan itu tidak mengatakan apa pun tentang kecepatan. Mesin Turing memerlukan banyak langkah untuk aritmetika sederhana, dan beberapa sistem menjadi Turing-lengkap hampir secara kebetulan, seperti permainan kartu, rumus spreadsheet, dan redstone Minecraft.

Mengapa komputer tidak bisa begitu saja menjalankan program untuk melihat apakah program itu berhenti?

Menjalankannya menunjukkan bahwa sebuah program berhenti, jika memang berhenti, tetapi jika program itu belum berhenti, Anda tidak dapat mengetahui apakah ia tidak akan pernah berhenti atau hanya memerlukan lebih banyak waktu. Bukti Turing menunjukkan bahwa tidak ada metode yang lebih cerdik yang berhasil untuk setiap program, meskipun untuk banyak program tertentu pertanyaan itu dapat dijawab.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka simulator mesin Turing