turing makinesi ne demek?
Turing Makinesi
Turing Makinesi, Alan Turing tarafından 1936'da tanıtılan, hesaplama prensiplerini soyutlayan ve bir algoritmanın ne anlama geldiğini tanımlayan teorik bir hesaplama modelidir. Bu model, modern bilgisayarların temelini oluşturur ve hesaplanabilirlik teorisinin merkezinde yer alır.
Temel olarak bir Turing Makinesi şunlardan oluşur:
- Sonsuz Uzunlukta Bir Bant: Bu bant, sembollerin (genellikle girdi verileri ve ara sonuçlar) yazılıp okunabileceği sonsuz hücrelerden oluşur.
- Okuma/Yazma Kafası: Bant üzerinde hareket ederek hücrelerdeki sembolleri okur ve yazar.
- Durum Kaydedici: Makinenin mevcut durumunu tutar. Sonlu sayıda durum bulunur.
- Geçiş Fonksiyonu: Makinenin mevcut durumu ve okunan sembole göre, hangi sembolü yazacağını, hangi yöne (sağa veya sola) hareket edeceğini ve hangi yeni duruma geçeceğini belirler.
Çalışma Prensibi:
- Makine, başlangıç durumuyla çalışmaya başlar.
- Okuma/yazma kafası, bandın üzerinde bir hücreyi okur.
- Geçiş fonksiyonu, mevcut durum ve okunan sembole göre belirlenen işlemleri yapar:
- Banttaki hücreye bir sembol yazar.
- Okuma/yazma kafasını sağa veya sola hareket ettirir.
- Yeni bir duruma geçer.
- Makine, bir "kabul" durumuna veya "reddetme" durumuna ulaşana kadar (veya sonsuza kadar) bu adımları tekrar eder.
Turing Makinesinin Önemi:
- Evrensel Hesaplama Modeli: Turing Makinesi, herhangi bir algoritmayı simüle edebilen bir evrensel hesaplama modelidir. Bu, eğer bir problem Turing Makinesi ile çözülebiliyorsa, herhangi bir modern bilgisayar tarafından da çözülebileceği anlamına gelir.
- Hesaplanabilirlik Sınırları: Turing Makinesi, hangi problemlerin çözülebileceğini (hesaplanabilir) ve hangilerinin çözülemez olduğunu (hesaplanamaz) belirlemek için kullanılır. Ünlü Durdurma Problemi Turing Makinesi ile çözülemez bir probleme örnektir.
- Modern Bilgisayarların Temeli: Turing Makinesi'nin temel prensipleri, modern bilgisayarların tasarımında ve işleyişinde hala geçerlidir.
İlgili Kavramlar: