HİÇBİR ALGORİTMA BAZI DÖRT BOYUTLU ŞEKİLLERİ TANIYAMAZ

Bazı soruların tarifi yoktur. Henüz kimse bulamadığı için değil, hiçbir algoritmanın — ne kadar uzun olursa olsun, herhangi bir bilgisayarda çalıştırılan hiçbir adım adım prosedürün — onları her seferinde doğru cevaplayamayacağı kanıtlandığı için. Austin’deki Texas Üniversitesi’nden Cameron McA. Gordon, dört boyutlu şekiller hakkında bu türden iki soru daha ekliyor.

Bu aynı şekil mi?

Matematikçiler bu şekillere 4-manifold der: yakından bakıldığında her yerde sıradan dört boyutlu uzay gibi görünen uzaylar. Onları bir bilgisayara verebilmek için makale, şekillerin birbirine yapıştırılmış düz parçalardan kurulduğunu varsayıyor (“parçalı doğrusal”, İngilizcesiyle piecewise linear ya da PL); böylece her biri sonlu bir veri listesiyle tanımlanabiliyor. Temel soru o zaman şu: böyle iki şekil verildiğinde, bunlar sürekli deformasyona kadar aynı mıdır?

1958’de A. A. Markov bu sorunun bir algoritması olmadığını gösterdi. Markov’un kanıtı şekil problemini gruplarla ilgili bir probleme dönüştürür: sonlu sayıda kuralla tanımlanan öyle gruplar vardır ki, elemanlarının verilen bir bileşiminin birim elemana eşit olup olmadığına hiçbir algoritma karar veremez — “kelime problemi” (word problem). Böyle bir gruptan, bir algoritmanın ancak o imkânsız problemi çözerek birbirinden ayırt edebileceği şekiller kurulabilir.

Yediye geri sayım

Markov’un argümanı zorluğu belirli şekillere bile sabitler. Sıradan bir topun yüzeyi olan S²’yi alın ve dört boyutlu bir şekil olan S² × S² çarpımını oluşturun. Bunun k kopyasını birbirine yapıştırın (#k diye yazılan bir “bağlantılı toplam”, connected sum). Bazı k değerleri için, verilen bir şeklin #k(S² × S²) olup olmadığına hiçbir algoritma karar veremez. Hangi k?

Makale geri sayımın izini sürüyor. Borisov’un 1969’da bulduğu, kelime problemi çözülemeyen ve 12 kurallı bir grup 14 kopya verdi. Gordon bunu 2022’de 12’ye indirdi. M. Tancer, Freedman’ın dört boyutlu şekiller sınıflandırmasından geçen yeni bir yol buldu ve şekillerin düz parçalardan kurulmasının gerekmediği “topolojik” versiyonda 9’a ulaştı. Bu çalışmanın daha önceki bir versiyonu 8’e ulaşmıştı. Ardından Kegel, Li ve Ren çok daha küçük bir çözülemez grup kurdu — 3 üreteç ve 9 kural — ve topolojik versiyonda 7’ye, düz parçalı versiyonda ise 9’a ulaştı.

Gordon, Tancer’ın yolunu düz parçalardan kurulan şekiller için de işler hale getiriyor ve şunu kanıtlıyor:

Verilen bir 4-manifoldun, parça parça, 7 tane S² × S² kopyasının bağlantılı toplamıyla aynı olup olmadığına karar veren hiçbir algoritma yoktur.

Kanıtın özü bir sözlüktür. Kegel, Li ve Ren’in grubundaki her w kelimesi için Gordon dört boyutlu bir şekil kurar. w birim elemana eşitse, kurallar üzerinde izin verilen bir hamleler dizisi — şekli değiştirmeden betimlemeyi yeniden yazan Andrews-Curtis hamleleri — şeklin tam olarak yedi S² × S² kopyası olduğunu gösterir. Eşit değilse, şekil bir noktaya büzülemeyen ilmekler içerir — yedi S² × S² kopyasında bu asla olmaz — dolayısıyla şekil o yedi kopya olamaz. Dolayısıyla #7(S² × S²)’yi tanıyan bir algoritma kelime problemini çözerdi; bu ise imkânsızdır.

Düğümlü küreler

İkinci soru düğümlerle ilgili. Sıradan bir düğüm, üç boyutlu uzayda düğümlenmiş bir çemberdir ve bir düğümün çözülüp çözülemeyeceğine karar vermek mümkündür: Haken’e ait bir algoritma vardır. Bir boyut yukarıda, iki boyutlu bir küre dört boyutlu uzayın içinde düğümlenebilir. Daha yüksek boyutlarda, buna karşılık gelen problemin algoritması olmadığı biliniyor. Dört boyutlu küre S⁴ içindeki iki boyutlu küreler içinse kimse bilmiyor.

Gordon, #7(S² × S²) içinde, iki boyutlu bir kürenin — ya da yönlendirilebilir olsun olmasın herhangi bir yüzeyin — düğümsüz olup olmadığına karar veren hiçbir algoritma olmadığını kanıtlıyor. Bu arada makale, o şeklin içinde, çevresindeki uzayın grubu çözülemez kelime problemine sahip olan bir küre ve 12 S² × S² kopyasında, grubu bir bilgisayarla tanımlanabilen her grubun bir kopyasını içeren bir küre kuruyor.

Ödül: sıfır kopya

Makale hedefi açıkça ortaya koyuyor: kopya sayısını sıfıra indirmek. Sıfır kopya, dört boyutlu kürenin, S⁴’ün kendisi demektir. Beş ve daha fazla boyutta hiçbir algoritma küreyi tanıyamaz; iki ve üç boyutta ise tanıyabilir. Dört boyut açık kalıyor — S⁴ içindeki düğümlü kürelerin saptanıp saptanamayacağı sorusu da öyle. Çıkarılan her kopya iki soruyu da yakınlaştırıyor.