Keadaan
Jumlah langkah
Simbol di pita
Status

Keadaan Baca Tulis Gerak Keadaan berikutnya

Selengkapnya tentang mesin Turing

Simulator mesin Turing

Mesin Turing adalah komputer paling sederhana yang mungkin ada: sebuah kepala yang membaca satu simbol dari pita tanpa ujung, menulis sebuah simbol, bergerak satu sel ke kiri atau ke kanan, dan mengubah keadaannya, mengikuti tabel aturan yang pendek. Alan Turing menciptakannya pada tahun 1936, dan segala yang dilakukan komputer Anda pada prinsipnya dapat dilakukan dengan cara ini. Tulis aturan Anda sendiri atau muat contoh, tekan Jalankan, dan saksikan pita berubah langkah demi langkah, dengan diagram seluruh riwayatnya di bawahnya. Pilih program atau tulis sendiri, masukkan input, lalu tekan Jalankan, atau Langkah untuk mengikuti satu aturan setiap kali; Mundur membatalkan satu langkah. Setiap baris program adalah satu aturan: keadaan, simbol yang dibaca, simbol yang ditulis, gerakan (L, R, atau N untuk tidak bergerak) dan keadaan berikutnya, misalnya A 0 -> 1 R B. Gunakan _ untuk sel kosong. Mesin mulai dalam keadaan aturan pertama, pada simbol pertama input, dan berhenti di H, accept, atau reject, atau ketika tidak ada aturan yang cocok. Diagram menampilkan pita setelah setiap langkah, dari atas ke bawah.

Cara kerjanya

  1. Pilih contoh program atau tulis aturan seperti A 0 -> 1 R B, satu per baris, lalu ketik input.
  2. Tekan Jalankan untuk melihat kepala bergerak, atau Langkah untuk mengikuti satu aturan setiap kali; Mundur membatalkan satu langkah.
  3. Baca keadaan, jumlah langkah, dan simbol di pita pada kotak-kotak, serta riwayat pita pada diagram.

Cara kerja mesin

Pada setiap saat mesin berada dalam salah satu dari beberapa keadaan, dan kepalanya berada di satu sel pita. Aturan untuk keadaan itu dan simbol di bawah kepala menyatakan tiga hal: simbol apa yang ditulis di sel, apakah bergerak ke kiri, ke kanan, atau tidak sama sekali, dan ke keadaan mana selanjutnya. Itulah seluruh mesinnya. Mesin berhenti ketika mencapai keadaan berhenti, seperti H, accept, atau reject, atau ketika tidak ada aturan yang cocok. Program untuk menambahkan 1 ke bilangan biner hanya memerlukan sembilan aturan semacam itu.

Berang-berang sibuk

Di antara mesin dengan n keadaan yang dimulai pada pita kosong, mesin manakah yang menulis angka 1 paling banyak sebelum berhenti? Tibor Radó mengajukan pertanyaan ini pada tahun 1962. Para juaranya disebut berang-berang sibuk (busy beaver), dan mereka tumbuh lebih cepat daripada fungsi apa pun yang dapat dihitung komputer. Dua keadaan menghasilkan 4 angka 1 dalam 6 langkah, tiga keadaan 6 angka 1, empat keadaan 13 angka 1 dalam 107 langkah. Juara lima keadaan, yang ditemukan pada tahun 1989, menulis 4.098 angka 1 dalam 47.176.870 langkah, dan pada tahun 2024 sebuah kolaborasi daring membuktikan dengan matematika yang diperiksa komputer bahwa tidak ada mesin lima keadaan lain yang berhenti yang berjalan lebih lama.

Pertanyaan yang sering diajukan

Bagaimana cara menulis aturan?

Satu aturan per baris: keadaan saat ini, simbol yang dibacanya, simbol yang ditulis, gerakan (L, R, atau N), dan keadaan berikutnya, misalnya A 0 -> 1 R B. Panah dan koma bersifat opsional. Gunakan _ untuk sel kosong dan # untuk komentar. Mesin mulai dalam keadaan aturan pertama; keadaan berikutnya yang bernama H atau halt menghentikannya, sedangkan accept dan reject menghentikannya dengan sebuah putusan.

Apakah mesin Turing benar-benar dapat menghitung apa saja?

Apa pun yang dapat dihitung oleh komputer mana pun, asalkan pita dan waktunya cukup: itulah tesis Church–Turing. Mesin Turing tidak memiliki batas memori, sehingga dalam arti itu ia lebih kuat daripada komputer nyata mana pun, meskipun jauh lebih lambat. Yang tidak dapat dilakukannya adalah menjawab setiap pertanyaan: Turing membuktikan bahwa tidak ada mesin yang dapat memutuskan, untuk setiap program dan input, apakah program itu akan berhenti.

Mengapa pencacah tidak pernah berhenti?

Aturannya tidak pernah mengarah ke keadaan berhenti. Ia terus menambahkan 1 ke bilangan biner di ujung kanan pita lalu berjalan kembali, sehingga bilangan itu tumbuh selamanya. Masalah perhentian Turing menyatakan bahwa tidak ada metode umum yang dapat mengetahui, untuk setiap mesin, apakah mesin itu akan berhenti; untuk pencacah sederhana ini Anda dapat melihatnya, tetapi untuk beberapa mesin yang hanya memiliki enam keadaan belum ada yang tahu.

Bagaimana berang-berang sibuk lima keadaan bisa berjalan 47 juta langkah di sini?

Pita disimpan sebagai larik ringkas yang tumbuh ke dua arah, dan pada pengaturan tercepat aplikasi menjalankan ratusan ribu langkah di antara pembaruan layar, sehingga seluruh proses hanya memakan beberapa detik di browser modern. Diagram hanya merekam 400 langkah pertama, karena gambar dengan 47 juta baris tidak akan muat di layar mana pun.

Apakah ada yang dikirim ke server?

Tidak. Program berjalan di browser Anda, dan program serta input Anda tetap tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

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

Ke Editor