Kulağa Kolay Gelen Bir Sorun Evrenimiz İçin Çok Büyük Sayılar Ortaya Çıkarıyor | Quanta Dergisi

5 yaşındaki çocukların bilgisayar biliminin sınırlarını zorlayan soruları kavraması pek sık görülen bir durum değil, ancak bu gerçekleşebilir. Örneğin, Alice adında bir anaokulu öğrencisinin iki elması olduğunu, ancak portakalları tercih ettiğini varsayalım. Neyse ki sınıf arkadaşları döviz kurlarının sıkı bir şekilde uygulandığı sağlıklı bir meyve ticareti sistemi geliştirdiler: Diyelim ki bir elmadan vazgeçerseniz bir muz alabilirsiniz. Alice, muz veya kavunu alıp boşaltarak en sevdiği meyveye ulaşmasını sağlayacak bir dizi işlemi gerçekleştirebilecek mi?

Kulağa yeterince basit geliyor. "İlkokula gidip bunu çocuklara anlatabilirsiniz" dedi Christoph HaaseOxford Üniversitesi'nde bilgisayar bilimcisi. “İnsanlar 'Bu kolay olmalı' diye düşünecek.”

Ancak Alice'in ikileminin altında yatan matematik problemi (vektör toplama sistemleri için ulaşılabilirlik problemi olarak adlandırılır) şaşırtıcı derecede inceliklidir. Bazı durumlar kolayca çözülebilirken, bilgisayar bilimcileri yaklaşık yarım yüzyıl boyunca soruna ilişkin kapsamlı bir anlayış geliştirmek için çabaladılar. Geçtiğimiz birkaç yıldaki bir dizi atılımla, bu sorunun tam olarak ne kadar karmaşık hale gelebileceğini kesin olarak ortaya koydular.

Bu çocuksu problemin absürt derecede, neredeyse karikatürize edilmiş bir şekilde karmaşık olduğu ortaya çıktı; o kadar karmaşık ki neredeyse diğer tüm problemler meşhur zor hesaplama problemleri çocuk oyuncağı gibi görünüyor. Bu sorunu çözmek için gereken çabayı ölçmeye çalışın; çok geçmeden o kadar büyük sayılarla karşılaşacaksınız ki, rakamlarını saymak bile daha önce hiç duymadığınız sayılara ulaşmanızı sağlayacaktır. Bu tür sayılar çoğu zaman evrenin ölçeğine ilişkin karşılaştırmalara davetiye çıkarır, ancak bu benzetmeler bile yetersiz kalır. "Bu adaleti sağlamaz" dedi Georg ZetzscheKaiserslautern, Almanya'daki Max Planck Yazılım Sistemleri Enstitüsü'nde bilgisayar bilimcisi. “Evren çok küçük.”

Yakın?

Ulaşılabilirlik sorunu, özüne indirgendiğinde, sıralı sayı listelerinden oluşan, vektör adı verilen matematiksel nesnelerle ilgilidir. Bu listelerdeki girişlere bileşenler adı verilir ve bir vektördeki bileşenlerin sayısına onun boyutluluğu denir. Örneğin Alice'in meyve envanteri dört boyutlu bir vektör (a, b, c, d), Bileşenleri herhangi bir zamanda kaç tane elma, muz, kavun ve portakal bulunduğunu temsil ediyor.

Bir vektör toplama sistemi veya VAS, bir sistemdeki durumlar arasındaki olası geçişleri temsil eden vektörlerin bir koleksiyonudur. Alice için geçiş vektörü (−1, −1, 1, 0), bir elma ve bir muzun bir kavunla değişimini temsil eder. VAS erişilebilirlik problemi, sizi belirli bir başlangıç ​​durumundan belirli bir hedef duruma götürebilecek izin verilen geçişlerin herhangi bir kombinasyonunun olup olmadığını veya matematiksel terimlerle ifade edersek, başlangıç ​​vektörünü hedef vektöre dönüştüren herhangi bir geçiş vektörleri toplamının olup olmadığını sorar. Tek bir sorun var: Sistemin durumunu tanımlayan vektörün hiçbir bileşeni sıfırın altına düşemez.

"Bu, bir gerçeklik modeli için çok doğal bir kısıtlamadır" dedi Wojciech CzerwińskiVarşova Üniversitesi'nde bilgisayar bilimcisi. “Negatif sayıda elmaya sahip olamazsınız.”

Bazı sistemlerde hedef vektörün ulaşılabilir olup olmadığını belirlemek kolaydır. Ancak durum her zaman böyle değildir. Bilgisayar bilimcileri en çok, ulaşılabilirliği belirlemenin ne kadar zor olduğunun açık olmadığı basit görünümlü vektör toplama sistemleriyle ilgileniyorlar. Bu vakaları incelemek için araştırmacılar, belirli bir sistemin boyutunu ölçen bir sayı tanımlayarak başlıyor. Bu sayı ile temsil edilir n, boyutların sayısını, geçişlerin sayısını ve diğer faktörleri kapsar. Daha sonra ulaşılabilirlik sorununun zorluğunun ne kadar hızlı artabileceğini soruyorlar. n daha da büyüyor.

Bu soruyu cevaplamak için araştırmacılar birbirini tamamlayan iki yaklaşım kullanıyor. İlk olarak, ulaşılabilirliğin belirlenmesinin minimum düzeyde çaba gerektirdiği, özellikle zorlu vektör toplama sistemlerinin örneklerini araştırıyorlar. Bu minimum seviyelere, problemin karmaşıklığına bağlı olarak "alt sınırlar" deniyor; araştırmacılara şöyle diyorlar: "Belirli bir durum için en zor sistemler. n en azından bu kadar zor.”

İkincisi, araştırmacılar “üst sınırlar”, yani en şeytani sistemlerde bile ulaşılabilirliğin ne kadar zor olabileceğine dair sınırlar oluşturmaya çalışıyor. Bunlar şöyle diyor: "Belirli bir durum için en zorlu örnekler n en fazla bu kadar zor.” En zorlu sistemlerde ulaşılabilirliğin ne kadar zor olduğunu tam olarak belirlemek için araştırmacılar, alt sınırları yukarı ve üst sınırları buluşana kadar aşağı itmeye çalışıyor.

Kabus Şeyleri

Vektör toplama sistemlerinin uzun bir geçmişi vardır. 1960'lı yıllardan bu yana, bilgisayar bilimcileri bunları, bir hesaplamayı birçok küçük parçaya bölen ve bu parçalar üzerinde aynı anda çalışan programları modellemek için kullandılar. Bu tür "eşzamanlı hesaplama" artık her yerde mevcut, ancak araştırmacılar hala bunun matematiksel temellerini tam olarak anlayamıyorlar.

1976 yılında bilgisayar bilimcisi Richard Lipton VAS erişilebilirlik sorununun karmaşıklığını anlama yolunda ilk adımı attı. Bir durumun diğerinden erişilebilir olup olmadığını belirlemenin en hızlı yolunun, bunlar arasındaki geçiş dizisini haritalandırmak olduğu sistemler oluşturmak için bir prosedür geliştirdi. Bu, ulaşılabilirlik probleminin zorluğunun bir ölçüsü olarak dikkatlice seçilmiş iki durum arasındaki en kısa yolun uzunluğunu kullanmasına olanak sağladı.

o zaman Lipton kanıtladı büyüklükte bir sistem inşa edebilirdi n burada iki durum arasındaki en kısa yol $latex 2^{2^n}$'den daha fazlasını içeriyordu. Bu, sistemlerinde erişilebilirliği belirlemek için gereken çabaya karşılık gelen çift üstel bir alt sınır anlamına geliyordu. Şaşırtıcı bir keşifti; çift üstel büyüme, bilgisayar bilimcilerinin kabuslarından biridir. Gerçekten de araştırmacılar, kıyaslandığında sönük kalan sıradan üstel büyüme karşısında bile genellikle tereddüt ediyor: $latex {2^5}= 32$, ancak $latex 2^{2^5}$ 4 milyarın üzerindedir.

Çoğu araştırmacı, Lipton'un mümkün olan en karmaşık vektör toplama sistemlerini hazırladığını, yani alt sınırı olabildiğince yükseğe çıkardığını düşünüyordu. Bu durumda eksik olan tek şey, bununla uyumlu bir üst sınır olacaktır; yani ulaşılabilirliği belirlemenin daha da zor olduğu bir sistemin olamayacağının kanıtı. Ama kimse bunu nasıl kanıtlayacağını bilmiyordu. Bilgisayar bilimcisi Ernst Mayr ona en yakın olanıydı. kanıtladı 1981'de prensip olarak herhangi bir vektör toplama sisteminde ulaşılabilirliği belirlemenin her zaman mümkün olduğunu ortaya çıkardı. Ancak onun kanıtı, sorunun ne kadar zor olabileceğine dair herhangi bir niceliksel üst sınır koymuyordu. Bir zemin vardı ama görünürde tavan yoktu.

Lipton, "Bunu kesinlikle ara sıra düşündüm" dedi. "Fakat bir süre sonra pes ettim ve bildiğim kadarıyla 40 yıl boyunca hiç kimse ilerleme kaydedemedi."

2015 yılında bilgisayar bilimcileri Jérôme Leroux ve Sylvain Schmitz nihayet kuruldu niceliksel bir üst sınır — o kadar yüksek ki araştırmacılar bunun Lipton'un alt sınırına ulaşmak için aşağı itilebilecek bir ilk adım olduğunu varsaydılar.

Ama olan bu değil. 2019'da araştırmacılar, Lipton'unkinden çok daha yüksek bir alt sınır keşfettiler ve bu, onlarca yıllık geleneksel düşünceyi altüst etti. VAS'a ulaşılabilirlik sorunu herkesin beklediğinden çok daha karmaşıktı.

Bir Güçler Kulesi

Şok edici 2019 sonucu başarısızlıktan doğdu. 2018'de Czerwiński, Leroux ve Filip MazowieckiŞu anda Varşova Üniversitesi'nde bir bilgisayar bilimcisi olan bu kişi, ilgili bir sorun üzerinde ilerleme kaydedilmesine yardımcı olabilirdi. Daha sonraki tartışmalarda araştırmacılar, ekstra karmaşık vektör toplama sistemleri oluşturmanın umut verici yeni bir yolunu buldular; bu, ilerlemenin çok uzun süredir durduğu VAS erişilebilirlik probleminde yeni bir alt sınıra işaret edebilir.

Czerwiński, "Aklımdaki her şey VAS'ın ulaşılabilirliğine bağlıydı" diye hatırladı. Ders yükünün hafif olduğu bir dönem boyunca Leroux, Mazowiecki ve diğer iki araştırmacıyla birlikte yalnızca bu soruna odaklanmaya karar verdi: Sławomir Lasota Varşova Üniversitesi'nden ve Ranko Lazić Warwick Üniversitesi'nden.

Birkaç ay sonra çabaları sonuç verdi. Czerwiński ve meslektaşları gösterdi iki durum arasındaki en kısa yolun, tetrasyon adı verilen ve kabus gibi çift üstel büyümeyi bile uysal hale getiren matematiksel bir işlemle sistemin boyutuyla ilişkilendirildiği vektör toplama sistemleri oluşturabileceklerini.

Tetrasyon, toplama işlemiyle başlayarak matematikteki en tanıdık işlemleri birbirine bağlayan bir modelin basit bir uzantısıdır. Birlikte ekle n bir sayının kopyaları ve sonuç bu sayının şu şekilde çarpılmasına eşdeğerdir: n. Birlikte çoğalırsanız n Üs alma işlemine eşdeğer olan veya sayıyı bir sayıya yükselten bir sayının kopyaları ngüç. Çoğunlukla yukarıyı gösteren bir çift okla temsil edilen tetrasyon, bu dizideki bir sonraki adımdır: Bir sayının şu şekilde tetrat edilmesi: n bunu üstelleştirmek anlamına gelir n bir güç kulesi üretme zamanı n büyük hikayeler.

Tetrasyonun ne kadar çabuk kontrolden çıktığını anlamak zor: $latex 2 uparrowuparrow 3$ veya $latex 2^{2^2}$, 16, $latex 2 uparrowuparrow 4$ 65,000'in biraz üzerinde ve $latex 2 uparrowuparrow 5$ yaklaşık 20,000 haneli bir sayıdır. $latex 2 uparrowuparrow 6$'ın tüm rakamlarını yazmak fiziksel olarak imkansızdır; bu kadar küçük bir evrende yaşamanın bir sorumluluğudur.

Çığır açan sonuçlarıyla Czerwiński ve meslektaşları, farklı boyutlarda vektör toplama sistemlerinin mevcut olduğunu kanıtladılar. n ulaşılabilirliği belirlemenin en iyi yolu $latex 2 uparrowuparrow n$ geçişten daha fazlasını içeren bir yolun haritasını çıkarmaktır; bu da Lipton'unkini gölgede bırakan yeni bir alt sınıra işaret eder. Ancak tetrasyon ne kadar baş döndürücü olsa da, sorunun karmaşıklığıyla ilgili son söz bu değildi.

Quinquagintillion'a ve Ötesine 

VAS'a ulaşılabilirliğin karmaşıklığına ilişkin şok edici yeni alt sınırdan yalnızca birkaç ay sonra Leroux ve Schmitz aşağı itti üç yıl önce belirledikleri üst sınırı, ancak tetrasyona kadar inemediler. Bunun yerine ulaşılabilirlik probleminin karmaşıklığının, Ackermann fonksiyonu adı verilen matematiksel bir canavardan daha hızlı büyüyemeyeceğini kanıtladılar.

Bu işlevi anlamak için tetratasyonu tanımlamak için kullanılan modeli korkunç sonucuna götürün. Sıradaki pentasyon adı verilen bir sonraki işlem, tekrarlanan tetratasyonu temsil eder; bunu tekrarlanan pentasyon için başka bir operasyon (heksasyon) takip eder ve bu böyle devam eder.

$latex A(n)$ ile gösterilen Ackermann işlevi, sayı doğrusundaki her durakta bu işlemler merdiveninde bir adım yukarı çıktığınızda elde ettiğiniz şeydir: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $lateks A(3) = 3^3$, $lateks A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, vb. $latex A(4)$'daki rakam sayısı, yaklaşık olarak 1 kentilyona eşit devasa bir sayıdır; bu, 1'in ardından gelen 153 sıfır için ilginç ve nadiren ihtiyaç duyulan isimdir. "5 yaşındaki Ackermann için endişelenmeyin" tavsiyesinde bulundu javier esparzaMünih Teknik Üniversitesi'nde bilgisayar bilimcisi.

Leroux ve Schmitz'in sonucu alt ve üst sınırlar arasında büyük bir boşluk bıraktı; VAS erişilebilirlik sorununun kesin karmaşıklığı aralığın her iki ucunda veya arada herhangi bir yerde bulunabilir. Czerwiński bu farkın devam etmesine izin vermek niyetinde değildi. "Bunun üzerinde çalışmaya devam ettik çünkü bunun hayatımızda yaptığımız en büyük şey olduğu açıktı" dedi.

Son atılım 2021'de gerçekleşti; Czerwiński, Łukasz Orlikowski adlı ikinci sınıf bir lisans öğrencisine danışmanlık yapıyordu. Kendisini hızlandırmak için Orlikowski'ye problemin basit bir versiyonunu atadı ve Orlikowski'nin çalışması, ikisinin genel erişilebilirlik sorununa da uygulanan yeni bir teknik geliştirmesine yardımcı oldu. Bu onlara izin verdi alt sınırı yükselt büyük ölçüde - Leroux ve Schmitz'in Ackermann üst sınırına kadar. Bağımsız olarak çalışan Leroux, eşdeğer bir sonuç yaklaşık aynı zamanda.

Sonunda araştırmacılar ulaşılabilirlik sorununun gerçek karmaşıklığını ortaya çıkardılar. Czerwiński, Orlikowski ve Leroux'nun alt sınırı, iki durum arasındaki en kısa yolun Ackermann fonksiyonuyla orantılı olarak büyüdüğü, giderek daha büyük vektör toplama sistemleri dizisinin olduğunu gösterdi. Leroux ve Schmitz'in üst sınırı, erişilebilirlik sorununun bundan daha karmaşık olamayacağını gösterdi; sorunu çözmek için şaşmaz pratik bir prosedür umut eden herkes için pek teselli değil. Bu, görünüşte basit hesaplama problemlerinin ne kadar incelikli olabileceğinin çarpıcı bir örneğidir.

Asla Bitmedi

Sorunun birçok çeşidi cevapsız kaldığı için araştırmacılar, karmaşıklığını tam olarak belirledikten sonra VAS erişilebilirlik sorununu incelemeye devam etti. Örneğin Ackermann üst ve alt sınırları, artırmanın farklı yolları arasında ayrım yapmaz n, vektörlerin boyutluluğunun arttırılması veya izin verilen geçişlerin sayısının arttırılması gibi.

Son zamanlarda Czerwiński ve meslektaşları Ilerleme kaydedildi Sabit boyutlu vektör toplama sistemlerinin varyantlarında karmaşıklığın ne kadar hızlı artabileceğini inceleyerek bu farklı etkileri birbirinden ayırmak. Ancak daha yapılacak çok şey var; vektör toplama sistemlerinin görselleştirilmesinin kolay olduğu üç boyutta bile ulaşılabilirlik sorununun tam karmaşıklığı bilinmiyor.

Mazowiecki, "Bir bakıma bu bizim için utanç verici" dedi.

Araştırmacılar, nispeten basit vakaların daha iyi anlaşılmasının, vektör toplama sistemlerinden daha ayrıntılı olan diğer hesaplama modellerini incelemek için yeni araçlar geliştirmelerine yardımcı olacağını umuyor. Şu anda bu daha ayrıntılı modeller hakkında neredeyse hiçbir şey bilmiyoruz.

Zetzsche, "Bunu hesaplanabilirliği anlamaya yönelik çok temel bir arayışın parçası olarak görüyorum" dedi.

Kuantum izleyicilerimize daha iyi hizmet verebilmek için bir dizi anket yürütüyor. Bizimkini al bilgisayar bilimi okuyucu anketi ve ücretsiz kazanmak için girileceksiniz Kuantum mal.