Özyinelemeli Fonksiyonlar ve Kayıt Makineleri
Özyinelemeli fonksiyon kuramı, hesaplanabilir fonksiyonları birkaç temel işlemden inşa ederken, kayıt makineleri kayıtlarda depolanan tam sayılarla hesaplama yapmaktadır. Bu iki model, Turing makinesini çevrelemekte ve hesaplanabilirliğin sağlamlığını doğrulamaktadır.
Tanım
Genel özyinelemeli fonksiyonlar, sabitler, ardıl ve izdüşümlerden bileşim, ilkel özyineleme ve sınırsız minimizasyon yoluyla inşa edilen fonksiyonlardır; kayıt makineleri ise doğal sayıları tutan sonlu bir kayıt kümesinin içeriğini artırarak, azaltarak ve test ederek hesaplama yapan soyut cihazlardır.
Kapsam
Bu konu, ilkel özyinelemeli fonksiyonları, genel özyinelemeli fonksiyonları elde etmek için sınırsız minimizasyonun eklenmesini, ilkel özyinelemeli olmayan hesaplanabilir bir fonksiyon olarak Ackermann fonksiyonunu, kayıt ve sayaç makinelerini ve bunların evrenselliğini, ayrıca tüm bu modellerin Turing hesaplanabilirliği ile eşdeğerliğini kapsamaktadır.
Temel sorular
- Hesaplanabilir fonksiyonlar herhangi bir makine olmaksızın aritmetik olarak nasıl tanımlanabilir?
- Sınırsız minimizasyon, ilkel özyinelemenin ötesinde neden gereklidir?
- Basit kayıt makineleri, hesaplamanın tam gücüne nasıl ulaşmaktadır?
- Bu aritmetik ve makine modelleri neden Turing makineleriyle örtüşmektedir?
Temel kuramlar
- Turing hesaplanabilirliği ile Eşdeğerlik
- Genel özyinelemeli fonksiyonlar ve kayıt makineleri tarafından hesaplanan fonksiyonlar, tam olarak Turing-hesaplanabilir fonksiyonlardır; bu durum, tamamen aritmetik ve temel makine terimleriyle tanımlanan modeller aracılığıyla Church–Turing tezini pekiştirmektedir.
- İlkel Özyinelemenin Ötesi
- Ackermann fonksiyonu toplam ve hesaplanabilir olmasına rağmen, ilkel özyinelemeli olamayacak kadar hızlı büyümektedir; bu durum, sınırsız aramanın esas olduğunu ve ilkel özyinelemeli fonksiyonların hesaplanabilir olanların uygun bir alt sınıfı olduğunu göstermektedir.
- Kayıt Makinelerinin Evrenselliği
- Minsky, yalnızca iki sayacı ve artırma, azaltma ve sıfır testi işlemlerine sahip bir makinenin zaten Turing-tam olduğunu göstermiştir; bu, tam hesaplamanın ne kadar az yapı gerektirdiğinin aşırı bir göstergesidir.
Klinik önem
Kayıt makineleri, gerçek işlemcilerin tam sayı aritmetiğini bantlardan daha doğrudan modellemektedir; ilkel özyineleme, her zaman sonlanan programlara karşılık gelmekte olup, toplam fonksiyonel dillerin ve sonlandırma analizinin temelini oluşturmaktadır ve özyinelemeli fonksiyon bakış açısı, hesaplamayı matematiğin temelleriyle ilişkilendirmektedir.
Tarihçe
Gödel ve Herbrand, genel özyinelemeli fonksiyonları 1930'ların başında tanımlamış, Kleene ise minimizasyonun rolü de dahil olmak üzere kuramı geliştirmiştir. Ackermann daha önce hızlı büyüyen fonksiyonunu sergilemiş, Minsky ise 1960'larda kayıt ve sayaç makinelerini tanıtmış, hatta iki sayaçlı makinelerin bile evrensel olduğunu kanıtlamıştır.
Öne çıkan isimler
- Kurt Gödel
- Stephen Kleene
- Wilhelm Ackermann
- Marvin Minsky
İlgili konular
Temel eserler
- cutland1980
- minsky1967
Sıkça sorulan sorular
- İlkel özyinelemeli ve genel özyinelemeli fonksiyonlar arasındaki fark nedir?
- İlkel özyinelemeli fonksiyonlar, sınırlı döngüler kullanılarak inşa edilir ve her zaman sonlanır, ancak her hesaplanabilir fonksiyonu kapsamazlar. Süresiz çalışabilen bir arama olan sınırsız minimizasyonun eklenmesi, Turing-hesaplanabilir fonksiyonlarla tam olarak örtüşen genel özyinelemeli fonksiyonları verir.
- Sadece iki sayacı olan bir makine, bir bilgisayar kadar güçlü nasıl olabilir?
- Minsky, doğal sayıları tutan iki kaydın, yalnızca artırma, azaltma ve sıfır testi işlemleriyle, bir Turing makinesini bandını kayıtlara kodlayarak simüle edebileceğini göstermiştir. Yapı oldukça verimsizdir, ancak minimal donanımın bile hesaplamanın tam gücüne ulaştığını kanıtlamaktadır.