3 Ocak 2019 Perşembe

Mu Puzzle

Douglas Hofstadter'in "Gödel,Escher,Bach" kitabında tanımladığı bir bulmaca türüdür. Bulmaca başlangıç stringini (MI) çeşitli kurallara göre yeniden düzenleyerek hedef (MU) stringe ulaştırmayı amaçlar.

Bulmacanın kuralları kısaca şu şekilde özetlenebilir;

Elimizde M, I, ve U karakterleri olsun, bu karakterleri aşağıdaki kurallalara göre düzenleyebiliriz:

1. Bulmaca MI stringi ile başlar,
2. I ile biten stringin sonuna U ekleyebilirsin,  MI > MIU
3. M'den sonra gelen stringi 2 kere yazabilirsin, MIU>MIUIU   yada  MI>MII
4. Ard arda gelen herhangi III karakterini U ile değiştirebilirsin , MIIII>MIU
5. Arda arda gelen herhangi UU karakterlerini silebilirsin, MUUU>MU

Şimdi bir kaç yolu deneyerek çözüme gitmeye çalışalım,
1.Dal;
MI > 2. kuralı uygulayalım MIU
MIU > için sadece 3. kural uygulanabilir MIUIU
MIUIU > yine sadece 3. kural uygulanabilir MIUIUIUIU
Bu şekilde 3. kural uygulanacağından dolayı String sonsuza kadar MIUIUIUIUIUIU....... şeklinde devam der, dolayısı ile 3. kuralı xIU dan sonra kullanmamak gerekir.

2.Dal;
İlk denememiz M den sonra sürekli IU şeklinde sonsuz döngüye hapsolmuştuk şimdi diğer yolları deneyelim
MI > 3. kuralı çalıştıralım MII
MII > 3. kuralı bir kez daha çalıştıralım MIIII
MIIII > 4. kuralı çalıştıralım MUI
MUI > 2. Kuralı çalıştıralım MUIU
MUIU > 3. Kuralı uygulayalım MUIUUIU
MUIUUIU > 5. kuralı uygulayalım MUIIU
MUIIU > 3. Kuralı uygulayalım MUIIUUIIU
MUIIUUIIU > 5. kuralı uygulayalım MUIIIIU
MUIIIIU > 4. kuralı uygulayalım MUIUU
MUIUU > 5. kuralı uygulayalım MUI
Böylece bu dalda uyguladığımız 3. adıma geri dönmüş oluyoruz ve o adımdan sonra sürekli aynı döngüye hapsaluyoruz.

Bu şekilde bulmacaya dair tüm ihtimaller denense bile eninde sonunda sonsuz döngüye girmiş oluyorsunuz? Aşağıdaki şekilde MU bulmacasının çözümü için çeşitli dallanmalar gösterilmiştir.
Mu bulmacasının ağaç diyagramı

Peki MU bulmacasını çözmeye çalışan bir bilgisayar programı yazabilir misiniz?

Hiç yorum yok:

Yorum Gönder