Hakkında Künye

Sonlanma Problemi

Bilgisayarlar her şeyi yapabilir mi? Bir sokak ropörtajında bu soruyu sorsak, alacağımız yanıtların çoğunluğunun evet olacağını tahmin ediyorum. Fakat malesef, “evet” cevabını verenler yanılacaklar. Bilgisayarlar her şeyi yapamaz. Bilgisayar bilimiyle ilgilenen herkesin tanıdığı Alan Turing, bunu, 1936 yılında, “Sonlanma Problemi” adında, hiçbir algoritmanın çözemeyeceği bir problemi ortaya atarak ispatladı.

Öncelikle bu problemi ana hatlarıyla anlatalım.

İlk olarak, elimizde sadece aritmetik işlemleri yapabilen bir A makinesi olduğunu hayal edelim. Bu A makinesi, bir toplama, çıkarma, çarpma ya da bölme işlemini girdi olarak alsın, ve sonucu çıktı olarak versin.

 

4+6 →  [A] → 10
5 / 3 → [A] → 1

Şimdi de elimizde bir B makinesinin olduğunu hayal edelim. Bu B makinesi de, sadece yazdığımız bir kelimenin ingilizce karşılığını bize çıktı olarak verebilsin.

Kitap → [B] → Book
Bilgisayar → [B] → Computer

Evet, şu an elimizde iki tane işini son derece iyi yapan makine var. Peki, birinin işini diğerine yaptırmaya kalkarsak ne olur?

4 + 6 → [B] → ?
Kitap → [A] → ?

Makineler, bu sorulara cevap verecek şekilde yazılmadıkları için, işlemleri gerçekleştiremeyecekler, dolayısıyla süreç asla sonlanmayacaktır.

Buraya kadarki kısmı bütün okuyucular zaten ben söylemesem de tahmin edebilirlerdi. Zaten asıl olay da burdan sonra başlıyor.

Elimizde üçüncü bir S makinesi olduğunu düşünün. Bu makine, bizim için asıl problem olacak. S makinesi iki tane girdi alsın. İlk girdi, çözülmesi gereken bir problem, ikinci girdi ise, bir makinenin planı olsun. Çıktı olarak da, işlemin sonlanıp sonlanmayacağını söylesin.

(4+6, A) →  [S] → İşlem sonlanır.
(Kitap, A) →  [S]  → İşlem sonlanmaz.

Makinemizi bir program gibi düşünüp, psüdo koduna dökecek olursak:

			bool S(soru, makine)
			{
			if(makine sonlanır)
			  return true
			else
			  return false
			}

bu hale geliyor.

Böyle bir makine olamaz. Neden mi? İşte cevabı:

Farkındayım sürekli yeni yeni makineler çıkarıp duruyorum ama bu sefer gayet sıradan iki yeni makine tanıtacağım sizlere. Birisi, yıllardır bildiğimiz, emektar fotokopi makinemiz olacak. Bu fotokopi makinesine, makinelerin planlarını vereceğiz, karşılığında da o planların iki tane kopyasını alacağız. Ona F adını koyalım. İkinci makinemiz ise ne söylersek tersini yapsın. Adı da T makinesi olsun. Şekile dökecek olursak:

A → [F] → ( A, A )     B → [F]→ ( B, B )

İşlem sonlanır  → [T] → !!!!11!11!!1bir!1!    - makine sonsuz döngüye girer -
İşlem sonlanmaz  → [T] → :)     - makine işlemi sonlandırır -

Şimdi, bu iki makineyi ve S makinemizi birleştirip, adına da X diyelim.

            X           
[F] → [S] → [T]

Can alıcı noktaya geldik. Sizce X makinesine kendi planını verirsek ne olur? Gelin deneyip görelim.

X → [X] → ?

İlk adım:

([X]) → [F] →( [X], [X] ) → [S] → ? → [T]

Burada duralım. Çünkü hayali S makinemizin ne cevap vereceği hayati önem taşıyor.

İkinci adım:

Varsayım 1:
S makinesinin, işlem sonlanır dediğini varsayalım.

([X]) → [F] →( [X], [X] ) → [S] → İşlem sonlanır → [T] → !!!!111!!!11!1bir!1!

Ne oluyor? Yoksa makine yanıldı mı? X makinesine kendi girdisini verdiğimiz zaman işlemin sonlanacağını söylemişti. Fakat sonlanmadı.

Bir de öbür türlü deneyelim. Bu sefer hayali makinemiz işlemin sonlanmayacağını söylesin.

Varsayım 2:

([X]) → [F] →( [X], [X] ) → [S] → İşlem sonlanmaz → [T] → :)

Bu sefer de işlem sonlandı. Ama hani sonlanmaz demişti? Yine mi yanıldı?

Cevap evet, S makinemiz, iki seferde de yanıldı. İlk varsayımımızda makinenin işlemi sonlandıracağını söylemişken, işlem sonlanmadı. İkinci varsayımımızda ise işlemin sonlanmayacağını söylediği halde, işlem sonlandı. İki varsayımımız da yanlış olduğuna göre, S gibi bir makinenin olması mümkün değil. Az önce verdiğim psüdo kodu yerine bu sefer, makinenin aslında sahip olması gereken kodu yazıyorum. Sanırım bugüne kadar yazdığım en anlamsız kod bu. Daha beterlerini ileride yazmam diye umuyorum.

			bool sonlanir_mi(soru, program)
			{
			program(soru);
			return true;
			}

İşte, bilgisayarların da yapamayacağı şeyler olduğunu ispatladık. Fakat yine de unutmayın, biz bilgisayar mühendisleri için sınırı her zaman hayal gücümüz belirler.

Kaynakça:

Yağız Arkayın
- 5 -