Anasayfa/BİLİŞİM/Bilgisayarların Çözmesi İmkansız Problem: Durma Problemi
Günümüzde bilgisayarların hayatımızın ne kadar içine girdiğinden dem vurmaya gerek yok sanırım. Her an basit ya da karmaşık bir bilgisayarla etkileşim içindeyiz. Neredeyse her sorunumuza hızlı ve etkili çözüm sağlayan bu cihazları o kadar kanıksadık ki bazen çözemeyecekleri bir problem olamayacağına bile inanıyoruz. Fakat elbette onların da güçlerinin bir sınırı var ve sandığımızın aksine bu sınırları teknolojik gelişmeler ya da mevcut bilgi birikimimiz değil direkt olarak temel matematiksel gerçekler belirliyor. Gelin bunlardan biri olan “Durma Problemi (Halting Problem)”ne yakından bakalım.
Öncelikle böyle bir problemin nasıl ortaya çıktığına bir göz atalım. 20. yüzyılın başlarında dönemin ünlü matematikçilerinden David Hilbert, matematikte o zamana kadar uygulanmış yöntemlerin sistemsizliğinden meydana gelen paradokslardan ve tutarsızlıklardan kurtulmak için bir öneri sunar. Amacı matematik için sağlam temeller oluşturmaktır. Bu öneriler matematik yaparken uygulanacak yöntemlerle ilgili de bir uzlaşı sağlamış olsa da matematiğin özüne yöneltilmiş soruların da ortaya çıkmasına sebep olur. Ortaya çıkan sorulardan biri ve bizim bugünkü yazımızın temelini oluşturan, her matematiksel problemin doğru/yanlış gibi bir sonuç verip veremeyeceğidir. Buna karar verilebilirlik(decidability) denir.
Hilbert bu soruya yanıt olarak matematikte doğru yöntemler adım adım izlendiğinde her problemin bir sonuç vereceğini söylemiştir, yani matematiğin karar verilebilir bir yapısı olduğunu ima eder, hatta ünlü sözünde (There is no ignorabimus) “bilemeyiz” diye bir şey yoktur, der.
Hilbert’İn bu savı üzerine bilgisayar biliminin babası kabul edilen Alan Turing bir soru sorar: “Herhangi bir bilgisayar programına bakıp/inceleyip, onun verilen girdiyle çalıştığında durup durmayacağını söyleyecek bir program yazabilir miyiz?”
Bu soru ilk bakışta öyle görünmese de paradoksal sonuçlar üreten bir sorudur.
Şekil 1: D Makinesi
Şimdi Turing’in bahsettiği tarzda bir program inşa edelim. Programımızın adı “D” olsun. D’nin görevi bir başka programın çalışma şekline bakıp onun durup durmayacağını belirlemesi olacak (Şekil 1). Kontrol edilecek programımızın adı “K” olsun, daha önceden bahsettiğimiz gibi bir programın çalışması için girdiye ihtiyacı vardır ve şimdiki testimizde K için girdimize de “G” diyelim. D’nin amacı G girdisi ile çalışan K programı duracak mı yoksa sonsuz döngüye mi girecek diye kontrol etmek olacak (Şekil 2).
Şekil 2: K ve G girdileri ile D Makinesi
Şimdi gelin, bu D makinesini kullanarak yeni bir makine üretelim ve bunun adı D2 olsun. Bu yeni makinenin işlevi ise şekil 3’te de görüleceği gibi D makinesinin çıktısını alıp tam tersini çıktı olarak vermek. Yani eğer D mekinesi “Durur” diyorsa D2 makinesi “Durmaz” diyecek.
Şekil 3: D2 Makinesi
Sıra geldi meşhur “Durma Problemi”nin ortaya çıktığı aşamaya. Eğer “D2 makinesine D2 programı ve G girdisi verilirse sonuç ne olur?” diye sorarsak nasıl bir cevap alırız?
D2 makinesinin bir cevap verebilmesi için önce D makinesinin çalışıp bir sonuç vermesi lazım (hatırlarsanız D2 makinesi D makinesi ne sonuç verirse tersini verecekti). Kafa karışıklığına sebep olmamak için problemi adım adım inceleyelim:
D2 makinesine bir soru geldi. Ama o tek başına işlem yapamaz, vereceği cevap D makinesinin o soruya vereceği cevaba bağlı. Hemen arka planda D makinesine kendisine gelen girdileri yönlendirir.
D makinesine gelen soru: “D2 makinesi G girdisiyle nasıl bir sonuç verir?” D makinesi bu soruya 2 cevap verebilir: Durur veya Durmaz.
“Durur” derse, D2 makinesi bu cevabın tersini alarak “Durmaz” cevabını verecektir. Ama D makinesi “Durur” diyeceğini söylemişti! ÇELİŞKİ! (Şekil 4)
“Durmaz”derse, D2 makinesi bu cevabın tersini alarak “Durur”cevabını verecektir. Ama D makinesi “Durmaz” diyeceğini söylemişti! ÇELİŞKİ! (Şekil 5)
Peki, bu bizi nereye getirdi?
Başlangıçta Turing’in bahsetmiş olduğu “Her ne girdi verilirse verilsin muhakkak girilen programın durup durmayacağı ile ilgili doğru sonuç verecek bir program(makine) üretebilir miyiz?” sorusuna “Evet” diye cevap verdik ve ürettiğimiz makine, D2 makinesi girdi olarak verildiğinde tutarlı sonuçlar vermedi. Böylece Olmayana Ergi (Proof by Contradiction) ispat yöntemiyle böyle bir makinenin üretilemeyeceğini göstermiş olduk.
Böylece Hilbert’in “Uygun yöntemleri adım adım izleyerek çözemeyeceğimiz problem var mıdır?” sorusuna “Durma problemi çözülemez” diye de cevap verebilmiş oluyoruz.
Konu ile ilgili daha fazla animasyon ve şema bulabileceğiniz,kaynak olarak kullandığım birkaç YouTube videosunu ve konunun felsefi boyutunu tartışan ufak bir makaleyi kaynakça kısmında bulabilirsiniz.
Up and Atom/Why This Problem is IMPOSSIBLE for Computers to Solve (The Halting Problem): https://www.youtube.com/watch?v=t37GQgUPa6k
Computerphile/Turing & The Halting Problem – Computerphile: https://www.youtube.com/watch?v=macM_MtS_w4
Turing’in Makalesi: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf