Hücresel Otomatlar Hakkında | Hayat Oyunu, Kural 30, Kural 110 ve Daha Fazlası

Dört temel parça

Her hücresel otomat aynı dört parçadan oluşur. Izgara, hücrelerin yaşadığı alandır. Tek boyutlu bir çizgi, satranç tahtası gibi iki boyutlu bir düzlem, hatta üç boyutlu bir uzay olabilir. Durumlar, bir hücrenin alabileceği değerlerdir. En basit durumda hücre ikilidir: siyah ya da beyaz, 1 ya da 0. Komşuluk, bir hücreyi doğrudan etkileyen hücreler kümesidir. Kare ızgarada bu genellikle çevredeki sekiz hücrenin tümünü kapsayan Moore komşuluğu ya da yalnızca kuzey, doğu, güney ve batıyı kapsayan von Neumann komşuluğudur. Kurallar otomatın beynidir: her hücreye yeni durumunu veren mantık. Örneğin: canlıysam ama ikiden az canlı komşum varsa yalnızlıktan ölürüm. Her hücre aynı kuralları aynı anda uygular.

1. Conway’in Hayat Oyunu

Kurallar: B3/S23. Canlı bir hücre 2 ya da 3 canlı komşusu varsa hayatta kalır. Ölü bir hücre tam 3 canlı komşuyla canlanır. Diğer tüm hücreler bir sonraki nesilde ölüdür. John Conway onu 1970’te tasarladı ve Martin Gardner’ın Scientific American’daki köşesi onu ünlü yaptı. Planörler, osilatörler ve uzay gemileri üretir. Bill Gosper aynı yıl ilk planör tabancasını buldu: her 30 nesilde bir, sonsuza dek yeni bir planör fırlatan bir desen. Hayat hesaplama yapabilir, çünkü planörler sinyal taşıyabilir ve mantık kapıları gibi çarpışabilir. Hepsinden önemlisi, basit kurallardan karmaşık davranışın doğduğunu gösterir.

Hayat Oyunu’nda çapraz bir planör akışı fırlatan Gosper planör tabancası — 330 nesil sonra Gosper planör tabancası. PictorX’te oluşturuldu.

2. Kural 30

Tür: tek boyutlu temel hücresel otomat. Her hücrenin bir sonraki durumu kendisine ve iki komşusuna bağlıdır ve her nesil sonuncunun altına yeni bir satır olarak çizilir. Stephen Wolfram Kural 30’u 1983’te tanıttı. Tek bir siyah hücreden başlatın, kaotik bir üçgen büyütür. Deterministik kuralına rağmen rastgele görünür; o kadar rastgele ki orta sütunu sözde rastgele sayı üreteci olarak kullanılmıştır. Aynı türden üçgenler Conus textile deniz kabuğunun pigmentinde de görülür.

Tek bir siyah hücreden büyüyen Kural 30 üçgeni; sağda kaotik, solda çizgili — Tek siyah hücreden 224 nesil boyunca büyüyen Kural 30. PictorX’te oluşturuldu.

3. Kural 110

Tür: Kural 30 gibi tek boyutlu temel hücresel otomat, ama sekiz yanıttan oluşan farklı bir tabloyla. Kural 110’un hesaplama açısından evrensel olduğu kanıtlanmıştır: Matthew Cook, uygun bir ilk satırla genel amaçlı bir bilgisayarın yapabileceği her hesaplamayı taklit edebildiğini gösterdi. Tekrarlanan bir arka plan üzerinde ilerleyen ve karşılaştıklarında etkileşen hareketli yapılar barındırır. Kanıt, mantık olarak bu çarpışmaları kullanır. Çok basit kuralların keyfi hesaplamayı nasıl taklit edebildiğini gösterir.

Sağdaki tek bir hücreden büyüyen ve iç içe üçgenlerle sola yayılan Kural 110 — Sağ kenardaki tek siyah hücreden Kural 110. PictorX’te oluşturuldu.

4. Brian's Brain

Durumlar: kapalı, açık (ateşleyen) ve refrakter. Kurallar: kapalı bir hücre tam 2 komşusu açıksa açılır. Açık bir hücre refrakter olur. Refrakter bir hücre kapanır. Onu Brian Silverman tasarladı. Bir hücre ateşledikten sonra bir nesil dinlenmek zorunda olduğundan, her darbe geçtiği yerden uzaklaşmaya devam eder. Sonuç, sinir dokusu ya da kalp kası gibi uyarılabilir ortamlardaki dalgalara benzeyen ve çoğu zaman canlı ve organik görünen, kendi kendine ilerleyen desenlerden oluşan bir kalabalıktır.

Rastgele bir yamadan yayılan Brian's Brain; ateşleyen hücreler sarı, solan izler mor — Rastgele bir yamadan 70 nesil sonra Brian's Brain, solan izlerle. PictorX’te oluşturuldu.

5. Wireworld

Durumlar: boş, elektron başı, elektron kuyruğu ve iletken. Kurallar: baş kuyruğa, kuyruk iletkene dönüşür; iletken ise komşularından tam 1 ya da 2 tanesi baş olduğunda başa dönüşür. Boş hücreler boş kalır. Wireworld’ü de 1987’de Brian Silverman tasarladı. İletken hücreler tellerdir ve ardından bir kuyruk gelen baş, bu teller boyunca ilerleyen bir elektrondur. Elektronik devreleri simüle edebilir: tek elektronlu bir tel halkası bir saattir, küçük bir çentik bir diyottur ve birkaç hücre bir mantık kapısı oluşturur. İçinde eksiksiz bilgisayarlar inşa edilmiştir; örneğin David Moore ve Mark Owen’ın asal sayıları hesaplayan Wireworld bilgisayarı.

İki saat halkası, iki diyot ve bir XOR kapısı olan Wireworld devresi; sarı tel üzerinde mavi ve kırmızı elektronlar — Wireworld’de iki saat, iki diyot ve bir XOR kapısı. PictorX’te oluşturuldu.

Wolfram’ın 256 kuralı ve dört sınıfı

İki komşusu olan tek boyutlu bir hücre, 111’den 000’a kadar sekiz desenden birini görür. Bir kural her biri için yeni durumu verir; yani sekiz bittir ve 2⁸ = 256 temel kural vardır. Sekiz yanıtı ikili bir sayı olarak okuyun, kuralın adını elde edersiniz: Kural 30’un karşılığı 00011110, Kural 110’unki ise 01101110’dur. Stephen Wolfram kuralları yaptıklarına göre, düzenden kaosa doğru sıraladı. 1. Sınıf 1 tekdüze bir duruma oturur. 2. Sınıf 2 kararlı ya da tekrarlanan yapılara oturur. 3. Sınıf 3, Kural 30 gibi kaotik ve rastgele görünümlü kalır. 4. Sınıf 4, Kural 110 gibi düzen ile kaos arasındaki sınırda hareket eden ve etkileşen yapılar kurar.

Zorluk sıralaması

Hayat Oyunu ★☆☆☆☆ · Kural 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Kural 110 ★★★★★. İlk ikisi siz izlerken kendini açıklar. Kural 110 hareketli yapılarını tekrarlanan bir arka planda gizler.

Görsel olarak en güzeller

1. Brian's Brain · 2. Conway’in Hayat Oyunu · 3. Kural 30 · 4. Kural 110 · 5. Wireworld.

Matematiksel olarak en önemliler

1. Kural 110, evrensellik için · 2. Hayat Oyunu, evrensellik ve ortaya çıkış için · 3. Kural 30, kaos ve rastgelelik için · 4. Wireworld, dijital mantık için · 5. Brian's Brain, uyarılabilir sistemler için.

Doğada, fizikte ve kriptografide

Hücresel otomatlar doğadaki, fizikteki ve kriptografideki karmaşık sistemleri simüle etmek için kullanılır. Fikir, 1940’larda kendini kopyalayabilen bir makine tasarlamak için hücrelerden oluşan bir ızgara kullanan Stanisław Ulam ve John von Neumann’a dayanır. Gerçek dünyada hücresel otomatları, üçgenleri Kural 30’a benzeyen Conus textile gibi bazı deniz kabuklarının pigmentinde ve pulları hücresel otomata yakın bir kurala göre yeşil ile siyah arasında geçiş yapan gözlü kertenkelede (Timon lepidus) görebilirsiniz. Fizikçiler onları gaz akışını, kum yığınlarını ve orman yangınlarını modellemek için kullanır. Kural 30’un görünürdeki rastgeleliği onu rastgele sayı üreteçleri ve akış şifreleri için bir aday yaptı.

PictorX’te keşfedin

Beşini de çalıştırmak için Hücresel Otomatlar uygulamasını açın. Planör tabancasını, bir uzay gemisi filosunu ya da kararlı hale gelmesi 1.103 nesil süren R-pentominoyu izleyin. B36/S23 gibi herhangi bir Hayat kuralını ya da 0 ile 255 arasında herhangi bir temel kural numarasını yazın. Hücre çizin ve silin, Wireworld devrelerinden elektron gönderin, kenarları birleştirin ve renkli moda geçin. PNG kaydedin ya da tuvali PictorX düzenleyicisinde açın.

Sık sorulan sorular

Hücresel otomat nedir?

Her hücrenin bir durumu olduğu bir hücre ızgarası. Her adımda tüm hücreler, yalnızca bir hücreye ve komşularına bakan tek bir sabit kurala göre birlikte güncellenir. Kurallar basit olsa da desenler karmaşık ve öngörülemez olabilir.

Hücresel otomatları kim icat etti?

Stanisław Ulam ve John von Neumann, 1940’larda Los Alamos’ta. John Conway’in Hayat Oyunu (1970) fikri popüler yaptı ve Stephen Wolfram 1980’lerde 256 temel kuralı inceledi.

Hangi hücresel otomatlar Turing-tamdır?

Buradaki beşi arasında Kural 110 ve Hayat Oyunu’nun evrensel olduğu kanıtlanmıştır; Wireworld ise eksiksiz bir bilgisayarı barındırabilir. Evrensel, doğru başlangıç deseniyle genel amaçlı bir bilgisayarın yapabileceği her hesaplamayı yapabilmeleri demektir.

Wolfram’ın dört sınıfı nelerdir?

Sınıf 1 sönerek tekdüze bir duruma ulaşır, sınıf 2 kararlı ya da tekrarlanan yapılara oturur, sınıf 3 Kural 30 gibi kaotik kalır ve sınıf 4 Kural 110 gibi hareket eden, etkileşen yapılar kurar.

Kural 30 neden rastgele görünür?

Her adım sabittir, ama her hücre sol komşusunu diğer ikisiyle, küçük farkları hızla yayacak şekilde karıştırır. Orta sütununda basit bir desen bulunamamıştır; bu yüzden rastgele sayı üretmek için kullanılmıştır.