Turing makinesi ve hesaplanabilirlik
Bu sayfa bir hüküm vermez; iddiaları ve kanıtları kaynaklarıyla sunar. Bilimde hiçbir teori mutlak değildir. Yöntem
Herkes için
Turing 1936'da her türlü mekanik hesabı taklit edebilecek soyut bir makine tanımladı. Bu tanımla, hiçbir algoritmanın çözemeyeceği problemler olduğunu ispatladı. Bunlardan en bilineni, bir programın durup durmayacağını önceden bilme problemidir (durma problemi). Bu fikir bugünkü bilgisayarların kuramsal temelidir.
Uzmanlar için
Turing, evrensel bir makinenin başka her makinenin tanımını girdi olarak alıp onu taklit edebileceğini gösterdi. Köşegen argümanıyla durma probleminin karar verilemezliğini ispatladı ve Hilbert'in Entscheidungsproblem'ine olumsuz yanıt verdi. Church, λ-hesabıyla aynı sonuca bağımsız olarak ulaştı. Church–Turing tezi, "etkili olarak hesaplanabilir" kavramının Turing-hesaplanabilirlikle çakıştığını söyler. Bu bir teorem değil, bir tezdir.
İddialar
- Bir programın her girdide durup durmayacağına karar veren genel bir algoritma yoktur.[1]
Kanıtlar
Destekleyen
Köşegen argümanı, böyle bir algoritma varsa kendisiyle çelişen bir programın kurulabileceğini gösterir.[1]
Karşı çıkan / sorgulayan
—
Görüşler
- Church–Turing tezinin güçlü (fiziksel) biçimini sorgulayanlar
- Fiziksel süreçlerin, örneğin kuantum veya göreli sistemlerin, Turing makinelerinin hesaplayamayacağı şeyleri hesaplayıp hesaplayamayacağı açık bir sorudur.[2]
Bağlantılar
Kaynaklar
- Makale (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society s2-42(1), 230–265DOI 10.1112/plms/s2-42.1.230arşiv
- AnsiklopediThe Church–Turing Thesis. Stanford Encyclopedia of Philosophyplato.stanford.eduarşiv
Literatürde ara
Bu konudaki akademik yayınları başka dizinlerde de arayabilirsiniz:
Bu sayfayı kaynak göster
Athena katkıcıları. (2026). Turing makinesi ve hesaplanabilirlik. Athena: İnsanlığın bilgi ağacı. Erişim: 1 Kasım 2026, https://latifkedi.github.io/athena/d/turing/
@misc{athena_turing,
title = {Turing makinesi ve hesaplanabilirlik},
author = {{Athena katkıcıları}},
year = {2026},
howpublished = {\url{https://latifkedi.github.io/athena/d/turing/}},
note = {Athena: İnsanlığın bilgi ağacı. Erişim: 2026-11-01}
}Eklendi: 27 Eylül 2026 · Son değişiklik: 28 Eylül 2026 · Sayfa geçmişi