Köşegenleştirme adı verilen bir yöntemle elde edilen matematiksel kanıtlar acımasızca karşıt olabilir, ancak algoritmaların sınırlarını ortaya çıkarmaya yardımcı olurlar.
Algoritmalar her yerde karşımıza çıkar hale geldi. İşe gidiş gelişlerimizi optimize ediyor, ödemeleri düzenliyor ve internet trafiğinin akışını koordine ediyorlar. Kesin matematiksel terimlerle ifade edilebilen her sorun için, en azından prensipte, onu çözebilecek bir algoritma var gibi görünüyor.
Ancak durum böyle değildir - görünüşte basit olan bazı problemler asla algoritmik olarak çözülemez. Bilgisayar biliminin öncüsü Alan Turing, bu tür "hesaplanamaz" problemlerin varlığını yaklaşık bir asır önce, modern bilgisayar bilimini başlatan matematiksel hesaplama modelini formüle ettiği aynı makalede kanıtladı.
Turing bu çığır açan sonucu sezgisel olmayan bir strateji kullanarak kanıtladı: Çözüme yönelik her girişimi basitçe reddeden bir problem tanımladı.
Massachusetts Institute of Technology'de teorik bilgisayar bilimi okuyan yüksek lisans öğrencisi Rahul Ilango, "Size ne yaptığınızı sorduğumda, 'Hayır, ben farklı bir şey yapacağım' diyorsunuz" demişti.
Turing'in stratejisi, köşegenleştirme adı verilen ve seçkin bir geçmişe sahip olan matematiksel bir tekniğe dayanıyordu. İşte kanıtının ardındaki mantığın basitleştirilmiş bir açıklaması.
Sicim Teorisi
Köşegenleştirme, her biri 0 ya da 1 olabilen bit dizilerini içeren sıradan bir problemi çözmeye yönelik zekice bir numaradan kaynaklanmaktadır. Hepsi eşit uzunlukta olan bu tür dizilerden oluşan bir liste verildiğinde, listede olmayan yeni bir dizi oluşturabilir misiniz?
En basit strateji, her bir olası diziyi sırayla ele almaktır. Her biri beş bit uzunluğunda beş dizeniz olduğunu varsayalım. Listeyi 00000 için tarayarak başlayın. Eğer orada değilse, durabilirsiniz; eğer varsa, 00001'e geçersiniz ve işlemi tekrarlarsınız. Bu yeterince basittir, ancak uzun dizilerden oluşan uzun listeler için yavaştır.
Köşegenleştirme, eksik bir diziyi adım adım oluşturan alternatif bir yaklaşımdır. Listedeki ilk dizinin ilk biti ile başlayın ve onu ters çevirin; bu yeni dizinizin ilk biti olacaktır. Sonra ikinci dizinin ikinci bitini ters çevirin ve bunu yeni dizinin ikinci biti olarak kullanın ve listenin sonuna gelene kadar tekrarlayın. Çevirdiğiniz bitler, yeni dizinin orijinal listedeki her diziden en az bir yerde farklı olmasını sağlar. (Ayrıca diziler listesi boyunca köşegen bir çizgi oluştururlar ve tekniğe adını verirler).
Köşegenleştirme, listedeki her diziden yalnızca bir biti incelemeye ihtiyaç duyar, bu nedenle genellikle diğer yöntemlerden çok daha hızlıdır. Ancak gerçek gücü, sonsuzluğu ne kadar iyi değerlendirdiğinde yatıyor.
MIT'de teorik bilgisayar bilimcisi olan Ryan Williams, "Diziler artık sonsuz olabilir; liste sonsuz olabilir - işlem yine de sonuç veriyor," diyor.
Bu gücü kullanan ilk kişi, küme teorisinin matematiksel alt alanının kurucusu Georg Cantor'dur. Cantor, 1873 yılında bazı sonsuzlukların diğerlerinden daha büyük olduğunu kanıtlamak için köşegenleştirmeyi kullanmıştır. Altmış yıl sonra Turing, Cantor'un köşegenleştirme yöntemini hesaplama teorisine uyarladı ve ona belirgin bir şekilde karşıt bir nitelik kazandırdı.
Sınırlama Oyunu
Turing, hiçbir algoritmanın çözemeyeceği matematiksel problemlerin, yani iyi tanımlanmış girdileri ve çıktıları olan ancak girdiden çıktıya ulaşmak için kusursuz bir prosedürü olmayan problemlerin varlığını kanıtlamak istiyordu. Bu belirsiz görevi, yalnızca girdinin 0 ve 1'lerden oluşan herhangi bir dizi olabileceği ve çıktının 0 veya 1 olduğu karar problemlerine odaklanarak daha üstesinden gelinebilir hale getirdi.
Bir sayının asal (yalnızca 1'e ve kendisine bölünebilen) olup olmadığının belirlenmesi bir karar problemi örneğidir - bir sayıyı temsil eden bir girdi dizisi verildiğinde, sayı asal ise doğru çıktı 1, değilse 0'dır. Bir başka örnek de bilgisayar programlarının sözdizimi hatalarına (dilbilgisi hatalarına eşdeğer) karşı kontrol edilmesidir. Burada, girdi dizileri farklı programların kodlarını temsil eder - tüm programlar bu şekilde temsil edilebilir, çünkü bilgisayarlarda bu şekilde depolanır ve çalıştırılırlar - ve amaç, kod bir sözdizimi hatası içeriyorsa 1, içermiyorsa 0 çıktısı vermektir.
Bir algoritma bir problemi ancak olası her girdi için doğru çıktıyı üretiyorsa çözer - bir kez bile başarısız olursa, o problem için genel amaçlı bir algoritma değildir. Normalde, önce çözmek istediğiniz problemi belirtir ve sonra onu çözen bir algoritma bulmaya çalışırsınız. Turing, çözülemeyen problemleri araştırırken bu mantığı tersine çevirdi - tüm olası algoritmaların sonsuz bir listesini hayal etti ve listedeki her algoritmayı devre dışı bırakacak zorlu bir problem oluşturmak için köşegenleştirmeyi kullandı.
Akılda belirli bir nesneyle başlamak yerine, cevaplayıcının her soruya hayır demek için bir bahane icat ettiği 20 soruluk hileli bir oyun hayal edin. Oyunun sonunda, tamamen sahip olmadığı niteliklerle tanımlanan bir nesne tarif etmiş olurlar.
Turing'in köşegenleştirme ispatı, bu oyunun, soruların olası algoritmaların sonsuz listesinden geçtiği ve tekrar tekrar "Bu algoritma hesaplanamaz olduğunu kanıtlamak istediğimiz sorunu çözebilir mi?" diye sorduğu bir versiyonudur.
Williams, "Bu bir tür 'sonsuzluk soruları'" demiştir.
Oyunu kazanmak için Turing'in her algoritma için cevabın hayır olduğu bir problem yaratması gerekiyordu. Bu, ilk algoritmanın yanlış yanıt vermesine neden olan belirli bir girdiyi, ikincisinin başarısız olmasına neden olan başka bir girdiyi ve benzerlerini tanımlamak anlamına geliyordu. Bu özel girdileri, Kurt Gödel'in kısa süre önce "bu ifade kanıtlanamaz" gibi kendi kendini referans alan iddiaların matematiğin temelleri için sorun yarattığını kanıtlamak için kullandığına benzer bir yöntem kullanarak buldu.
Kilit içgörü, her algoritmanın (veya programın) bir 0'lar ve 1'ler dizisi olarak temsil edilebileceğiydi. Bu, hata kontrol programı örneğinde olduğu gibi, bir algoritmanın başka bir algoritmanın kodunu girdi olarak alabileceği anlamına gelir. Prensip olarak, bir algoritma kendi kodunu bile girdi olarak alabilir.
Bu kavrayışla, Turing'in ispatındaki gibi hesaplanamaz bir problem tanımlayabiliriz: "Bir algoritmanın kodunu temsil eden bir girdi dizisi verildiğinde, bu algoritma kendi kodu girdi olduğunda 0 çıktısı veriyorsa 1 çıktısı verin; aksi takdirde 0 çıktısı verin." Bu problemi çözmeye çalışan her algoritma en az bir girdide -yani kendi koduna karşılık gelen girdide- yanlış çıktı üretecektir. Bu da bu tuhaf problemin hiçbir algoritma tarafından çözülemeyeceği anlamına gelir.
Olumsuzlama Ne Yapamaz?
Bilgisayar bilimcilerinin köşegenleştirme ile işi henüz bitmemişti. 1965'te Juris Hartmanis ve Richard Stearns, Turing'in argümanını uyarlayarak tüm hesaplanabilir problemlerin eşit olmadığını, bazılarının doğası gereği diğerlerinden daha zor olduğunu kanıtladı. Bu sonuç, hesaplama problemlerinin zorluğunu inceleyen hesaplama karmaşıklığı teorisi alanını başlattı.
Ancak karmaşıklık teorisi Turing'in aksi yöndeki yönteminin sınırlarını da ortaya çıkardı. 1975 yılında Theodore Baker, John Gill ve Robert Solovay, karmaşıklık teorisindeki pek çok açık sorunun yalnızca köşegenleştirme yöntemiyle asla çözülemeyeceğini kanıtladı. Bunların başında, kolayca sınanabilir çözümleri olan tüm problemlerin uygun bir algoritma ile çözülmesinin de kolay olup olmadığını soran ünlü P'ye karşı NP problemi gelmektedir.
Köşegenleştirmenin kör noktaları, onu bu kadar güçlü kılan yüksek soyutlama seviyesinin doğrudan bir sonucudur. Turing'in ispatı pratikte ortaya çıkabilecek herhangi bir hesaplanamaz problemi içermiyordu - bunun yerine, böyle bir problemi anında yaratıyordu. Diğer köşegenleştirme ispatları da benzer şekilde gerçek dünyadan uzaktır, bu nedenle gerçek dünya ayrıntılarının önemli olduğu soruları çözemezler.
Williams, "Virüslerle uğraşan ve onlara bir kapalı kutudan erişen bir adam gibi hesaplamayı belli bir mesafeden yapıyorlar” diyor.
Köşegenleştirmenin başarısızlığı, P'ye karşı NP problemini çözmenin uzun bir yolculuk olacağının erken bir göstergesiydi. Ancak sınırlamalarına rağmen köşegenleştirme, karmaşıklık kuramcılarının elindeki en önemli araçlardan biri olmaya devam ediyor. Williams, 2011 yılında bu tekniği bir dizi başka teknikle birlikte kullanarak belirli bir kısıtlı hesaplama modelinin bazı olağanüstü zor problemleri çözemeyeceğini kanıtladı; bu sonuç 25 yıldır araştırmacıların dikkatinden kaçıyordu. Bu, P'ye karşı NP'yi çözmekten çok uzaktı, ancak yine de büyük bir ilerlemeyi temsil ediyordu.
Bir şeyin mümkün olmadığını kanıtlamak istiyorsanız, sadece hayır demenin gücünü hafife almayın.
Not: Ben Brubaker’a ait bu makale, https://nautil.us adlı siteden alınmış ve www.felsefearenasi.com.tr editörleri tarafından Türkçeye çevrilmiştir:
https://nautil.us/alan-turing-and-the-power-of-negative-thinking-390956/?fbclid=IwAR1-iKQt3EcgcbieG1BA8sTgRgPanFTwaoNiRyy3dBXtVCPrUnqLfZPONuw
Comentarios