Conway'in Hayat Oyunu

Vikipedi, özgür ansiklopedi
Atla: kullan, ara
Gosper'ın planör silahı yaratımı "planörler".
Color coded racetrack large channel.gif

Hayat oyunu 1970'de İngiliz matematikçi Horton Conway tarafından geliştirirmiş bir hücresel otomattır. Hücresel otomatın en iyi bilinen örneğidir.

Bu oyun aslında, insan oyunculardan girdiye ihtiyaçsız başlangıç durumları tarafından evreleri saptanan anlamına gelen insansız bir oyundur. Birinin başlangıç yapılandırmasını yaratarak ve nasıl geliştiğini gözlemleyerek hayat oyununu etkilemesidir.

Kökeni[değiştir | kaynağı değiştir]

Conway, kendisinin kopyasını yapabilen varsayımsal bir makine bulmak için denemeler yapan ve kartezyen ızgarası üstünde çok karmaşık kurallarla işleyen bir mekanizma gibi matematik modeli bulduğu zaman başarılı olan ünlü matematikçi John von Neumann'ın 1940larda sunduğu bir problem ile ilgilendi. Conway von Neumann'ın düşüncesini basitleştirmeyi denedi ve neticede başardı. Önceki başarısı ile Leech'in problemini kendini türeten mekanizma hakkında von Neumann'ın düşüncelerindeki ilgisi ile birlikte bir grup teoride birleştirerek Conway "the Game of Life"ı tasarladı.

Bunun Amerikan Bilimleri'nin Ekim 1970 sayısında Martin Gardner'in "Matematik Oyunları" köşesinde ilk halk gösterimi yapıldı. Görüşün bir teorik noktasından dolayı bu ilginçti çünkü bu Turing makinesinin gücüne sahipti: Conway'in Hayat Oyun'una algoritmik olarak herhangi bir şey hesaplatılabiliyordu. Gardner yazısında:

Bu oyun Conway hemen meşhur yapacak, ama hem de bütün matematik araştırmalarının yeni alanlarıyla görüşmeye başladı, hücresel özdevinirin alanı (...) yaşama benzer şekilde yükselme, düşüş ve yaşayan organizmanın toplumunun değişimi sebebiyle, bu 'simülasyon oyunları' denilen gelişen kategorinin içine ait (gerçek yaşam süreçlerine benzeyen oyunlar)

Yayınlanmasından beri, gelişebilen kalıpların şaşırtıcı yoluyla çok ilgi çekiyor. Yaşam ortaya çıkmanın ve kendinden organizasyonun bir örneğidir. Bu çok kolay kuralların yaşama geçiminden karmaşık kalıplar ortaya çıkabildiği yolu gözlemek için fizikçi, ekonomist, matematikçi, filozof, biyolog, üretken bilimlerin ve diğerleri için Conway'in Hayat Oyunu ilgi çekicidir.

Conway'in hayat oyununa marketlerde satışa sunulan ucuz yeni minibilgisayarların yeni nesilleri için zamanda oluşa gelmesi gerçeği, gecede başka türlü kullanılmammış bu makinelerin üstünde saatlerce çalışabilmesi anlamında, yardım etti. Bu itibar daha sonraki bilgisayar fraktral yapılarının tutulmasının habercisi oldu. Birçok meraklı için yaşam sadece bir programlama uğraşısı, CPU döngülerini israf etmek için eğlenceli bir yoldu. Ama bazıları için, yaşam çok filozofik yan anlamlara sahipti. Bu 1970ler ve sonrasında bir moda takip geliştirdi; güncel gelişmeler yaşam panosunun sınırlarının içindeki bilgisayar sistemlerinin teorik taklitlerinin yaratımına kadar vardı.

Önemli deneylerden sonra Conway 3 kritere göre dikkatlice kurallarını seçmiştir:

  1. Sınırsız nüfusu büyümeyen bir basit geçirmez (kanıt) için başlangıç kalıpları olmamalıdır.
  2. Görünüşe göre sınırsız büyümeyen başlangıç kalıpları olmalıdır.
  3. Aşağıdaki mümkün yollarda sona varmadan önce bir önemli zaman periyodu için değişen ve büyüyen basit başlangıç kalıpları olmalıdır:
    • Yavaş yavaş tamamen yok olma (aşırı kalıplaşmadan veya seyrekleşen oluşundan); veya
    • İki veya daha çok periyotun sonsuz döngüsünde tekrar eden sallanan kalıpları katarak veya ondan sonra değişmeden kalan sabit bir biçime yerleşme.

Kurallar[değiştir | kaynağı değiştir]

Hayat oyununun evreni sonsuz iki boyutlu dikey ızgaraların kare hücreleridir. Hücreler iki durumda olabilir: ölü ya da diri. Her hücre yatay, dikey veya çapraz omak üzere bitişik olan sekiz komşusuyla doğrudan etkileşir. Herhangi bir hücre için, her zaman adımında aşağıdaki değişikliklerden biri gerçekleşir:

  • Bir canlı hücrenin, iki'den daha az canlı komşusu varsa "yalnızlık nedeniyle" ölür
  • Bir canlı hücrenin, üç'ten daha fazla canlı komşusu varsa "kalabalıklaşma nedeniyle" ölür
  • Bir canlı hücrenin, iki ya da üç canlı komşusu varsa değişmeden bir sonraki nesile kalır
  • Bir ölü hücrenin tam olarak üç canlı komşusu varsa canlanır.

Başlangıçtaki dağılıma sistemin "tohumu" denir. Birinci nesil, üstteki kuralların eş zamanlı olarak "tohum"daki her hücreye uygulanmasıyla elde edilir.-canlanmalar ve ölümler tek bir anda oluşur. Bu bir sonraki nesle geçiş adımına bazen "tick" adı verilir. (başka bir deyişle, her nesil yalnızca bir önceki nesildeki dağılımın bir sonucudur). Bu kuralllar daha fazla nesil yaratmak için aynı şekilde ard arda uygulanır.

Kalıpların örnekleri[değiştir | kaynağı değiştir]

Bir "planör"'ün evrimi ve hareketi

Statik kalıplar (natürmort), tekrar eden kalıplar ( "osilatör" natürmortun üst kümesi) aynı yönde kendilerini çeviren kalıplar (uzay gemisi) gibi birçok farklı türde kalıp hayat oyununda gerçekleşir.

 Game of life block.png     Game of life boat.png     Game of life blinker.png     Game of life toad.png     Game of life glider.png     Game of life lwss.png   4demons.svg 
Blok Kayık Pirildak Kara kurbağa Planör LWSS Pulsar

Blok ve kayık hareketsiz yaşam, "fırıldak" ve kara kurbağa" çift fazlı osilatör, ve planör ve LWSS zamanın geçmesi gibi, muntazam ızgaraların içinden yollarında yürüyen uzay gemisidirler. Pulsar çok yaygın 3 periyodlu osilatördür. İki perüyodlu doğal meydana gelen iki peiyodlu osilatörlerin büyük çoğunluğu, fırıldak ve kara kurbağa gibidir, ama 4, 8, 15, 30, ve birkaç diğeri nadir fırsatlarda görür.

Çok yaşlı adam denilen kalıplar uzun periyotlar için önce tekrar ederek gelişebilir. "Tutucu" bir kalıp 130 nesilden veya basamaktan önce genelde kaybolur. “Meşe palamudu” en azından 25 “planör” ve birçok “asilatör” gibi istiklar sağlayıcı üretmek için 5206 nesil alır.

 Game of life diehard.png   Game of life methuselah.png 
Tutucu Meşe palamudu

Conway başlangıçta kalıpsızlıktan süresiz büyüyebilmeye –i.e., bir sınırlı sayıda yaşayan hücre ile herhangi bir önceki kurulumun, nüfusun sınırlı limitin ötesine büyüyememesine dayanır. Matematiksel oyunlarının içinde oyunun özgün ortaya çıkışında, Conway 1970in sonundan önce varsayımı kanıtlayana veya çürütene 50$ ödül teklif eder. Çürütmenin bir yolu da karşıtlıkları ekleyerek alanda tutan kalıpları keşfetmek olacaktır: hareket eden “planör” veya lokomotif gibi bir nesneye defalarca ateş etmeye yapılandırırılmış, hereket eden ama arkasında kalıcı "duma"nın izini bırakmaya yapılandırılandırılmış olan bir "silah".

Ödülü aynı yılın Kasımında Massachusetts Institute of Technology'den Bill Gosper'ın liderliğinde bir grup kazandı; Gosper silahı, 15'inci nesil ilk planörü olan üretimi, ve her 30’ncu nesilden sonra başka planör aşağıda gösterilmiştir:

Game of life glider gun.png
Gosper Planör Silahı

Sonsuz büyümenin sergisinin basit kalıpları daha sonra bulundu. Tüm üç aşağaıdaki kalıpların her üçü süresiz büyür: ilk iki her motoru açan bir "blok-döşeme" yaratırken üçüncüsü iki yaratır. İlki sadece 10 yaşayan hücreye (minimum olduğu kanıtlanan) sahiptir. İkinci 5x5 bir kare formundadır. Üçüncüsü sadece bir hücre yüksekliğindedir:

Game of life infinite1.png     Game of life infinite2.png

Game of life infinite3.png

Sonraki buluşlar sabit ve planörler veya diğer uzaygemileriyle çarpışan, "silahlar"ı ; "bir döküntü izinin arkasında yaşam boyunca hareket eden, “balonbalıklar"ı; ve hareket eden ve uzay gemilerini yollayan, "tırmıklar"ı içerir. Hem de Gosper "üretici" denen, silahların izlerinin arkasından yaşayarak çalışan, asimptotik olarak en uygun ikinci dereceden büyüme oranı tertip eder.

İlginç yollarda diğer nesnelerden planörlerin etkilenmesi mümkündür. Örneğin eğer sadece doğru yolda iki planör bir engelde çarpışırlarsa, engel planörün kaynağına daha yakın hareket edecektir. Bu "kayan hafıza engeli" bir karşıtlığı taklit etmek için kullanılır. Bunun planörleri kullanarak VE, VEYA, ve DEĞİL gibi mantık kapıları inşa etmesi mümkündür. İki karşıtlığa bağlı bir sonlu hal makinesi gibi davranan bir kalıp yapması mümkündür. Bu Turing makinesi gibi aynı sayısal güce sahiptir. Böylece Hayat Oyunu herhangi sınırsız hafızalı bilgisayar kadar güçlüdür: bu eksiksiz Turing’dir.

Dahası, orijinal kalıpların kopyalarını içererek, bir kalıp inşa edilen yeni nesnelerle birleşen bir silahlar koleksiyonunu içerebilir. Kendinin birçok kopyasını kapsayan Turing eksiksiz bilgisayarını içeren ve karışık nesnelerin birçok türünü inşa edebilen bir "evrensel inşaatçı" inşa edilebilir. Bu yapıların tanımlamaları kazanan yollarda Conway, Elwyn Berlekamp ve Richard Guy tarafından verirdi.

Yineleme[değiştir | kaynağı değiştir]

Izgaranın üstündeki bir rasgele yaşayan başlangıç kalıplarından dolayı gözlemciler nesiller yanında imlerken sürekli değişerek nüfusu bulacaklardır. Kalıplar üzerine düşünülmüş güzelliğin bir formu olabilen basit kurallardan ortaya çıkar. Simetrik olmayan başlangıçlar simetrik olma eğilimi ile izole edilmiş küçük alt kalıplardır. Bollukta bu bir kez artabilir simetri olur, ama bir yakın kalıp düzenini bozmak için yakına gelmedikçe, kaybetdirilemez. Birçok sebepte tüm yaşayan hücrelerin yok olmasıyla toplum sonuncunda ortadan kaybolur, buna rağmen birçok büyük nesil için bu olmayabilir. İki veya birçok durum arasında sonsuza kadar salınan sabit biçimler veya kalıplardan birini üreterek çoğu başlangıç kalıbı sonunda "yanar"; hem de birçoğu başlangıç konumundan belirsizce uzaklara giden bir veya daha çok “planör” veya “uzay gemisi” üretir.

Algoritmalar[değiştir | kaynağı değiştir]

Yaşam Oyununun en erken sonuçları bilgisayarların kullanımı dışında elde edildi. Grafik kâğıtları, kara tahtalar, cismi oyun tahtalarında (go gibi) ve onun gibileri kullanılarak çeşitli kaderlerin küçük başlangıç kurulumları izlenir iken basit “osilatörler” ve “durgun-yaşamlar” keşfedildi. İlk araştırmalar boyunca, Conway F-pentomino (onun “R-pentomino” dediği) nesillerin küçük bir sayısı içinde dengede başarısız olduğu keşfetti.

Bu keşifler dünya üstündeki bilgisayar programlarına Yaşam kalıplarının evriminin izinde programlar yazmak için ilham verdi. Biri güncel nesilleri tutmak için ve biri içinde olan ardıllarını hesaplamak için tipik tarzda iki sıra kullanıldı. Çoğunlukla 0 ve 1 sırasıyla ölü ve yaşayan hücreleri temsil etti. Bir çift döngü, her ardıl dizlerin uygun elemanlarının 0 veya 1 olup olmadığına karar vermek için her hücrenin yaşan komşu hücresini sayarak döngü içinde güncel dizilerin her elamanını hesaba katar. Ardıl diziler gösterildi. Gelecek tekrarlama için diziler, gelecek tekrar için güncel dizi olan son tekrar içindeki ardıl diziler için görevleri değiş tokuş ettirir.

Basit şema için Minör artırımların çeşitleri olanaklıdır ve gereksiz hesapları kaydetmek için birçok yol vardır. Bir hücre son zaman basamağında ve onun değişmiş komşularının hiçbirinde değişmeyen, en uygun güncel zaman adımında değişmeyeceğine garanti edilmiş, yani güncellenmeyen hareketsiz bölgelerden geçerek zamanı kayıt edebilen aktif alanın izlerini tutan bir programdır.

Prensipte, yaşam alanı sonsuzdur ama bilgisayar sonlu hafızaya sahiptir ve çoğunlukla ileride sıranın boyutları bildirilmelidir. Sıranın sınırında aktif bölgeler haddini aştığında bu problemlere yol gösterir. Bu problemleri adreslemek için programcılar birçok stratejiye sahiptir. En basit strateji basit olarak her hücrenin dışındaki ölü dizileri varsaymaktır. Bu program için basittir ama aktif bölge sınırı geçtiği zaman, yanlış sonuçlar gösterir. Bir karışık hile bir halka diziden kar sağlayarak beraber dikili olan alanların sağ ve sol kenarlarını, ayrıca köşelerin dibi ve zirvesini üzerinde düşünmektir. Sonuç karşı köşede bir yeniden görünen arazinin kenarına çaprazlama hareket eden aktif bölgelerdir. Eğer kalıp çok geniş büyürse, Ama en azından patolojik kenar etkisi yoktur, yine de yanlışlık meydana gelebilir. Dinamik belleğin paylaşımının teknikleri ayrıca büyüyen kalıpları tutmak için durmadan genişleyen diziler yaratarak kullanılabilir.

Alternatif olarak, programcı yaşayan hücreleri gösteren koordinat çiftlerinin bir vektörü gibi bir farklı veri yapısı kullanabilir ve iki boyutlu bir dizi ile Yaşam alanlarını gösteren kavramlardan vazgeçebilir. Bu yaklaşım nüfusun yaşayan koordineli dizinin büyüklüğünü geçmedikçe kalıplara engellenmemiş alanların çevresinde hareket etmelerine izin verir. Dezavantajı simülasyonun hızı yavaşlayarak yaşayan hücreleri saymak bir arama işlemi haline gelir. Karmaşık veri yapıları ile bu problem büyük ölçüde çözülebilir.

Geniş kalıpları keşfetmek için fevkalade zaman derinlikleri, Hashlife gibi karışık algoritmalar yararlı olabilir.

Yaşamda varyasyonlar[değiştir | kaynağı değiştir]

Yaşamın orijinal başlangıcından beri, yeni kurallar geliştirirdi. Standart Yaşam Oyunu içinde, eğer bir hücre kesin olarak 3 komşuya sahipse, bir hücre "doğmuş" olur, eğer 2 veya 3 yaşayan komşuya sahipse ve başkalarını öldürüyorsa, hayatta kalır, "23/3" gibi sembolize edilir. Bir hücrenin devam etmesi için sayıların listesi veya ilk sayı gerekir. İkinci set için doğum gereklidir. Bu nedenle "16/6" "eğer 6 tane komşu var ise bir hücre doğar ve eğer 1 veya 6 komşudan herhangi biri varsa geçinir" anlamına gelir. Yüksek Yaşam bu nedenle 23/36 olur, çünkü içinde 6 tane komşusu vardır, üstelik orijinal oyunun 23/36 kuralı bir doğuşu yaratır. Yinelemelerinden dolayı Yüksek Yaşam en iyi olarak bilinir. İlaveten bu evrenlerin geniş çoğunluğunun kaotik veya metruk olmasına rağmen varyasyonlar yaşamda var olur.


Bir 2D altı köşeli Yaşam Oyunundan 48-adım oskilatör'ün örneği (kural 34/2).

Dikkate değer yaşam programları[değiştir | kaynağı değiştir]

Yüzlerce çevrimiçi yaşam programı var iken, bir liste burada karşılanamaz. Nadir veya popüler özellikler gibi önemli bazı isteklere göre cüzi sayıda programın bir seçkisi aşağıdadır. Bu çoğu program Yaşam ve diğer CA kurallarında ilginç kalıpların bir geniş kütüphanesi ve Yaşamı içeren çoklu kuralları simule edebilmek için yeteneği, kalıpları düzenlemek ve simülasyon için grafik kullanıcı arabirimi içerir.

Dış bağlantılar[değiştir | kaynağı değiştir]

Birçok dış bağlantı the Open Directory Project'de Conway'in Hayat Oyunu dayanabilen Hayat Oyununu içerir. Ayrıca, Hayat Oyununun Haberleri birçok bireysel tarafından son gelişmeleri rapor ederek bir web günlüğü olur.

Bazı ek bağlantılar: