entscheidungsproblem

• alm. benim bir p tezim var, şimdiye kadar bu p tezinin yanlış oldugu gösterilemedi lakin doğru oldugu da ispatlanamadı. bir algoritma bulsak, öyle ki, bu algoritma p'ye baksa, yazsa, çizse "evet, sizin teziniz ispatlanabilirdir." ya da "olmamış. otur sıfır" dese ne güzel olurdu. ve fakat bu mümkün müdür?
  
  leibniz'den miras, hilbert tarafından resmileştirilmiş bu soruya cevap 1936'da turing ve church tarafından farklı yöntemlerle, en azından sayılar teorisi için, "yoktur." olarak gelmiş, hilbert "hiç mi yok" diyince kavga çıkmıştır.
  
  (bkz: evrensel turing makinası)
• türkçesi karar verme problemi olabilir.
• daha düzgün bir dille "iyi tanımlanmış bir formal sistemde verilmiş yine iyi tanımlanmış bir problemin çözümü olup olmadığını belirlemek için bir yöntem var mıdır?" şeklinde de ifade edilebilir.
  (bkz: iyi tanımlanmış)
• ingilizce'si decision problem'dir. ayrıca şurdan yakmakta da fayda var.
  
  (bkz: sembolik mantık)
• hilbert'in ortaya attığı soru, kabaca şöyle bişey "tüm matematik problemlerini çözümlemek için sonlu sayıda adım içeren algoritmik bir yöntem var mıdır?". birbirine eşdeğer iki farklı çözümü vardır. (bkz: alan turing), (bkz: alonzo church)
• çözümü halting problem i doğuran soru.
• (bkz: düşünce deneyi/#92649934)
• türkçeye "sonlanma problemi" olarak tercüme edilebilecek olan matematik ve bilgisayar bilimi problemidir. en basit tanımı ile bilgisayar programlarının durup durmayacağının gayrikabilitahmin oluşunu, bunu belirleme görevi atanabilecek türde bir program yazılamayacağını ele alır. (burada sözü edilen genel bir algoritmadır)
  
  ilk bakışta bu sorun üzerinde düşünmeye dahi değmeyecek lüzumsuz bir mevzu gibi gelebilir, lakin öyle değildir. entscheidungsproblem için üç soru önem arz eder:
  
  1) böyle bir program yazılabilseydi matematik ve bilgisayar dünyasında ne olurdu?
  2) böyle bir program neden yazılamaz?
  3) matematiğin soyut dünyası dışında bu problem bize tam olarak neyi ifade eder?
  
  birinci sorudan başlayalım. şüphe yok ki, böyle bir program yazılabilseydi pek çok matematik problemi çok daha verimli bir yöntemle çözümlenebilirdi.
  
  buna ilk örnek olarak collatz sanısını verebiliriz. bütün sayıların 1'e indirgenebileceği teoremidir. a sayısı çift ise bu a/2, tek ise de 3a+1 şeklinde indirgeme yapılabilir. bunun testi hâlâ devam etmektedir.
  
  goldbach konjonktürünü düşünelim. 2'den büyük her çift sayının iki asal sayının toplamı şeklinde yazılabileceği iddiasıdır ki denemesi bilgisayarlarda 400,000,000,000,000'lere gelene kadar yapılmıştır.
  
  fermat'nın son teoremi, yani "x^n + y^n = z^n" yüzyıllarca bir tartışma konusu olmuştur.
  
  pi sayısının virgülden sonra kaç basamağı olacağını, basamakların bir sınırı olup olmadığını sadece pi değerini hesaplayan programın duracağı/durmayacağı bilgisi üzerinden anlamak mümkün olabilirdi.
  
  alan turing ise bu makineyi yapmanın imkânsız olduğunu göstermiştir. bunu anlayabilmek için matematikçi olmaya gerek yoktur, reductio ad absurdumdan yola çıkmak yeterlidir.
  
  diyelim bu makineyi inşa ettik. makinenin işlevi ne? "x programı i inputu ile sonlanır mı?" sorusuna cevap vermek. bunu test edip evet veya hayır sonucunu veren makineye de m1 dedik. sonra m1'i ikinci bir makine ile birleştirdik. (o da m2 olsun) m2, m1'den gelen cevap evet ise loopa girsin, hayır ise sonlansın. bu oluşan yeni birleşik makinede yürüttüğümüz işlemin sonlanıp sonlanmayacağını, m1'in bir özdeşi ile çözümleyebilir miyiz? m1 sonlanırsa bütünsel olarak sonlanma olmaz, yok eğer sonlanmazsa da bütünsel olarak sonlanma olur. bu da kusursuz bir m1'in tasarlanamayacağının kanıtıdır.
  
  ilginç bir şekilde, günümüzde insan beyninin algoritmik işlediğine dair bir algı vardır. bu öyle yanıltıcı bir algıdır ki, sanki beynin algoritmik olduğu kanıtlamazsa eğer; bu onun rastgele veya doğa kanunlarından azade bir işleyişe sahip olduğu anlamına gelmelidir. aksi yöndeki varsayımlar ise yapay zekanın zamanla bilinç kazanacağı çıkarımına, bilinci bilgisayarlara yükleme hayallerine kadar gidebilmektedir.
  
  roger penrose buyurur ki; turing makineleri için bir entscheidungsproblem algoritması yoktur lakin sistem deterministiktir.
  
  düşünsel olarak herhangi bir fiziksel sürece uygulanabilecek olan yorumlamasını sizlere bırakıyorum.