Semut Langton

Semut Langton adalah yang paling sederhana dalam satu keluarga semut. Dengan n warna yang diberi nomor mulai dari 0 untuk kosong, sebuah aturan berupa deretan $r = r_0 r_1 \cdots r_{n-1}$ yang tersusun dari huruf R dan L, satu huruf untuk tiap warna. Aturan semut Langton adalah RL. Semut berdiri di petak p menghadap arah d, dan satu langkahnya adalah

Semut tidak memiliki ingatan dan hanya melihat warna di bawahnya. Di sini Anda dapat melihatnya membentuk keteraturan, lalu kekusutan, lalu jalan; Anda juga bisa menjalankannya mundur, mewarnai petak di jalurnya, dan mencoba deretan huruf lain.

Warna adalah keadaan dalam aturan. Bidang tidak memiliki tepi dan tidak tersambung kembali ke sisi seberangnya. Kurva di bagian atas panel menghitung petak berwarna setelah setiap langkah.

Dimulai pada bidang kosong sambil menghadap ke atas, semut mula-mula membuat pola kecil yang rapi. Beberapa simetris terhadap putaran setengah lingkaran, seperti pada langkah 473. Kemudian muncul kekusutan yang tampak acak selama sekitar sepuluh ribu langkah. Mulai langkah 9 977, semut mengulang 104 gerakan yang sama, dengan tiap putaran bergeser (−2, 2): dua petak ke kiri dan dua ke bawah. Semut membangun pita diagonal yang disebut jalan raya, dan setiap 104 langkah menambah tepat 12 petak berwarna. Hanya gerakan semut dan pita di bawahnya yang berulang. Kekusutan di belakang tetap di tempatnya.

Beberapa putaran berulang tidak membuktikan apa-apa: putaran berikutnya bisa menemui petak berwarna dan berbelok keluar. Karena itu, halaman menjamin jalan hanya setelah pemeriksaan. Setelah putaran terakhir, petak yang dibaca, jika digeser sebesar perpindahan semut, harus menunjukkan warna yang dimiliki petak asal sebelum putaran itu, dan semut harus menghadap arah yang sama seperti saat itu. Selain itu, dalam setiap putaran mendatang, petak di luar petak putaran sebelumnya harus kosong sekarang dan tidak boleh pernah dikunjungi oleh putaran mana pun sejak putaran yang diperiksa. Dengan begitu, setiap putaran menjumpai persis apa yang dijumpai putaran sebelumnya, sehingga gerakannya sama selamanya. Garis putus-putus pada kurva menandai awal pengulangan. Jika ada petak berwarna di depan, halaman melingkarinya dan tidak memberi jaminan.

Jadi, untuk bidang kosong, jalan itu terbukti melalui perhitungan beserta pemeriksaan ini. Untuk RL, semua papan dengan jumlah petak berwarna berhingga yang pernah dicoba akhirnya membentuk jalan, tetapi belum ada yang membuktikan bahwa semua papan seperti itu pasti demikian.

Setiap langkah bisa dibatalkan. Semut menghadap arah gerakan terakhirnya, jadi petak asalnya berada di belakang, dan warna petak itu telah maju satu posisi dalam siklus. Satu langkah mundur adalah

Jadi, papan dan semut menentukan keadaan satu langkah sebelumnya. Mundur menjalankan semut ke belakang menurut aturan, bukan memutar rekaman secara terbalik.

Dengan lebih banyak huruf, setiap kunjungan memajukan petak ke warna berikutnya. Dari bidang kosong, tombol-tombol aturan menumbuhkan bentuk yang sangat berbeda: pola yang tampak simetris untuk LLRR, persegi yang hampir penuh untuk LRRRRRLLR, dan segitiga yang terus membesar untuk RRLLLRLLLRRR. Bagaimana ketiganya berakhir belum diketahui. LLRRRLRLRLLR memang membentuk jalan setelah sekitar tiga puluh ribu langkah.

Chris Langton menjelaskan semut ini pada 1986 sebagai contoh kehidupan buatan.