Wolfram Araştırma şirketi her yıl, "Yeni Bilim Türü" alanında ilerleme ve fikir alışverişinde bulunmak için bir yaz okulu (Wolfram Yaz Okulu) düzenler. Bu etkinlik 13 yıldır düzenleniyor ve her yıl dahil olan içeriklerden biri "karmaşıklığın" kendisidir - karmaşıklık nedir? Karmaşıklığın bir sınırı var mı?
Stephen Wolfram Fotoğraf
Bu soruyu cevaplamak için 2002'de Wolfram, araştırmasını resmetmek için bin sayfadan fazla muhteşem bir çalışma yayınladı - "Yeni Bir Bilim Türü" (Çince: yeni bir bilim). Bu kitabın "doruk noktası", "Hesaplamalı Eşdeğerlik İlkesi" nin son bölümünde yatıyor.
Zuckerberg'in masasında "Yeni Bir Bilim Türü"
Hesaplamalı Eşdeğerlik İlkesi Basitçe söylemek gerekirse, daha karmaşık görünen herhangi bir sistem (akışkan, sosyal sistem, karınca kolonisi vb.) Karmaşıklıkları aynı , Ve ikisi Karmaşıklığın sınırına ulaşıldı - Karmaşıklıkları, beyin gibi evrendeki diğer son derece karmaşık sistemlerle aynıdır. Dahası, bu ilke hesaplama perspektifinden "insanlar evreni anlayabilir mi" sorusuna yanıt veriyor gibi görünüyor.
Bu büyük ilkeyi ve "karmaşıklık" ilkesini anlamak için, en basit sistem hücresel otomatından başlamamız gerekir.
1940'larda von Neumann kendi kendini kopyalayıcılar üzerinde çalışırken "hücresel otomata" kavramını önerdi. Hücresel otomata, belirli kurallara göre gelişen ayrı bir sistemdir. Wolfram, aşağıdaki şekilde gösterildiği gibi en basit hücresel otomatlardan birini kabul eder, biz buna "Elementary Cellular Automata" (Elementary Cellular Automata, ECA) diyoruz.
Şekil 2: Temel hücresel otomata No. 30.
Temel hücresel otomat, tek boyutlu uzayda ayrı ayrı gelişen bir sistemdir.Yatay eksen uzay, dikey eksen ise zamandır. Belirli bir başlangıç durumundan (ilk satır) sonra, sistem alt kurala göre (altıncı kurala göre) gelişir: (siyah 1, beyaz 0'dır). İlk satırdaki siyah karenin aşağıda olduğu bilinebilir Evrimin bir adımında, o da siyahtır. Yukarıdaki resim tamamen bu sekiz basit kuraldan geliştirilmiştir. Buradaki sözde "30" da kurallardan elde edilir. Sekiz kuralı 01 dizgesini elde etmek için düzenlemek, ona 000111110 ikili sayı gibi davranmak, o zaman hesaplaması kolaydır. 0'dan 255'e kadar her sayı bir kurala karşılık gelir ve gelecekte bu gösterimi her zaman kullanacağız.
128 adım gibi evrimsel adımların sayısını uzatırsak, davranışının son derece karmaşık hale geldiğini görebiliriz:
Şekil 3: 128 aşamalı evrimden sonra uzay-zaman diyagramı
Diğer birçok kuralı deneyebilir ve davranışının çok zengin olduğunu görebiliriz:
Şekil 4: Altı farklı temel hücresel otomata, davranışları çok farklı, kaotik, düzenli ve fraktaldir ve çok zengin bir davranış gösterir.
Burada gösterilen sistemler son derece basit kurallara dayanmaktadır, ancak çok zengin davranışlar üretebilirler. Hatta bazı sistemler rasgele sayı üreteçleri olarak da kullanılabilir. Yukarıdaki gerçekler bize "karmaşıklığın" son derece basit kurallardan ortaya çıkabileceği konusunda ilk ilhamı veriyor. Daha sonra, "karmaşık davranışların doğada neden bu kadar yaygın olduğunu" niteliksel olarak açıklayabiliriz - herhangi bir kural ve dinamik mekanizma bunları içerdiği sürece Basit kurallar Daha sonra karmaşık davranışlar üretme potansiyeline sahiptir. Ancak yukarıdaki kuralların basitliğinden dolayı daha karmaşık kurallara sahip birçok sistem kolaylıkla dahil edilebilir.
Ancak, bu bir soruyu gündeme getiriyor: karmaşıklık nasıl ölçülür? Karmaşıklığın sınırı nerede?
Bu soruyu cevaplamak için en doğal başlangıç noktası karmaşıklığı aramaktır. aynısı sistemi. Hesaplama açısından, "A ve B aynı karmaşıklığa sahiptir", "A, B'yi simüle edebilir" ve "B, A'yı da simüle edebilir" şeklindedir. Bu sorunun bir kısmıyla başlıyoruz: Sistem A, Sistem B'yi simüle eder.
Wolfram'ın kitabında, bu türden çok sayıda ilişkiyi sıraladı: Hücresel otomata, diğer çeşitli sistemlerin davranışına eşdeğer olabilir. Sayısal devrelerden sayı teorisine, mantıksal cebire ve ardından genel Turing makinesine kadar tüm hesaplanabilir sistemleri simüle edebilen bir sistem.
En basit örnek, kural 132'dir. :
Kural 132'nin Gelişimi
Kural 132 için Kural Diyagramı
Bu sistem aşağıdaki hesaplamaları tamamlamıştır:
N çift ise 0 döndür; n tekse 1 döndür
Burada n, ilk satırdaki siyah karelerin sayısıdır. Pek çok kez evrim geçirdikten sonra, f (n) elde edilir.
Cebirsel işlemler için, hücresel otomata açıkça daha fazlasını yapabilir.
N'nin karesini hesaplayabilir:
Aşağıdaki hücresel otomata kuralları yukarıdakinden biraz daha karmaşıktır.
Bu hücresel otomat n'nin karesini hesaplayabilir
Benzer şekilde, ilk satırdaki siyah karelerin ilk sayısı göz önüne alındığında, sistem kararlı hale geldikten sonra siyah karelerin sayısıdır. Yani, eşdeğerdir:
Hücresel otomata asal sayıları bulmak için bile kullanılabilir:
Her beyaz çizgi bir asal sayıya karşılık gelir
Soldaki her beyaz çizgi bir asal sayıya karşılık gelir. Başka bir deyişle, bu hücresel otomat, çalışmaya eşdeğerdir:
"Her yerde bulunan denkliği" tartışacağımız için, sadece cebir ve sayı teorisi işlemleri yeterli olmaktan uzaktır.
Temel mantıksal işlemler:
Basit kurallara sahip hücresel otomatik veriler, AND, OR ve kendisi tarafından oluşturulan çeşitli işlemleri destekleyebilir:
Temel mantıksal işlemler
Gördüğünüz gibi, aşağıdaki kurallar listesi eskisinden çok daha uzun. Aynı zamanda, temel hücresel otomatadaki 146 ve 190 numaralı kurallar mantıksal işlemleri gerçekleştirebilir:
Yukarıdaki hücresel otomatlar, basitlik ve karmaşıklık - cebir, sayı teorisi ve mantıksal işlemler, kuralların oluşturulabileceğinden çok daha karmaşık davranışlar arasındaki köprülerden biridir.
Yukarıdaki örneklerden, insanlar doğal olarak başka herhangi bir sistemi simüle edebilecek son derece basit kurallara sahip bir sistemin olup olmadığını düşünüyor?
İlk fikir, tüm temel hücresel otomatları simüle etmek için daha karmaşık hücresel otomat kullanmaktı. Gerçekler bunun mümkün olduğunu gösteriyor, ancak kurallar son derece karmaşık. Buradaki kuralları detaylandırmayacağım, sadece kısaca tanıtacağım:
Sırasıyla No. 254, No. 90 ve No. 30 olan yukarıdaki şekilde gösterildiği gibi, başlangıç değerini, yani hücre renklerinin ilk sırasının sırasını ayarlayarak tüm temel hücresel otomatayı simüle edebilir.
Bununla birlikte, "zanaatkarlar" tarafından yapılan bu tür genel bir arama teoriye pek yardımcı olmaz - birçok eşdeğer sistem bulmaktan başka bir şey değildir. Bununla birlikte, sonraki bir atılım doğrudan "hesaplamalı eşdeğerlik ilkesinin" doğmasına yol açtı.
2000 yılında Wolframın asistanlarından Matthew Cook, temel hücresel otomatların Kural 110 Turing tamamlandı .
Genel amaçlı bir bilgisayara eşdeğer olan Hücresel Otomata No. 110'un evrim diyagramı
110 numaralı hücresel otomata kural grafiği
Bu, yukarıdaki şekilde gösterilen hücresel otomattır. Benzer şekilde, sekiz parametre kullanılarak belirlenen basit bir kural.
Bu araştırmanın önemini açıklamak için, "Universal Turing Machine" (UTM) nedir ve "Turing Complete" nedir kısaca açıklamamız gerekiyor. Sezgisel bir hayal gücü, Evrensel Turing Makinesi'nin (UTM) soyut bir bilgisayar olmasıdır. Yalnızca bilgisayarları tanımlamak için kullanılır Yeteneği hesapla Soyut bir model. Başka bir açıdan, Turing makineleri bir bilgisayarda gerçekleştirilebilen hesaplamaları gerçekleştirebilir. Turing makinesi, şu anda elde edilebilen bilgi işlem sistemleri (aynı zamanda Turing makineleri olan kuantum bilgisayarlar dahil) arasında en güçlü hesaplama kapasitesine sahip sistemdir. Sözde "Turing bütünlüğü" basitçe genel bir Turing makinesine eşdeğer bir sistemdir.
Böylece, kural 110 Turing tamamlandı, en basitinden en karmaşığına kadar herhangi bir programı çalıştırabilir. Ve en karmaşık programları çalıştırabildiği için, sistemin kendisinin karmaşıklık sınırına ulaştığı düşünülebilir mi? Wolfram'ın cevabı: "Evet, UTM karmaşıklığın sınırıdır ve ulaşılması kolaydır."
Dikkat edilmesi gereken bir diğer husus, kural 110'un kendisinin çok basit olmasıdır - bu, biraz daha karmaşık olan diğer kurallara sahip sistemler için, kuralların kendilerinin zaten hücresel otomat 110'u içermesi muhtemel olduğu anlamına gelir. Bu, çok sayıda sistemin genel amaçlı Turing makineleri olduğu ve karmaşıklıklarının aynı olduğu ve hepsinin hesaplama karmaşıklığının sınırında olduğu anlamına gelir.
Öyleyse soru şu ki, bir sistem diğer sistemlerin davranışını kolayca içerebilir mi? Yakın zamanda yapılan bir araştırma, gözlem sisteminin ölçeğini kademeli olarak artırdığımızda (gerçek uzay yeniden normalleştirme), gittikçe daha fazla sistemin birbirini veya tek yönlü simülasyonu simüle edebileceğini buldu.
Sıradan hücresel otomata, tek bir hücreyi bir birim olarak alır, yani 0 veya 1. Ancak yeniden normalleştirme fikrini ortaya atarsak, iki veya üç hücreyi bir birim olarak kullanacağız, örneğin, tanımlarız:
Şu anda, başlangıç değeri {..., 0,1,0, ...} yerine yalnızca {1,1} ve {0,0} düzenlemesidir. Bu sürece "derleme" diyoruz ve bu dönüşümün kuralı "derleyici" dir. Şu anda, Hücresel Otomata No. 94'ün Hücresel Otomata No. 90'ın davranışını sergileyebileceğini bulduk:
Bu, kural 94'ün kural 90'ın davranışını içerdiği anlamına gelir. Burada iki hücreyi tek bir birimde birleştiriyoruz.Peki ya "bire üç değişiklik" veya "bire dört değişiklik" ise? Araştırmalar, bu sayı arttıkça birbirini simüle edebilecek daha fazla sistem olduğunu buldu:
Yukarıdaki şekilde, yatay eksen derleyicinin boyutu, dikey eksen ise birbirini simüle edebilen sistemlerin sayısı, yani oluşum sıklığıdır. Farklı renk çizgileri, farklı hücresel otomata ailelerini temsil eder. Bu şekil, derleyicinin boyutu arttıkça, bir tarafın sistemler arasında diğer yaklaşımları (1) veya 1'e çok yakın bir değeri simüle etme olasılığının olduğunu göstermektedir.
Bu sonuç çok önemli! Bu, doğada sistemler arasında simülasyonun da çok yaygın olduğu anlamına gelir.
Öyleyse önceki paragrafa geri dönelim:
Dikkat edilmesi gereken bir diğer husus, kural 110'un kendisinin çok basit olmasıdır - bu, biraz daha karmaşık olan diğer kurallara sahip sistemler için, kuralların kendilerinin zaten hücresel otomat 110'u içermesi muhtemel olduğu anlamına gelir. Bu, çok sayıda sistemin genel amaçlı Turing makineleri olduğu ve karmaşıklıklarının aynı olduğu ve hepsinin hesaplama karmaşıklığının sınırında olduğu anlamına gelir.
Şimdi, bir varsayım daha olduğu sürece, hesaplamalı eşdeğerlik ilkesi elde edilebilir:
Pek çok insan bu cümlenin çok fazla olduğunu düşünebilir, çünkü dünyayı görmek için sadece farklı bir perspektif gibi görünüyor. Ancak bu varsayımın güçlü bir gerekliliği ifade ettiği unutulmamalıdır: evrendeki tüm davranışlar, fenomenler ve değerler Hesaplanabilir, Turing makinesinde bir program çalıştırılarak elde edilebilir.
Bu varsayımın gerekliliğini göstermek için bir örnek verin:
2015 yılında yapılan bir araştırma, iki boyutlu Sınırsız Kafes malzemelerinin enerji açığı hesaplanamaz.
Bununla birlikte, şu anki anlayışımıza göre, evrende sonsuz bir nesne yoktur ve bu çalışma aynı zamanda herhangi bir sonlu iki boyutlu kafesin enerji boşluğunun hesaplanabilir olduğunu da kanıtlamıştır. Hiçbir gerçek fiziksel sistemin hesaplanamaz olduğu kanıtlanmamıştır.
"Evren bir bilgisayar" varsayımı ile "hesaplamalı eşdeğerlik ilkesini" öne sürebiliriz. Wolfram'ın ifadesi:
O kadar basit görünmeyen neredeyse tüm süreçler aynı karmaşıklığa sahiptir. (Açıkça basit olmayan neredeyse tüm süreçler, eşdeğer karmaşıklığın hesaplamaları olarak görülebilir.)
Dahası, "karmaşıklığın sınırına ulaşmak kolaydır." Kurallar biraz daha zengin olduğu sürece, sistem evrendeki en karmaşık davranışı - genel Turing makinesinin çeşitli davranışlarını gösterecektir. Bu, evrende bu kadar çok ve bu kadar zengin karmaşık davranışları görebilmemizin temel nedeninin, dinamik mekanizmalarının Turing'in en basitinden en çoğuna her şeyi kapsayan eksiksiz hesaplamalarını desteklemesi olduğu anlamına gelir. Tüm karmaşık davranışlar.
Hesaplamalı eşdeğerlik ilkesine dayanan bir başka çıkarım, "insanların evreni anlayabileceği" veya evreni aşamalı olarak anlayabileceği şeklindedir. "Anlayışı" hesaplama perspektifinden tanımlarsak, şu çıkarımı elde edebiliriz: A'yı "anlayış" B'yi tanımlarız, bu da A'nın beyinde veya kendi sistemlerinden bazılarında somut veya soyut olarak yeniden üretilebileceği anlamına gelir. B. Yani, A, B'yi simüle edebilir ve A, B'yi çalıştırabilir.
"Fiziksel bir yasayı anlıyorum" diyoruz. En temel şey, beyindeki belirli bir kuralı fiziksel imgeler ve formüllerle tanımlayabilmektir.
Hesaplamalı eşdeğerlik ilkesi yanlışsa, görece basit bir beyin görece karmaşık evreni nasıl anlayabilir? Hesaplamalı eşdeğerlik ilkesini kabul edersek, beynin karmaşıklığının evreninkiyle aynı olduğunu ve tek sınırlamanın kapasite olduğunu söyleyebiliriz, ancak yine de anlayışını genişletmek için bilgisayarları kullanabiliriz.
Wolfram bir keresinde Nutshell ile yaptığı röportajda şöyle demişti: "Evrenin özü hesaplamadır." Korkarım derin anlamı bunda yatıyor.
1: Wolfram Yaz Okulu;
2: Neumann, J. V. (1966) Kendi Kendini Üreyen Otomata Teorisi (A. W. Burks, Ed.) Champaign, IL, ABD: Illinois Üniversitesi Yayınları.
3: Tomassini, M., Sipper, M., ve Perrenoud, M. (2000). İki boyutlu hücresel otomata ile yüksek kaliteli rastgele sayıların oluşturulması üzerine. Bilgisayarlarda IEEE İşlemleri, 49 (10), 11461151 .
4: Hesaplanabilir bir sistemi ifade eder;
5: Cook, M. (2004) Elementer hücresel otomatada evrensellik Kompleks Sistemler, 15 (1), 1-40.
6: Jürgen Riedel ve Hector Zenil. (N.d.) Emülasyon Ağlarından Hücresel Otomata'nın Sınır Ötesi Davranışsal Yeniden Programlanabilirliği.
7: Undecidability of the Spectral Gap (tam sürüm), popüler bilim baskısına bakın: Çözülemeyen fizik problemleri, matematiğin çekirdeğinden gelen paradokslar
8: Stephen Wolfram: Evrenin özü hesaplamadır