Çalışan Programcılar için Primitive Recursive Functions

Temel özyinelemeli fonksiyonlar: çalışan programcılar için bir rehber

Programcılar sık sık "Turing completeness" terimini kullanır. Bazı alanlarda Turing-tam olmamak bir erdem ya da gereklilik olarak görülebilir. Ancak tartışmaların çoğu yanlış bilgilere dayanır. Turing-tam olmamanın gerçekte ne anlama geldiği farklıdır. Turing-tamlık matematiksel bir terimdir ve çok belirli bir anlama sahiptir. Bunu başka amaçlar için yeniden yorumlamaya izin verilmez.

Part I: Özet

• Turing-tam bir dilde yazılmış bir program O(22N)'den daha hızlı çalışıyorsa, Turing-tam olmayan bir dilde de uygulanabilir.
• Pratikteki sorunların çoğu "ikinin ikinin ikisi"nden daha hızlıdır.
• Turing-tam olmayan diller pratikte bir kısıt getirmez.
• Bir programın sonlanmaması ile sonlanmasının inanılmaz derecede uzun sürmesi aynı şekilde ele alınır.

Part II: Makineler nasıl çalışır

Sonlu durum makineleri (Finite State Machines)

• Sonlu durum makineleri bir dizgeyi girdi olarak alır ve "evet" ya da "hayır" döndürür.
• Sonlu sayıda duruma sahiptir.
• Durum geçiş fonksiyonu, mevcut durumu ve sonraki girdi sembolünü alıp yeni bir durum döndürür.
• Sonlu durum makineleri sonsuz döngüye giremez.
• Sonlu durum makineleri düzenli ifadelerle aynı ifade gücüne sahiptir.

Turing makineleri (Turing Machines)

• Turing makineleri, sonlu durum makinelerinden biraz daha karmaşıktır.
• Turing makineleri değişken uzunlukta bir bant kullanarak çalışır.
• Durum geçiş fonksiyonu, mevcut durum ile bant üzerindeki mevcut sembolü alır; yeni durum, sembol ve hareket yönünü döndürür.
• Turing makineleri bir fonksiyon olarak çalışır ve sonsuz döngüye girebilir.
• Turing makineleri sonlu durum makinelerini simüle edebilir.

Turing makinelerini programlama

• Turing makineleri sonsuz bir banda sahiptir.
• Turing makineleri kullanıcı tarafından sağlanan programları çalıştırmaz. Program makineye sabit kodlanmıştır.
• Evrensel Turing makinesi başka Turing makinelerini simüle edebilir.
• Turing makineleri Python gibi dillerle aynı hesaplama gücüne sahiptir.

Turing makinelerinin sınırları

• Turing makineleriyle gerçekleştirilemeyen fonksiyonlar vardır.
• Tüm Turing makineleri listelenebilir, ancak tüm fonksiyonlar listelenemez.
• Belirli problemler (ör. durma problemi) Turing makineleriyle çözülemez.
• Turing makinelerinin gücü, bir programın sonlanıp sonlanmayacağını belirlemeyi imkansız kılar.

Part III: Pratik sorunlara geri dönüş

Temel özyinelemeli fonksiyonlar (Primitive Recursive Functions)

• Temel özyinelemeli fonksiyonlar, doğal sayı demetlerini girdi olarak alıp doğal sayı döndüren fonksiyonlardır.
• zero ve succ fonksiyonlarından başlayarak diğer fonksiyonlar oluşturulur.
• Genel özyinelemeye izin verilmez, ancak sınırlı biçimde döngülere izin verilir.
• Toplama, çarpma, üs alma gibi işlemler tanımlanabilir.
• Mantıksal işleçler ve koşullu ifadeler tanımlanabilir.
• Veri yapılarını temsil etmek için sayılar kullanılır.

GN⁺ özeti

• Bu yazı, Turing-tamlık ve temel özyinelemeli fonksiyonların anlaşılmasına yardımcı olmak için yazılmıştır.
• Turing-tam olmamanın pratikte ne anlama geldiğini açıklar.
• Sonlu durum makineleri ile Turing makineleri arasındaki farkı açıklar ve Turing makinelerinin sınırlarını tartışır.
• Temel özyinelemeli fonksiyonların tanımını ve kullanımını açıklar.
• Bu yazı, programcıların Turing-tamlık ve temel özyinelemeli fonksiyonlara dair anlayışını artırmaya yardımcı olacaktır.
• Benzer işleve sahip projeler arasında "regular expressions" ve "finite state machines" bulunur.