The source-page: http://www.efgh.com/math/impossible.htm
Philip J. Erdelsky
İlk kez Dr. Dobb’s Journal Mayıs 1987
Son 40 yılda bilgisayarlardaki muazzam gelişmelere tanık olan herkes, bilgisayarların sonunda iyi tanımlanmış her sorunu çözebileceği izlenimini edinebilir. Dil anlayışındaki ilerleme ve diğer yapay zeka biçimleri hayal kırıklığı yaratıyor, ancak insan dili belirsizlikler ile dolu, bu yüzden iyi tanımlanmış bir sorun değil. Öte yandan satranç çok iyi tanımlanmıştır. Bir zamanlar akıllı aktivitenin özü olarak görülmesine rağmen, bilgisayarlar artık satrancı birkaç insan oyuncudan daha iyi oynayabiliyor.
Bazı sorunlar, iyi tanımlanmasına rağmen, en büyük bilgisayarlarımızda bile makul bir sürede çözülemeyecek kadar büyüktür. Ancak, bir bilgisayar zaman ve bellek üzerindeki tüm sınırlamalardan kurtulabiliyorsa, iyi tanımlanmış bir sorunu çözemedi mi?
İlk gerçek bilgisayarlar kurulmadan önce bile matematikçiler tarafından bilinen bu sorunun şaşırtıcı cevabı hayır. Hiçbir bilgisayarın yapamayacağı bazı şeyler vardır, çünkü bunları yapmak için hiçbir algoritmanın olmadığı kanıtlanabilir – tıpkı bir pusulanın ve düzlüğün bulunduğu bir çemberin karesini çizmenin bir yolu olmadığı gibi.
Bunlar sadece matematiksel merak değil. Bunlar, programcıların bilgisayarlarının kendileri için yapmasını istedikleri ve yazılım geliştirme araçları tedarikçilerinin hata ayıklayıcılarına dahil etmek istedikleri şeylerdir. Bilgisayar bilimi müfredatı genellikle hesaplanamayan fonksiyonlar konusunu içerir, ancak bilgisayar bilimleri bölümü olmayan programcılar bazen farkında olmadan imkansızı ister.
1935 yılında Alan Turing, bir bilgisayar programının başka bir bilgisayar programının durup durmayacağını belirleyebilecek bir yöntem olup olmadığını sordu. Bu ünlü “durma problemi” dir. Turing bunun bir çözümü olmadığını gösterdi.
Bu yeteneğe sahip bir hata ayıklayıcı kesinlikle yararlı olacaktır. Normal olarak durmamak, yaygın bir program hatası biçimidir. Ayrıca, hata ayıklayıcı, asılı olan parçayı izole etmek için başarısız programın bölümlerine art arda uygulanabilir.
Böyle bir hata ayıklayıcının imkansız olduğu açık değildir. Elbette, hata ayıklayıcı, programın durup durmadığını görmek için yalnızca tek adım atamaz. Program durmazsa, hata ayıklayıcı durumun böyle olduğunu belirlemeden sonsuza kadar çalışabilir. Ya da insan programcılarının bazen yaptığı gibi, programın sona ermek üzereyken vazgeçebilir. Bir noktada, hata ayıklayıcının “Aha! Bu döngü sonsuz!” Diyebilmelidir. Modern üst düzey dillerin tüm araçlarına sahip akıllıca yazılmış bir hata ayıklayıcı bunu yapabilir gibi görünüyor.
İmkansızlık kanıtı aşağıdaki argümana dayanmaktadır. Durma sorununu çözebilecek, sınırsız zaman ve bellek veren bir hata ayıklayıcının varsa, hata ayıklayıcının bazıları kendisiyle çelişen ve dolayısıyla imkansız olan başka şeyler yapmak için aynı kodu kullanabilirsiniz.
Özel bilgisayar dili önemli değildir. Bir dil için durma sorununu çözebilirseniz, başka bir dil için çözme sorununu çözebilirsiniz. Durma problemini çözmeden önce bir derleyici veya başka bir çeviri programı kullanın. Bir derleme dili programının daha yüksek bir dile çevrilmesi oldukça kolaydır, ancak nesne programı verimsiz olmak zorundadır. Ancak amaç, durma problemine bir çözümün sadece verimsiz değil, imkansız olduğunu göstermektir.
Kendini çevirmek, Turing Makinesi olarak adlandırılan minimal bir makine önerdi. Belleğinin sonsuz uzunluğunda, ancak sadece bir bit genişliğinde olması gerekiyordu ve makine bir bantta olduğu gibi ona sadece sıralı erişime sahipti. Programlama dili aslında sadece birkaç temel komut içeren bir akış şemasıydı. Bununla birlikte, Turing, makinesinin yeterli zaman ve uygun bir program verildiğinde başka bir makineyi taklit edebildiğini gösterdi. Böyle bir yapı bizim amaçlarımız için gerekli değildir – bilgisayarın tanıdık bir üst düzey dilde programlandığını hayal edebilirsiniz.
Şimdi, bir programın belirtilen bir S dizesini (başka bir çıktı ile veya başka bir çıktı olmadan) yazdırabileceğini belirleme sorununu düşünün. Durdurma sorununu çözebilirseniz, bu sorunu çözebilirsiniz. Programdaki her baskı deyimini, çıktıyı yazıcıya göndermeyen, ancak çıktıyı izleyen ve S dizesi göründüğünde duran bir rutinle değiştirin. Ardından, programın başka herhangi bir nedenle durmasını önlemek için, programdaki tüm durma deyimlerini sonsuz döngülerle değiştirin. Ardından sonuç için durma problemini çözün.
Böyle bir program kendi içinde faydalı olacaktır çünkü birçok çalışma zamanı hatası farklı mesajlar üretir ve bu tür hataların oluşacağını önceden tahmin etmek yararlı olacaktır.
Bu herhangi bir S dizesi için geçerli olduğundan, bir programın kendi kopyasını yazdırıp yazdırmayacağını da belirleyebilirsiniz. Bu ilk bakışta göründüğü kadar meraklı değil. Kendisi de dahil olmak üzere 1.000 karakterin tüm kombinasyonlarını yazdıran 1.000 karakterlik bir program yazmak kolaydır. Aslında, 1000 karakter muhtemelen çoğu üst düzey dilde gerekli olan karakter sayısının fazla tahminidir.
Şimdi aşağıdakileri yapmak için bir program yazabilirsiniz. İlk olarak, olası tüm programları tek tek oluşturun. Bunu yapmanın en kolay yolu tüm dizeleri oluşturmak ve her birinin bir program olup olmadığını kontrol etmektir. Derleyiciler sözdizimini kontrol ettiklerinde bunu yaparlar. Ardından, her bir programı kendi kopyasını yazdırıp yazdırmayacağını kontrol edin. Son olarak, kendisinin bir kopyasını yazdırmayan her programın bir kopyasını yazdırın.
Bu program, tüm programları üretme sürecinde sonunda kendini üretecektir. Kendisinin bir kopyasını yazdırıyor mu? Varsa, kendisinin bir kopyasını basan bir programın bir kopyasını yazdırarak kuralı ihlal eder. Başlamazsa, kendisinin bir kopyasını yazdırmayan bir programın kopyasını yazdırarak kuralı ihlal eder. Bu ölümcül çelişki, durma sorununun bir çözümü olmadığını kanıtlıyor.
Bunu Russell’ın paradoksu (kendilerini içermeyen tüm setler kümesi) veya berber paradoksu (kendini tıraş etmeyen herkesi tıraş eden berber) olarak tanıyabilirsiniz.
Bir hata ayıklayıcının dize çıktı sorunu gibi durma sorununa dönüştürebileceği herhangi bir sorun aynı şekilde çözülemez. Bazı diğer açık örnekler:
- bir programın belirli bir noktaya ulaşıp ulaşmayacağını belirleme (Ada programcıları: bu yüzden PROGRAM_ERROR bir derleme zamanı hatası değil bir çalışma zamanı hatası olmalıdır)
- bir değişkenin kullanılmadan önce başlatılıp başlatılmadığını belirleme
- belirli bir kod segmentine erişilemez olup olmadığını ve asla yürütülmeyeceğini belirleme
- iki programın aynı şeyi yapıp yapmadığını belirleme
Elbette, bir hata ayıklayıcı veya derleyici bazen bu hataları tahmin edebilir – örneğin, erişilemeyen kod bazen derleme zamanında tanımlanabilir. Ancak bu tür sorunlara evrensel çözümler mevcut değildir.
İki programın aynı şeyi yapıp yapmadığını belirlemenin imkansızlığı, belirli bir Truva atı türünü yenmenin her zaman mümkün olduğu anlamına gelir. ACM’nin Bildirimleri’nde (Ağustos 1984) yeniden basılan bir derste Ken Thompson, derlenmiş herhangi bir Unix sistemine erişmesine izin vermek için giriş deyimini yanlış derleyecek bir C derleyicisine bir Truva atı koyabileceğini savundu ve kendisinin bir kopyasını eklemek için C derleyicisini yanlış derleyin. Truva atı C derleyicisinin kaynak kodunda görünmez. Editöre bir mektupta, Steve Draper, böyle bir Truva atının C derleyicisini (aynı şeyi yapan farklı kod yazarak) başka sözcükler yazarak ve sonra derleyerek yenilebileceğini belirtti. Hiçbir Truva atı, yanlış yazılmış programları tanıyamaz – bu nedenle her zaman Truva atı’nı yenecek bir açıklama vardır.
Bu konudaki kendi düşüncem, Truva atı ustaca yazılmadığı sürece, birçok başka ifadenin onu yeneceği ve aslında sonunda normal yazılım bakımı ile yenileceği yönündedir. Çoğu paraphras’ı tanıyacak kadar akıllı herhangi bir Truva atı muhtemelen C derleyicisinin geri kalanından çok daha büyük olacaktır. Asla kapılardan geçemezdiniz.
Durma problemi, matematikçi David Hilbert tarafından 1900’de ortaya atılan diğer iki problemle yakından ilgilidir. Her matematiksel ifade için resmi bir kanıt veya dayanıklılık yok mu? Kanıt bulmak için bir algoritma var mı?
İlk soru 1931’de Kurt Gödel tarafından olumsuz olarak cevaplandı. Gödel’in kanıtı karmaşıktı, ancak durma sorununun çözümsüzlüğünü kabul ederseniz, basitçe kanıtlanabilir. Belirli bir programın durup durmayacağı matematiksel bir ifadedir. Aslında, birçok matematiksel teorem zaten durdurma probleminin özel durumlarıdır, çünkü karşı örnekleri aramak ve birini bulduğunda durmak için bir program yazabilirsiniz. Teorem, programın hiç durmadığı iddiasına eşdeğerdir.
Bir programın durduğu iddiasının her zaman resmi bir kanıtı veya kanıtı olsaydı, bir kanıtı veya bir kanıtı bulana kadar tüm kanıtları (daha önce açıklanan programın tüm programları oluşturduğundan daha fazla veya daha az) oluşturabilirsiniz. Bu durma problemini çözecektir. Durma problemi genel olarak çözülemez olduğu için, bu türden en az bir matematiksel ifade bulunmamalıdır – yani, kanıtlanamaz veya resmi olarak kanıtlanamaz.
Bu, genel olarak bir programın çalıştığını kanıtlamanın imkansız olduğunu gösterir. Belirli programların veya sınırlı program sınıflarının belirli şeyleri yaptığı kanıtlanabilir, ancak bunu her program için yapmanın bir yolu yoktur.
Bazı matematiksel ifadelerin kararsız olduğu düşünüldüğünde, herhangi bir matematiksel ifadenin doğru veya yanlış olup olmadığına karar vermeden bile karar verilebilir olup olmadığını söyleyebilen bir program, “karar verilebilirlik programı” var mı? Bu makalenin tonundan tahmin edebileceğiniz gibi, cevap yine hayır. Karar verilebilir bir programınız varsa, herhangi bir programı alıp durup durmadığını sorabilirsiniz. Ardından bu soruya karar verme programını uygulayın. Soru karar verilebilirse, tüm ispatların araştırılması bunu ispatlar ya da çürütür. Soru kararsızsa, program asla durmaz; aksi takdirde, durana kadar çalıştırarak durduğunu kanıtlayabilirsiniz.
Bu nedenle, teorem kanıtlama programları, sınırlı alanlarda olmalarına rağmen başarılı olmakla birlikte, her şeyi kanıtlayamaz. Bazı şeyler daima kavrayışının ötesinde kalmalıdır.
Bu argümanlar matematiksel anlamda titiz değildir, çünkü çok fazla şey dışarıda bırakılmıştır. Turing ve Gödel’in çalışmalarının büyük bir kısmı, “hesaplama” ve “kanıt” kavramlarının argümanlarının matematikçiler tarafından kabul edileceği noktaya resmileştirilmesini içeriyordu.
Gerçeğe karşılık gelmeyen bir zımni varsayımı daha önce görmüş olabilirsiniz. Programlar, bellek sınırlamaları ile kısıtlanmamıştır. Bir programın bellek sınırlaması varsa, durma problemi teoride çözülebilir – ancak sadece çok daha büyük bir belleğe sahip bir program tarafından çözülebilir.
Bu şekilde yapılabilir. Bellek sınırlaması olan bir programın yalnızca sınırlı sayıda durumu vardır. Bir hata ayıklayıcı, işgal ettiği durumları takip ederek tek adımda ilerleyebilir. Durmadan önce aynı durumu iki kez işgal ederse, aynı durum sırasını süresiz olarak tekrarlar ve asla durmaz.
Bunu yapmak için, hata ayıklayıcının programın hangi durumları işgal ettiğini takip etmek için yeterli belleğe ihtiyacı vardır. Her olası durum için sadece bir bit gerekir, ancak basit bir program için bile olası durumların sayısı gerçekten akıl almazdır. Bellekteki her bit kombinasyonu farklı bir durumdur. Bu nedenle, yalnızca 1.024 bayt belleğe sahip bir program, bayrak ve kayıtlardan hiçbir şey söylemek için yalnızca bellek yapılandırması nedeniyle en az 2(1024 x 8) duruma sahiptir. Bu parmak arası terlik, bilinen tüm evrene uymayacaktır. Dolayısıyla durma sorununun bu durumda bile çözümünün olmadığı söylenebilir.
Öyleyse, yapay zekanın neyi başarabileceği konusunda kesinlikle bazı sınırlar olduğu ve matematikçilerin ve programcıların işlerinin asla tamamen otomatik olamayacağı açık olmalıdır. (Bu benim için büyük bir rahatlık çünkü ben bir matematikçi ve programcıyım.
Ancak sadece mükemmel çözümler imkansızdır. Hala tartışılabilir ve bazıları tarafından yapay zeka programlarının en azından aynı başarı oranıyla insan zihninin çözebileceği her sorunu çözebileceği tartışılmaktadır. Ve tek gereksinim mükemmel çözümler değil pratik çözümler ise, o zaman birçok ilginç ama teorik olarak çözülemeyen sorun çözülebilir.