Langton karıncası

Langton karıncası, bir karınca ailesinin en basit üyesidir. Boş hücre için 0’dan başlayarak numaralandırılmış n renk varsa, kural her renge bir harf karşılık gelecek şekilde R ve L harflerinden oluşan bir $r = r_0 r_1 \cdots r_{n-1}$ dizisidir. Langton karıncasının kuralı RL’dir. Karınca p hücresinde d yönüne bakıyorsa bir adım şöyledir:

Karıncanın belleği yoktur; yalnızca altındaki rengi görür. Burada önce düzenli şekiller, sonra karmaşık bir yumak, ardından bir yol oluşturmasını izleyebilir; onu geriye yürütebilir, yolundaki hücreleri boyayabilir ve başka harf dizilerini deneyebilirsiniz.

Renkler kuralın durumlarıdır. Düzlemin kenarı yoktur ve karşı tarafa sarılmaz. Panelin üstündeki eğri, her adımdan sonraki boyalı kare sayısını gösterir.

Boş düzlemde yukarı bakarak başlayan karınca önce küçük, düzenli desenler oluşturur. 473. adımdaki gibi bazıları yarım tur dönmeye göre simetriktir. Ardından yaklaşık on bin adım boyunca rastgele görünen bir yumak gelir. Sonra 9 977. adımdan itibaren karınca aynı 104 hareketi tekrarlar; her döngü (−2, 2), yani iki hücre sola ve iki hücre aşağı kaymıştır. Karınca, otoyol denen köşegen bir şerit inşa eder ve her 104 adımda tam 12 renkli hücre eklenir. Yalnızca karıncanın hareketleri ve altındaki şerit tekrarlanır. Arkasındaki yumak yerinde kalır.

Birkaç döngünün tekrarlanması hiçbir şeyi kanıtlamaz; sonraki döngü renkli bir hücreye rastlayıp yoldan çıkabilir. Bu yüzden sayfa, ancak bir denetimden sonra yolun süreceğini garanti eder. Son döngü bittiğinde, okunan hücreler karıncanın yer değiştirmesi kadar ötelenirse, elde edilen hücrelerin renkleri asıl hücrelerin döngüden önceki renkleriyle aynı olmalı; karınca da o zamanki yönüne bakmalıdır. Ayrıca gelecekteki her döngüde, önceki döngünün hücrelerinin dışına çıkan hücreler şimdi boş olmalı ve denetlenen döngüden itibaren hiçbir döngü tarafından ziyaret edilmemiş olmalıdır. Böylece her döngü, bir öncekinin karşılaştığı durumun aynısıyla karşılaşır ve aynı hareketleri sonsuza kadar yapar. Eğrideki kesikli çizgi, tekrarın başladığı yeri gösterir. İleride renkli bir hücre varsa sayfa onu daire içine alır ve garanti vermez.

Dolayısıyla boş düzlem için yol, hesaplama ve bu denetim birlikte kullanılarak kanıtlanmıştır. RL için, sonlu sayıda renkli hücre içeren ve şimdiye kadar denenmiş bütün tahtalar sonunda yol oluşturur; ancak hepsinin bunu yapacağı henüz kanıtlanmamıştır.

Her adım geri alınabilir. Karınca az önce yürüdüğü yöne baktığından, geldiği hücre arkasındadır ve o hücrenin rengi döngüde bir sıra ilerlemiştir. Bir adım geri gitmek şöyledir:

Yani tahta ile karınca, bir adım önceki durumu belirler. Geri, bir kaydı tersten oynatmaz; karıncayı kurala göre geriye yürütür.

Harfler çoğaldığında, her ziyaret hücreyi bir sonraki renge geçirir. Boş düzlemden başlayan kural düğmeleri çok farklı şekiller büyütür: LLRR için simetrik görünen bir desen, LRRRRRLLR için neredeyse içi dolu bir kare, RRLLLRLLLRRR için büyüyen bir üçgen. Bu üçünün sonunda ne olacağı bilinmiyor. LLRRRLRLRLLR ise yaklaşık otuz bin adımdan sonra gerçekten bir yol oluşturur.

Chris Langton bu karıncayı 1986’da yapay yaşam örneği olarak tanımladı.