Durma Problemi: Turing'in "İmkânsızlık" Teoremi

"Bu kod sonsuza dek mi çalışır?"

Programlama yapan herkes bu kâbusu yaşamıştır: bir kod yazıyorsunuz, çalıştırıyorsunuz, sonra bir şey olmuyor. Program duruyor mu, çok mu yavaş, yoksa sonsuz döngüye mi girdi? Beklemeli misiniz, durdurmalı mısınız?

Hayalim: bir araç olsa, koda bakıp size kesin söyleseydi: "Bu program 5 saniye içinde duracak" veya "Bu program asla durmayacak." Hayat bilgisayarcı için cennet olurdu.

Maalesef böyle bir araç var olamaz. Bu, bilgisayar biliminin en derin imkânsızlık teoremi'dir: durma problemi (halting problem).

Resmi ifade

Durma problemi: Verilen bir program $P$ ve bir girdi $I$ için, "$P(I)$ sonunda duracak mı, yoksa sonsuza dek mi çalışacak?" sorusunu cevaplayan genel bir algoritma var mıdır?

Alan Turing 1936'da yayımladığı "On Computable Numbers, with an Application to the Entscheidungsproblem" makalesinde kanıtladı: Hayır, böyle bir algoritma yoktur.

Kanıt: çelişkiyle imkânsızlık

Turing'in kanıtı diagonalization (köşegenleştirme) tekniğini kullanır — Cantor'un farklı sonsuzluk seviyeleri için kullandığı yöntemin sade bir uyarlaması.

Adım 1: Varsayım — bir algoritma halts(P, I) var olsun. Bu algoritma True döner eğer $P(I)$ duruyorsa, False döner eğer sonsuza dek çalışıyorsa.

Adım 2: Şu garip programı tanımlayın:

function diabolical(P):
    if halts(P, P):
        # sonsuz döngü
        while True:
            pass
    else:
        return  # hemen dur

diabolical(P): eğer $P$ kendisini girdi olarak alındığında duruyorsa, sonsuz döngüye girer; durmuyorsa hemen durur. Kendisinin tersini yapar.

Adım 3: Şimdi diabolical(diabolical) çalıştırın. Ne olur?

• Eğer diabolical(diabolical) duruyorsa: halts(diabolical, diabolical) = True olmuştur, dolayısıyla diabolical sonsuz döngüye girer. Çelişki.
• Eğer diabolical(diabolical) durmuyorsa: halts(diabolical, diabolical) = False, dolayısıyla hemen durur. Çelişki.

Her iki durumda da çelişki. Demek ki başlangıç varsayımımız (halts algoritması var) yanlış. Böyle bir algoritma yoktur.

Russell paradoksuna benzerlik

Bu kanıt Russell paradoksuna çok benzer ("kendisini içermeyen kümelerin kümesi") ve Gödel'in eksiklik teoremine yakındır. Hepsinin ortak teması: kendi kendine referans veren sistemler kendi sınırlarına ulaşır.

20. yüzyıl matematik tarihinin en güzel parçalarından biri: aynı sezgi farklı dallarda farklı sonuçlar veriyor.

Anlamı: ne öğrendik?

Durma problemi: bilgisayar bilimlerinin temel sınırı. Pratik sonuçlar:

1) "Mükemmel" antivirüs imkânsız

Bir virüs analiz programının "Bu program zararlı mı?" sorusuna genel olarak cevap vermesi mümkün değildir. Çoğu güvenlik aracı kısmi yaklaşımlar kullanır.

2) "Mükemmel" derleyici uyarısı imkânsız

Bir derleyicinin "Bu döngü sonsuza gider!" diye uyarması genel olarak imkânsızdır. Bazı durumlarda evet (basit kalıplar), genel olarak hayır.

3) Otomatik teorem ispatlamanın sınırı

"Bu önerme kanıtlanabilir mi?" sorusu, durma problemine indirgenebilir. Yani tüm matematik problemlerini otomatik çözebilen bir AI yoktur (Gödel-Turing imkânsızlığı).

4) Yapay zekânın sınırı?

Bazı düşünürler (Roger Penrose, vs.) insan zekâsının Turing'in modelini aştığını iddia eder. Tartışmalı; çoğu bilgisayar bilimcisi bu görüşü reddeder.

"Bazı problemler çözülemez"

Durma probleminin getirdiği felsefi sonuç: bilgisayar dünyasında bazı sorular'a "evet/hayır" diye cevap algoritmik olarak verilemez. Bunlara hesaplanamaz (uncomputable) sorular denir.

Durma problemi sadece bir tanesi; pek çok başka soru da hesaplanamazdır:

• Post yazışma problemi
• Diophantine denklemleri (Hilbert'in 10. problemi, Matiyasevich 1970)
• Word problem (gruplar teorisi)
• Tile döşeme problemi

Pratik yaklaşımlar

Bilgisayar bilimcileri pratikte ne yapar?

1) Yaklaşık çözümler

"Programı 1 milyon adım çalıştır, durmazsa muhtemelen sonsuz" gibi heuristikler. Mükemmel değil ama çoğu zaman yeterli.

2) Belirli alt sınıflar için çözümler

Tüm programlar için imkânsız ama belirli alt sınıflar için çözüm bulunabilir. Örneğin doğrusal program alt sınıfı, belirli tip sistemler vs.

3) İnteraktif kanıtlama

İnsan + bilgisayar işbirliği. Coq, Lean gibi sistemler insan rehberliğinde matematik kanıtlarını yapılandırır.

4) Statik analiz araçları

Modern derleyici/IDE'lerde "bu kod muhtemelen sorunlu" diye uyarılar; pragmatic, %100 değil.

Turing'in bağlamı

Alan Turing 1936 makalesini David Hilbert'in "Entscheidungsproblem" (karar problemi) sorusuna cevap olarak yazdı. Hilbert sorusu: "Tüm matematik önermelerini otomatik karar verebilen bir algoritma var mı?"

Turing'in cevabı: "Hayır. Durma problemi imkânsız olduğu için karar problemi de imkânsız."

Aynı yıl Alonzo Church lambda hesabı üzerinden bağımsız aynı sonuca ulaştı. Bu, Church-Turing tezi'nin başlangıcı: "Algoritmik olarak hesaplanabilen şeyler tam olarak Turing makinesinin hesaplayabildiği şeylerdir."

Tarihte derin bir an

1936 yılı bilgisayar bilimleri tarihinin doğum yılı'dır. O zaman bilgisayar bile yoktu; sadece Turing'in soyut Turing makinesi modeli vardı. Ama bu soyut model, sonraki 80 yıl boyunca gelişecek tüm bilgisayar bilimlerinin temelini kurdu.

Durma probleminin imkânsızlığı, bilgisayarların gücünün temel olarak sınırlı olduğunu gösterir. Bu sınırlama her geçen yıl daha hızlı CPU'larla aşılamaz; mantıksal bir gerçektir.

"Bilim olarak kabul"

Durma probleminin en güzel yönü: negatif bir sonucu matematiksel olarak kesin ispatlamak. Çoğu zaman bilim "şu mümkündür" der; nadiren "şu imkânsızdır" diyebilir. Turing imkânsızlığı kanıtladığı için bilgisayar bilimleri bilim statüsünü kazandı.

Bir programcının önündeki en sıradan soru — "Bu kod duracak mı?" — modern bilgisayar bilimlerinin en derin gerçeğini taşıyor: bazı sorular vardır ki bilgisayar onları cevaplayamaz.

Turing'in 1936'daki bu sıradışı ispatı, hâlâ her bilgisayar mühendisinin bilmesi gereken bir gerçek.