Biz diyoruz Langton en karınca bir iki boyutlu hücresel otomat (bkz Turing makinesi çok basit bir dizi kural içeren). Mucidi Christopher Langton'un adı verildi .
Ortaya çıkan davranış örneğini vurgulamak için en basit sistemlerden biridir .
İki boyutlu bir ızgaranın kareleri beyaz veya siyah olabilir. Bu kutulardan biri keyfi olarak karıncanın ilk yeri olarak kabul edilir . Başlangıç durumunda tüm kutular aynı renktedir.
Karınca her seferinde aşağıdaki kurallara göre sola, sağa, yukarı veya aşağı hareket edebilir:
Langton'ın karıncasını , ızgara kutularının çoğunun beyaz veya siyah olduğu ve karınca kutusunun hem rengini hem de ızgaranın yönünü kodlayan sekiz farklı durum alabildiği bir hücresel otomat olarak tanımlamak da mümkündür .
Bu basit kurallar, karıncanın şaşırtıcı bir davranışına yol açar: karınca, görünüşte kaotik bir dönemden sonra, kendini sonsuza kadar tekrar eden 104 aşamadan oluşan bir "yol" inşa eder. Bu 104 adımlık rota, bir Langton'ın karınca çekicisi gibi görünüyor . Bu çeker , ızgara başlangıçta boş olduğunda ve farklı başlangıç koşulları için görünür. Bu davranışın, ızgaraya çizilen herhangi bir başlangıç sonlu model için doğru kaldığını varsayıyoruz (diğer yandan, kendimize sonsuz bir modele izin verirsek yanlıştır).
Langton'ın karıncalarındaki bazı problemler , bir P-tam problemi olan bir Boole devresinin değerlendirilmesine kadar izlenebilir .
Basit bir uzantı, karınca tarafından döngüsel olarak değiştirilen ikiden fazla renk kullanmaktır. Her bir karıncanın basit bir şekilde adlandırılması, karıncanın kendisiyle karşılaştığında sola mı yoksa sağa mı dönmesi gerektiğini belirtmek için her renge "G" veya "D" harfini atamaktır. Bu nedenle, Langton'ın karıncası "DG" olarak adlandırılacaktır.
Bu uzantılardan bazıları "DGGD" gibi simetrik desenler üretir.