Donald Knuth, Claude Opus 4.6'nın çözülememiş bir kombinatorik problemi nasıl çözdüğünü makaleyle açıkladı
(www-cs-faculty.stanford.edu)Temel özet
- 'The Art of Computer Programming (TAOCP)' yazarı bilgisayar bilimci Donald Knuth, en yeni yapay zeka modeli 'Claude Opus 4.6'nın kendisinin haftalardır üzerinde çalıştığı çözülememiş bir kombinatorik problemi çözdüğünü duyurdu.
- Yönlü bir grafın Hamiltonyen çevrim ayrıştırmasını bulma probleminde Claude, 31 Python betiği çalıştırması ve kendi geri bildirim döngüsü üzerinden çalışan genelleştirilmiş bir algoritma yapısı keşfetti.
- Geçmişte üretken yapay zekanın sınırlarını işaret ederek kuşkucu olan Knuth, bu sonucu "otomatik tümdengelim ve yaratıcı problem çözmede çarpıcı bir ilerleme" olarak değerlendirdi ve yapay zekaya dair önceki görüşünü gözden geçireceğini ima etti.
Derinlemesine analiz
Çözülen problem: Hamiltonyen çevrim ayrıştırması (Hamiltonian Cycle Decomposition)
Knuth, TAOCP'nin bir sonraki cildini yazarken belirli bir yönlü graf (digraph) üzerindeki bir ayrıştırma problemini araştırıyordu. Köşeleri $0 \le i, j, k < m$ olan ve $m^3$ adet $ijk$ köşesi içeren bir grafta, her köşenin $i+jk$, $ij+k$, $ijk+$ yönlerine giden 3 yayı (arc) vardır; burada $i+ = (i+1) \bmod m$. Amaç, $m > 2$ olan tüm durumlar için bu yayları 3 adet yönlü $m^3$-çevrime ayıran genel bir çözüm (general decomposition) bulmaktı. Knuth, $m=3$ durumu için çözüm bulmuştu, ancak bunun ötesine genelleştirilebilecek bir formül çıkarmakta zorlanıyordu.
Uygulama ilkesi ve teknik arka plan: hibrit akıl yürütme ve otonom keşif döngüsü
Knuth'un meslektaşı Filip Stappers, bu problemi Anthropic'in en yeni hibrit akıl yürütme modeli 'Claude Opus 4.6'ya verdi. Bunu yaparken basit bir sorgunun ötesine geçip, agentic bir iş akışını zorlayan güçlü kısıtları prompt içinde tanımladı.
Claude hemen problemi matematiksel olarak yeniden tanımladı ve Python betikleri (exploreXX.py) yazarak hipotez test döngüsünü başlattı. Yaklaşık 1 saat boyunca brute force, fiber decomposition ve simulated annealing gibi çeşitli algoritmaları deneyerek 31 keşif yürüttü.
Problemi çözmedeki kritik kırılma noktası
Özellikle 25. keşifte Claude, "Simulated Annealing algoritması tekil çözümler bulabilir ancak genel bir matematiksel yapı (general construction) sunamaz; bu yüzden saf matematiksel bir yaklaşıma ihtiyaç var" diyerek kendi sınırını analiz etti ve keşif yönünü değiştirdi. Sonunda 31. keşifte, önceki aramaların yapısal örüntülerine dayanarak $m$ tek olduğunda çalışan doğru bir genelleştirilmiş yapı türetti. Knuth da bu sonuca dayanarak matematiksel kanıtı tamamladı ve buna 'Claude-benzeri ayrıştırmalar (Claude-like decompositions)' adını verdi.
Önemli kod ve veriler
Aşağıda Filip Stappers'ın Claude'a verdiği temel kısıtlar (prompt) ile Claude'un kaydettiği öz değerlendirme günlüklerinden bazı bölümler yer alıyor.
# 1. Claude'a verilen iş akışı kısıtları (döngü kontrolü ve belgeleme zorunluluğu)
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. Claude'un matematiksel problemi yeniden tanımlaması (ilk yaklaşım)
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. 25. keşiften sonra Claude'un öz değerlendirmesi (yön değişikliği)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
10 yorum
Ders kitabında adı geçen kişi, ders kitabına durmadan bir şeyler ekliyor....
(Katılıyorum)
Elbette, çünkü ders kitapları yazmak zaten onun işi (başını sallayarak)
Hahahaha, artık yapay zekâyla daha da ekleme yaparlar gibi görünüyor.
Demek ki TAOCP hâlâ geliyormuş.
Matematik problemlerini çözmek için yapay zekayı kullanma yöntemini olduğu gibi paylaşıp, bir de kendi geliştirdiği TeX ile makale yazmış.... aşırı havalı
Bu haber sayesinde TAOCP'yi ilk kez duydum; sanırım bir ara yavaş yavaş göz atmam gerekecek.
TAOCP’nin sonraki cildini yazıyormuş demek
Demek ki bu seriden daha fazlası gelecek gibi, vay be
Hâlâ hayatta mı?
Hâlâ düzeltme yapıyor...