Matiyasevich Teoremi ve Pogramlamanın Doğası

Question

Hilbert'in 10. problemi, polinomyel diyofantus denklemlerinin doğal sayılarda çözümü olup olmadığını söyleyen genel bir algoritmanın var olup olmadığıydı. Matiyasevich teoremi böyle bir algoritma olmadığını söylüyor, bu durumda çözümü olup olmadığını bulamayacağımız diyofantus denklemleri var mı? Çözümünü sadece biz mi bulamıyoruz yoksa biz buluyoruz da bilgisayarlar mı bulamıyor, buna ek olarak bizim çözebildiğimiz fakat bilgisayarların asla çözemeyeceği problemler var mı? Ha bir de bilgisayarların binary olup olmaması önemli mi?

Örneğin $x^3 + y^3 + z^3 = 33$ denklemini insanlar çözebilse de bilgisayarlar asla çözemez gibi bir durum var mı, teşekkürler.

Comments

Biraz felsefik bir soru olmus aslinda. Church-Turing hipotezi hesaplanabilir her seyin turing makinalari tarafindan hesaplanabilecegini iddia ediyor (belirtmek isterim bilgisayarlar turing makinasi degildir hafizalari sinirli oldugu icin). Bir de Church-Turing-Deutsch hipotezi var, bu ise evrenin bir quantum bilgisayar tarafindan hesaplanabilir olmasi gerektigini savunuyor. Turing makinasini yaparken insanlarin dusunme sistemini soyutlamaya calisti. Calisirken bir seyleri kagida yazariz daha sonra kagitta ileri geri gidip ya bir seyler sileriz yada bir seyler ekleriz. Turing makinalari da boyle calisiyor. Ben insanlarin cozebildigi her problemin bilgisayarlar tarafindan da teorik olarak cozulebilecegini dusunuyorum.

Answer 1

Hilbert'in sunduğu problemlerin tam listesi (23 tane) $1902$ de  Bulletin of the American Mathematical Society'de yayınlanmıştır.

10. Problem - Bir Diyofant Denkleminin Çözülebilirliğinin Belirlenmesi:

Herhangi bir sayıda bilinmeyen büyüklük ve rasyonel sayı katsayıları olan bir Diyofant denklemi verildiğinde: denklemin rasyonel sayılarda çözülebilir olup olmadığının sınırlı sayıda işlemle belirlenebileceği bir işlemler dizisi (algoritma) tasarlamak.

 

Sorunun ne dediğiyle ilgili biraz açıklama verebiliriz: Örneğin

$\bullet$ $a,b,c$ tam sayılar ve $x, y$ tam sayı bilinmeyenler olmak üzere $ax+by=c$ denkleminden $x, y$ değerlerini bulmamızı sağlayacak, $x, y$ tam sayıları yoksa da olmadığını söyleyebilecek bir yöntem (varsa) bulunuz. İki değişkenli lineer Diyofant denklemi olup nasıl çözeceğimizi iyi biliyoruz.

$\bullet$ $a,b,c, \dots, n$ tam sayılar ve $x, y, z$ tam sayı bilinmeyenler olmak üzere $ax^2+by^2 + cz^2 +dxy+eyz+fzx + kx +ly +mz +n =0$ denkleminden $x, y, z$ değerlerini bulmamızı sağlayacak, $x, y, z$ tam sayıları yoksa da olmadığını söyleyebilecek bir yöntem (varsa) bulunuz. $a=b=1$, $c=-1$, $d=e= \cdots = n=0$ durumunda $x^2 + y^2 = z^2$ denklemi olup Pisagor üçlülerini nasıl bulacağımızı iyi biliyoruz. $x,y,z$ den biri $0$ iken çözümleri bulmak da basittir. Fakat $a, b, \dots $ katsayıları keyfi değişirken nasıl çözüm üretebileceğim ile ilgili bildiğim bir yöntem yok. 

$\bullet$ Yöntemimiz $x^3 + y^3 + z^3 = a $ denklemini de $a$ tam sayısının alacağı değerlere göre çözebilmelidir. Bunun için de genel bir çözüm yöntemim yoktur.

$\vdots$

$\bullet$ Bulacağımız yöntem $a_1x^ny^mz^k + a_2x^{n-1}y^mz^k + \cdots + b_1x + b_2y + b_3z +c =0$  türündeki bir denklemi de tam sayılarda (veya rasyonel sayılarda) çözebilecek olmalıdır. Problem artık anlaşıldı sanıyorum. Matiyasevich, böyle bir genel yöntem olmadığını kanıtlamıştır.

 

Görüldüğü gibi bazı özel durumları ifade eden çözüm yöntemleri (algoritmalar) bulunmuştur. İnsan zekasıyla çözüm yöntemi bulduktan sonra bunu bilgisayar diliyle, kodlarla ifade etmek zor olmasa gerek. Hatta yöntemi bulsak bile, kağıt kalemle bu yöntemimizi uygulamak pek pratik olmayabilir. Örneğin sonlu adım olarak $1.000.000.000$ adım uygulamamız gerekiyorsa bunu bir insan ömrü içinde kontrol etmek mümkün olmayacaktır. Hilbert buna da razı, sonlu adımda problemi çözecek yöntem (varsa) bu yeterlidir, diyor. $1900$'de bilgisayar yoktu, bu sebeple problemin özünde binary (ikilik) sistem kullanıp kullanmama ile ilgili bir kısıtlama yoktur. Günümüzde, algotirmamızı yazıp işlemleri bilgisayarlara biraz daha hızlıca yaptırabiliyorsak bu da kabul ediliyor ve problemi çözmüş sayılıyoruz.

 

''Biz çözmesini biliyoruz ama bilgisayar çözemiyor'' gibi bir durum yoktur.

 

Not: Hilbert'in $1902$ de tamamı yaynlanan $23$ problemlik listesinin orijinal yaynına BURADAN ulaşabilirsiniz.