Anasayfa » BİLİŞİM » Bilgisayarların Çözmesi İmkansız Problem: Durma Problemi

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.

Acaba öyle midir?

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:

  1. 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.
  2. D makinesine gelen soru: “D2 makinesi G girdisiyle nasıl bir sonuç verir?” D makinesi bu soruya 2 cevap verebilir: Durur veya Durmaz.
  3. 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)
  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)
Şekil 4
Ş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.

Kaynakça:

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

Yazıyı Hazırlayan: Rumeysa Aslıhan Ertürk

Avatar
Vefa Lisesi 143. dönem mezunu, İTÜ Bilgisayar Mühendisliği anadal, Fizik bölümü yandal öğrencisi. Küçük yaşlarda bilimin büyülü dünyası başını döndürmüş olacak ki tüm hayallerini onun peşinden koşmak üzerine kurdu. Cehaletin mutluluk olduğuna inanmadığı gibi bilmekten ve öğrendiklerini paylaşmaktan çok keyif alıyor. Okuyucusuna keyifli dakikalar dilerken kendilerinin olumlu veya olumsuz görüşlerini de dört gözle bekliyor.

Bunlara da Göz Atın

Joan Clarke: Alan Turing’in Gölgesindeki Kalan Bir Kadın

Bilindiği gibi “The Imitation Game” isimli film matematikçi Alan Turing’in hayat hikayesinden uyarlanmıştır. Turing, II.Dünya …

2 Yorumlar

  1. Avatar

    Rümeysa Hanım,

    Bunun üzerine kafa yormaya yönlendirdiğiniz için teşekkür ediyor emeğinize sağlık diyorum, dogmalar okyanusuna zorla batırılmaya çalışıldığımız bugünlerde yazınızı okumak ilaç gibi geldi; bana göre, sadece yaşadığımız toplumu değil insanlığı kurtaracak bilimdir; tabii kötü emellere bulaştırılmadığı sürece

    • Avatar
      Rumeysa Aslıhan Ertürk

      Göstermiş olduğunuz ilgi ve güzel yorumlarınız için biz teşekkür ederiz, Cihangir Bey.
      Görüşlerinize tamamıyla katıldığımı belirtmek isterim. Bilim kötü niyetli kullanıma açık olduğundan, bilim ve genel anlamda etiğin birbirinden ayrı düşünülmemesi gerektiğine inanıyorum.
      İyi çalışmalar.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.