Alman matematikçi David Hilbert (1862-1943) ‘genel’ bir matematik probleminin çözümü için algoritmik bir yöntemin ilke olarak var olup olmadığı sorusunu ortaya koyar. Entscheidungs problem ya da hilbert problemi olarak bilinen problem budur:
İyi tanımlanmış ‘tüm’ matematik problemlerini çözecek ‘mekanik’ bir yöntem var mıdır?
Buna karşın, bir Turing Makinası’nın ‘mekanik’ olarak belirlenebilecek ‘her’ mantıksal veya matematiksel işlemi kapsayıp kapsamadığını da sorabiliriz. N. turing makinasını tn ile gösterelim. p sayısının ikilik kodlamasını da tn(m) = p şeklinde gösterelim. Bu durum, tn , m sayısına uygulandığında p sayısını üretir demektir. Bu işlem algoritmik bir yöntemdirve evrensel turing makinasına (u) uygulanabilir.
Buradan hareketle m sayısına uygulanan tn makinesinin stop konumuna geçip geçmeyeceği problemine de ‘durma problemi’ denir. Herhangi bir m sayısı için tn ‘ in durmasını sağlayan birçok komut dizi bulunabilir. Fakat bazen turing makineleri bir takım sayılarla işlem yaptıklarında sonsuza kadar durmazlar. M sayısına uygulanan tn makinesinin işleminin durmaması tn(m) = şeklinde gösterelim. Bir turing makinesinin durup durmayacağına karar verebildiğimizde, çözülmemiş matematik problemlerini de bu yöntemle ifade edebiliriz.
(x+1)t+3+(y+1)t+3 = (z+1)t+3
denklemini sağlayan x, y, z, t kümesi nedir?
Fransız matematikçi pierre de fermat’ ya (1601-1665) ait ‘Fermat’ nın Son Teoremi’ olarak bilinen denklemin kanıtına dair bir örnek halen bulunamamıştır.
Herhangi bir diophant denkleminin tam sayı çözümünün olup olmadığının bulunması’ problemine (Hilbert’ in onuncu problemi) ait bir algoritma da bulunamamıştır. Ve yine Goldbach konjektür’ ü olarak bilinen ‘2’ den büyük her çift sayı iki asal sayının toplamıdır’ şeklindeki genellemesinin doğruluğuna ait cevap, bir turing makinesinin durma problemi ile yakından ilişkilidir.
Bir turing makinasının durma problemine ait algoritmik yöntem bulunamadığını Alan Turing göstermiştir (Ayrıca Amerikalı mantık bilimci Alonzo Church’ un Stephen C. Kleene ile birlikte geliştirdiği ‘lambda hesabı’ nı da unutmamak gerekir).
Alan Turing bu kanıtı ortaya koyarken olmayana “ergi metodu”nu (reductio ad absurdum) kullanmıştır. Yani önce böyle bir algoritmanın var olduğunu düşünmüştür.
Öyle bir h turing makinası vardır ki n. turing makinasının m sayısına uyguladığı işlem sonrasında durup durmayacağına karar verebilsin. Ve durmaz ise bant üzerine 0, durursa 1 işlensin
0 , tn(m) = ?
h(n,m) =
1 , tn(m) durursa
Tüm turing makinalarının tüm girdilerini içeren sonsuz bir tablo düşünebiliriz.
Turing makinasının var olduğunu kabul ettiğimizden, bu tablo hesaplanabilir dizilerden oluşur. Yani m = 0, 1, 2, 3, … sayılarına uygulandığında dizinin elemanlarını üreten bir turing makinası vardır. yani tablo tn(m) x h(n,m) yöntemi ile, yani bir algoritma ile hesaplanabilir bir şekilde üretilmiştir.
( sembolik olarak @ x 0 = 0 ‘ dır )
n ve m sayılarına uygulandığında tabloya uygun kayıt üreten bir q turing makinesi vardır. Böylece h turing makinesinde olduğu gibi q’ nun bandında n ve m q(n,m) = tn(m) x h(n,m) yöntemi ile kodlanabilir. Ve Georg Cantor’ un (1845-1918) köşegen yöntemini kullanarak, tablonun köşegeninden elde edilen sayı dizisindeki (0, 0, 1, 2, 1, 3, 7, 1, …) her sayıya bir ekleyelim:
bu ‘hesaplanabilir’ yöntem sayesinde 1, 1, 2, 3, 2, 4, 1, 8, 2, … dizisi elde edilir.
n ve m sayılarına uygulandığında tabloya uygun kayıt üreten bir q turing makinası vardır. Böylece h turing makinasında olduğu gibi q’ nun bandında n ve m q(n,m) = tn(m) x h(n,m) yöntemi ile kodlanabilir. Ve Georg Cantor’ un (1845-1918) köşegen yöntemini kullanarak, tablonun köşegeninden elde edilen sayı dizisindeki (0, 0, 1, 2, 1, 3, 7, 1, …) her sayıya bir ekleyelim:
Bu ‘hesaplanabilir’ yöntem sayesinde 1, 1, 2, 3, 2, 4, 1, 8, 2, … dizisi elde edilir.
m ile n eşitlenerek köşegen üzerinde verildiğinden yeni bir hesaplanabilir dizi 1 + q(n,n) dizisi, yani 1+tn(n) x h(n,n) dizisi elde edilmiş olur. Tablo ‘her’ hesaplanabilir diziyi içerdiğinden elde edilen bu yeni diziyi de içeriyor olmalıdır. oOsa yeni dizi ilk kaydın ilk sırasından, ikinci kaydın ikinci sırasından … farklıdır. Ve bir çelişki’ ye ulaşılmıştır.
Diğer bir şekilde: 1 + q(n,n) algoritması için turing makinesi sayısı k olsun, öyle ise algoritma: 1 + tn(n) x h(n) = tk(n) şeklindedir, n yerine k yazılırsa
1 + tk(k) x h(k,k) = tk(k)
algoritması elde edilir. Bu da bir çelişkidir. Çünkü tk(k) durduğunda
1 + tk(k) = tk(k)
gibi olanaksız bir durum ortaya çıkar.
1 + o = ? ( h(k,k) =1
olduğuna göre tk(k) durmaz ise h(k,k) = o olacağından yine bir çelişki oluşur ).
Ulaşılan bu çelişkilerden bize h, turing makinasının gerçekte var olamayacağını göstermektedir. Böylece bir Turing makinasının durup duramayacağına karar verecek evrensel bir algoritma da yoktur.
Turing makinalarının durmasına ait bir algoritmanın olmaması, ‘tüm’ matematik sorularıyla ilgili karar verme konusunda ‘genel’ bir algoritmanın var olamayacağı anlamına gelmektedir. Bu da ‘hilbert problemi’ nin çözümünün olmadığını gösterir.
Bunun anlamı nedir; bu bir Yapay Zeka’da da mesela Terminatör’ün gerçek olduğunu farzedelim, onun kendisini kurtarmak için kullanması gereken karar analizlerinin asla tek tip bir algoritmayla yazılamayacağı yazılsa bile tutarsızlıklar göstereceğini belirtir. Bu da bir yandan the Matrix gibi bir düzeneğin, /bilgisayar/yazılımcı/kişi/evrensel algoritma/ simülasyonları tarafından yazılamayacağını iddia eder diye yorumlayabiliriz. Bu çözümsüzlüğün bir ucu da özgür irade, saçaklı mantık, kuantum bilinç felsefesine çıkmaktadır. Diğer yandan Garry Kasporov ya da x kişinin bir şekilde Deep Blue ya da x bilgisayarı her zaman satrançta yenebilme ihtimalini ortaya koyar. Bunun halk dilindeki nüksetme biçimi.: “neticede onu da bir insan yaptı” önermesidir.
Hilbert Problemlerine ilişkin iyi bir kaynak için bkz: mathworld.wolfram.com/hilbertsproblems.html