Bilgisayar ve Yazılım

Turing Makinesi ve Bilgisayarların Çözmesi İmkansız 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. Aslında bu sınırları teknolojik gelişmeler ya da mevcut bilgi birikimimiz belirlemiyor. Sorun direkt olarak kendileri ile alakalı. 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 kurtulmak için bir öneri sunar. Aslında amacı matematik için sağlam temeller oluşturmaktır. Bu öneriler matematik yaparken uygulanacak yöntemlerle ilgilidir. Sonunda bir uzlaşı sağlamış olsa da matematiğin özüne yöneltilmiş soruların da ortaya çıkmasına sebep olur.

Sorulardan biri her matematiksel problemin doğru/yanlış gibi bir sonuç verip veremeyeceğidir. Bunun üzerine Alan Turing 1936’da 24 yaşında modern bilgisayar kullanımına zemin hazırlayan bir makale yazdı. Makalesinde Turing “Bilgisayarların sınırları nelerdir?” sorusunu sormuştu. Ve bulduğu yanıt oldukça şaşırtıcıydı.

Bilgisayarların Yapabileceği Şeylerin Sınırı Nedir?

Alan Turing bu sorunun cevabını bulabilmek için sonsuz bir kağıt şerit üzerine yazılan sembolleri okuyan bir makine düşledi. Bu makine bir programa dayanarak sembolleri karıştırıp yerlerini değiştirebilecekti. Program sıfırlar ve birler halinde depolanacaktı. Devamında Turing şeridin kendi içinde de kurallar belirlenebileceğini fark etti. Bu tür bir aygıt her türlü matematiksel ve mantıksal işlem sırasının üstesinden gelebilirdi. Turing makinesine Evrensel Makine dedi. Bugün de Evrensel Turing Makinesi adıyla anılıyor. Bu Evrensel Turing Makinesi aslında düşünülebilecek en basit bilgisayardı.

İşin tuhafı, Turing bu zihin makinesini geliştirirken, bir bilgisa­yarın neler yapabileceğini değil neler yapamayacağını göstermeyi amaçlamıştı. Bir matematikçi olarak bilgisayarların nihai sınırına ilgi duyuyordu. Neyse ki, Turing’in hesaplanamaz bir problem bulma çabası uzun sürme­di.

Turing’in kuramsal aygıtı 5 yıl içinde hayata geçirildi ve Z3, Berlin’de 1941’de yapıldı. Alman hükumeti bilgisayarın askeri alandaki potansiyelini fark edemedi ama İngilizler aynı hataya düşmedi. Turing savaş esnasında şifrelerin kırılmasında büyük rol oynayan Colossus bilgisayarları ile çalışmaya başladı. https://en.wikipedia.org/wiki/Z3_(computer)

Halting – Durma Problemi

Alan Turing’in bir bilgisayar tarafından asla çözülemeyeceğini söylediği problemlerden birisi özgöndergeli olan ” Bu program duracak mı?” sorusudur. “Durma problemi” herhangi bir girdiyi işleyen herhangi bir bilgisayar programının eninde sorunda durup durmayacağını söyleyecek genel bir algoritma olup olmadığını sorar. Bir algoritmayı uygulayacak bir Turing makinesi kurduğunuzu ve girdiyi sonsuz uzunluktaki bandın üzerine yazıp makineye verdiğinizi düşünün. Verileri okuyup işlemeye başlayan makine bir süre sonra durup size cevabı verir mi? Yoksa sonsuza kadar çalışmaya devam mı eder?

1936’da Turing, bir programın sonunda du­racak mı yoksa sonsuzca çalışacak mı olduğunu bilmenin imkânsız olduğunu gösterdi. Hiçbir bilgisayar da bunu yapamazdı. Bu “Hesaplanamaz” bir şeydi. Gerçekten de çoğu problemin bilgisayarlarla hesaplanamayacağını biliyoruz. Neyse ki sözü geçen bu durma problemi, çözümleri için bilgi­sayarları kullandığımız türde problemlerin bir örneği değildir. Bu yüzden Turing’in bilgisayarlarla ilgili olarak getirdiği sınır teknolojik bakımdan geri kalmamıza neden olmamıştır.

Turing’in bu keşfinden beş yıl önce mantıkçı Kurt Gödel tarafından matematik alanında da benzer bir sonuç elde edilmişti. Gödel’in eksiklik teoremi matematik tarihinin en önemli sonuçlarından biridir. Tıpkı çoğu bilgisayar problemin hesaplanamaz olması gibi matematiksel önermelerin de çoğunlukla karar verilemez olduğu ortaya çıkmıştı. Bilgisayarlar şaşırtıcı bir şekilde saf matematiğin soyut dünyasında doğmuş olan, hayal gücünün ürünü makinelerdir. İkisinin de sınırları vardır. ­Neyse ki bu sınırlandırmalar ne bilgisayarların ne de matematikçilerin ilerleyişini durduramadı.

Kaynaklar ve İleri Okumalar:

Matematiksel

Sibel Çağlar

Yola Kadıköy Anadolu Lisesi ile başladım. Ardından gelen tesadüfler, zamanında pek de sevmediğim, matematik ile yolumu kesiştirdi. Sonucunda Marmara Üniversitesinde İng. Matematik öğretmenliğinden mezun oldum. Zaman akıp gitti; bu süreçte ben de çeşitli özel eğitim kurumlarında matematik öğretmenliği ve eğitim koordinatörlüğü yaptım. Bu esnada da bol bol matematik ile ilgili serzenişlere şahit oldum. Ne yapmalı diye düşünürken, aklıma bu site fikri geldi. 2015 yılında matematiksel.org web sitesini kurdum. Amacım bilime ve özelinde matematiğe ilgiliyi arttırmaktı. Matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarının da dahil olması ile kocaman bir aile olduk. Yolumuz uzun ama kesinlikle çok keyifli.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

Başa dön tuşu