Gödel'in Eksikliği ve Hesaplama
Gödel'in eksiklik teoremleri, yeterince güçlü, tutarlı herhangi bir biçimsel sistemin kanıtlayamayacağı doğru ifadeler içerdiğini göstermektedir; bu durum, hesaplanabilirlik kuramında keşfedilen karar verilemezlik (undecidability) ile derinlemesine iç içe geçmiş bir sonuçtur.
Tanım
Eksiklik teoremleri, temel aritmetiği ifade edebilen herhangi bir tutarlı biçimsel sistemin eksik olduğunu, kanıtlayamayacağı doğru aritmetik ifadeler içerdiğini ve kendi tutarlılığını kanıtlayamadığını belirtmektedir; hesaplama terimleriyle, kanıtlanabilir ifadeler kümesi tanınabilir (recognizable) ancak tümleyeni (complement) tanınabilir değildir, bu durum karar verilemezliği (undecidability) yansıtmaktadır.
Kapsam
Bu konu, birinci ve ikinci eksiklik teoremlerini, aritmetizasyon tekniğini ve Gödel numaralandırması aracılığıyla öz-referansı, eksiklik ile durma probleminin (halting problem) ve birinci dereceden mantığın karar verilemezliği (undecidability) arasındaki yakın ilişkiyi ve biçimsel akıl yürütmenin ve otomatik kanıtlamanın sınırlarına yönelik sonuçlarını kapsamaktadır.
Temel sorular
- Neden hiçbir tutarlı, yeterince güçlü biçimsel sistem tüm doğru aritmetik ifadeleri kanıtlayamaz?
- Gödel numaralandırması aracılığıyla öz-referans, kanıtlanamaz doğru bir cümleyi nasıl üretir?
- Eksiklik ve durma probleminin (halting problem) karar verilemezliği (undecidability) tek bir olgunun iki farklı görünümü müdür?
- Eksiklik, otomatik teorem kanıtlamanın sınırları için ne anlama gelmektedir?
Temel kuramlar
- Birinci eksiklik teoremi
- Aritmetiği kodlayabilecek kadar güçlü herhangi bir tutarlı biçimsel sistem, ne kanıtlayabileceği ne de çürütebileceği doğru bir ifade içermektedir; bu ifade, kendi kanıtlanamazlığını etkili bir şekilde iddia eden bir cümle tarafından oluşturulmuştur.
- Hesaplanabilirlik aracılığıyla eksiklik
- Eksiklik, durma probleminin (halting problem) karar verilemezliğinden (undecidability) kaynaklanmaktadır: eğer her aritmetik doğru kanıtlanabilir olsaydı, kanıt arayarak durmaya karar verilebilirdi; bu nedenle karar verilemez problemlerin varlığı, kanıtlanamaz doğruların varlığını zorunlu kılmaktadır.
Klinik önem
Eksiklik ve bunun hesaplama alanındaki karşılığı, otomatik akıl yürütmeye katı sınırlar getirmektedir: hiçbir algoritma tüm aritmetik doğrulara karar veremez veya her matematiksel sorunu çözemez; bu nedenle teorem kanıtlayıcılar ve doğrulama sistemleri, tam otomatik karar verme yerine insan rehberliğine, kısıtlı kuramlara veya etkileşimli kanıta dayanmak zorundadır.
Tarihçe
Gödel, eksiklik teoremlerini 1931'de kanıtlamış, Hilbert'in matematiğin eksiksiz ve kendini haklı çıkaran bir biçimselleştirme umudunu boşa çıkarmıştır. Beş yıl içinde Church ve Turing, bu sınırları karar verilemezlik (undecidability) ile ilişkilendirmiş ve eksikliğin durma problemi (halting problem) aracılığıyla hesaplamalı yorumu, hesaplanabilirlik kuramının temel bir unsuru haline gelmiştir.
Öne çıkan isimler
- Kurt Gödel
- Alan Turing
- Alonzo Church
- John Barkley Rosser
İlgili konular
Temel eserler
- godel1931
- boolos2007
Sıkça sorulan sorular
- Eksiklik, matematiğin bozuk olduğu anlamına mı gelmektedir?
- Hayır. Bu, hiçbir tek tutarlı biçimsel sistemin her aritmetik doğruyu kanıtlayamayacağı anlamına gelmektedir, matematiğin tutarsız veya güvenilmez olduğu anlamına gelmez. Matematikçiler biçimsel sistemler içinde ve arasında çalışmaktadır ve eksiklik, herhangi bir sabit sistemin yakalayabileceği içsel bir sınırı işaret etmektedir.
- Gödel'in teoremi durma problemi (halting problem) ile nasıl ilişkilidir?
- Yakından ilişkilidirler. Durma probleminin (halting problem) çözülemezliği (unsolvability) eksikliği ima etmektedir: eğer bir biçimsel sistem hangi programların durduğuna dair her doğruyu kanıtlayabilseydi, kanıt arayarak durmaya karar verilebilirdi, bu da Turing'in sonucuna aykırı düşerdi. Her ikisi de, mantıkta ve hesaplamada, biçimsel yöntemin aynı temel sınırlarını ifade etmektedir.