Kleene'nin özyineleme teoremi - Kleene's recursion theorem

In Hesaplama teorisi , Kleene'nin tekrarlama teoremleri uygulanması konusunda temel sonuçlarının bir çift olan hesaplanabilir fonksiyonlar kendi açıklamalara. Teoremler ilk olarak 1938'de Stephen Kleene tarafından kanıtlandı ve 1952'de Metamathematics'e Giriş kitabında yer aldı . Hesaplanabilir bir fonksiyonun sabit noktalarını oluşturan ilgili bir teorem, Rogers teoremi olarak bilinir ve Hartley Rogers, Jr.'dan kaynaklanır .

Özyineleme teoremleri, hesaplanabilir işlevler üzerinde belirli işlemlerin sabit noktalarını oluşturmak, quines oluşturmak ve özyinelemeli tanımlarla tanımlanan işlevleri oluşturmak için uygulanabilir .

gösterim

Teoremlerin ifadesi, ifade etmektedir kabul edilebilir numaralandırma ait kısmi yinelemeli fonksiyonları , indeksine karşılık gelen fonksiyonu şu şekilde olup . ${\görüntüleme stili \varphi }$${\görüntüleme stili e}$${\displaystyle \varphi _{e}}$

Eğer ve vardır kısmi fonksiyonlar doğal sayılar, gösterim belirtir, her biri için n ya ve hem de tanımlandığı gibidir ve eşit ya da başka olan edilir ve her iki tanımlanmamıştır. ${\görüntüleme stili F}$${\görüntüleme stili G}$${\ Displaystyle F\simeq G}$${\görüntüleme stili F(n)}$${\görüntüleme stili G(n)}$${\görüntüleme stili F(n)}$${\görüntüleme stili G(n)}$

Rogers'ın sabit nokta teoremi

Bir fonksiyon Verilen bir sabit nokta arasında bir endeks olup şekildedir . Rogers, aşağıdaki sonucu Kleene'nin (ikinci) özyineleme teoreminin "daha basit bir versiyonu" olarak tanımlar. ${\görüntüleme stili F}$${\görüntüleme stili F}$${\görüntüleme stili e}$${\displaystyle \varphi _{e}\simeq \varphi _{F(e)}}$

Rogers'ın sabit nokta teoremi . Eğer toplam hesaplanabilir fonksiyonudur, sabit bir nokta vardır.${\görüntüleme stili F}$

Sabit nokta teoreminin ispatı

Kanıt , aşağıdaki gibi tanımlanan belirli bir toplam hesaplanabilir işlevi kullanır . Doğal bir sayı verildiğinde , işlev , aşağıdaki hesaplamayı gerçekleştiren kısmi hesaplanabilir işlevin indeksini verir: ${\görüntüleme stili h}$${\görüntüleme stili x}$${\görüntüleme stili h}$

Bir girdi verildiğinde , önce hesaplamayı deneyin . Bu hesaplama bir çıktı döndürürse , hesaplayın ve varsa değerini döndürün .${\görüntüleme stili y}$${\görüntüleme stili\varphi _{x}(x)}$${\görüntüleme stili e}$${\displaystyle \varphi _{e}(y)}$

Bu nedenle, kısmi hesaplanabilir fonksiyonların tüm indeksleri için , tanımlanmışsa, o zaman . Eğer tanımlı değil, o zaman hiçbir yerde tanımlanmış bir fonksiyondur. İşlev kısmi hesaplanabilir fonksiyon imal edilebilir ve yukarıda tarif edilen smn teoremi : her biri için , fonksiyon hesaplayan bir programın endeksidir . ${\görüntüleme stili x}$${\görüntüleme stili\varphi _{x}(x)}$${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$${\görüntüleme stili\varphi _{x}(x)}$${\displaystyle \varphi _{h(x)}}$${\görüntüleme stili h}$${\görüntüleme stili g(x,y)}$${\görüntüleme stili x}$${\görüntüleme stili h(x)}$${\displaystyle y\mapsto g(x,y)}$

İspatı tamamlamak için, herhangi bir toplam hesaplanabilir fonksiyon olsun ve yukarıdaki gibi inşa edin. Toplam hesaplanabilir bir fonksiyon olan kompozisyonun bir indeksi olsun . Daha sonra tanımına göre . Ancak, çünkü bir dizini , , ve dolayısıyla . geçişliliği ile , bu demektir . Bu nedenle için . ${\görüntüleme stili F}$${\görüntüleme stili h}$${\görüntüleme stili e}$${\ Displaystyle F\circ h}$${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$${\görüntüleme stili h}$${\görüntüleme stili e}$${\ Displaystyle F\circ h}$${\displaystyle \varphi _{e}(e)=(F\circ h)(e)}$${\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}}$${\görüntüleme stili \simeq }$${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$${\görüntüleme stili n=h(e)}$

Bu ispat, Y birleştiricisini uygulayan kısmi özyinelemeli bir fonksiyonun yapısıdır .

Sabit nokta içermeyen fonksiyonlar

Bir fonksiyon , öyle ki tüm adlandırılan sabit nokta serbest . Sabit nokta teoremi, toplam hesaplanabilir fonksiyonun sabit noktadan bağımsız olmadığını, ancak hesaplanamayan birçok sabit noktadan bağımsız fonksiyon olduğunu gösterir. Arslanov'un tamlık kriteri , sabit noktadan bağımsız bir fonksiyonu hesaplayan yinelemeli olarak numaralandırılabilen tek Turing derecesinin , durma probleminin derecesi olan 0' olduğunu belirtir . ${\görüntüleme stili F}$${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$${\görüntüleme stili e}$

Kleene'nin ikinci özyineleme teoremi

İkinci özyineleme teoremi, Rogers teoreminin fonksiyonda ikinci bir girdiyle genelleştirilmiş halidir. İkinci özyineleme teoreminin resmi olmayan bir yorumu, kendine referanslı programlar oluşturmanın mümkün olduğudur; aşağıdaki "Quines'e başvuru" bölümüne bakın.

İkinci özyineleme teoremi . Herhangi bir kısmi özyinelemeli işlev için öyle bir dizin vardır ki .${\görüntüleme stili Q(x,y)}$${\görüntüleme stili p}$${\displaystyle \varphi _{p}\simeq \lambda yQ(p,y)}$

Teorem, Rogers'ın teoreminden, şöyle bir fonksiyon olmasına izin verilerek kanıtlanabilir ( Smn teoremi tarafından açıklanan bir yapı ). Daha sonra bunun sabit bir noktasının gerektiği gibi bir dizin olduğu doğrulanabilir . Teorem, sabit bir hesaplanabilir fonksiyonun Q için bir indeksi p indeksine eşlemesi anlamında yapıcıdır . ${\görüntüleme stili F(p)}$${\displaystyle \varphi _{F(p)}(y)=Q(p,y)}$${\görüntüleme stili F}$${\görüntüleme stili p}$

Rogers teoremi ile karşılaştırma

Kleene'nin ikinci özyineleme teoremi ve Rogers'ın teoremi birbirinden oldukça basit bir şekilde kanıtlanabilir. Bununla birlikte, Kleene teoreminin doğrudan bir kanıtı evrensel bir programı kullanmaz; bu, teoremin evrensel bir programı olmayan belirli özyinelemeli programlama sistemleri için geçerli olduğu anlamına gelir.

Quines'a başvuru

İkinci özyineleme teoremini kullanan klasik bir örnek, fonksiyondur . Bu durumda karşılık gelen indeks , herhangi bir değere uygulandığında kendi indeksini veren hesaplanabilir bir fonksiyon verir. Bilgisayar programları olarak ifade edildiğinde, bu tür indeksler quines olarak bilinir . ${\görüntüleme stili Q(x,y)=x}$${\görüntüleme stili p}$

Aşağıdaki örnek Lisp'te verilmektedir doğal sonucu olarak etkin bir işlev elde edilebilir . İşlev kodunu tarafından üretilen adı fonksiyonudur SMN teoremi . ${\görüntüleme stili p}$${\ ekran stili Q}$s11

Q herhangi bir iki argümanlı fonksiyona değiştirilebilir.

(setq Q '(lambda (x y) x))
(setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y))))
(setq n (list 'lambda '(x y) (list Q (list s11 'x 'x) 'y)))
(setq p (eval (list s11 n n)))

Aşağıdaki ifadelerin sonuçları aynı olmalıdır. ${\görüntüleme stili \varphi }$ p(nil)

(eval (list p nil))

Q(p, nil)

(eval (list Q p nil))

Özyinelemeyi ortadan kaldırmak için başvuru

Varsayalım ki ve bir işlev için yinelemeli bir tanımı kullanılan toplam hesaplanabilir fonksiyonlardır : ${\görüntüleme stili g}$${\görüntüleme stili h}$${\görüntüleme stili f}$

${\görüntüleme stili f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

İkinci özyineleme teoremi, bu tür denklemlerin hesaplanabilir bir işlevi tanımladığını göstermek için kullanılabilir; burada hesaplanabilirlik kavramı, ilk bakışta özyinelemeli tanımlara izin vermek zorunda değildir (örneğin, μ-özyineleme veya Turing tarafından tanımlanabilir). makineler ). Bu özyinelemeli tanım, özyinelemeyi simüle etmek için kendisine bir dizin olduğunu varsayan hesaplanabilir bir işleve dönüştürülebilir : ${\displaystyle \varphi _{F}(e,x,y)}$${\görüntüleme stili e}$

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

Yineleme teoremi hesaplanabilir fonksiyon varlığını belirler , öyle ki . Böylece verilen özyinelemeli tanımı karşılar. ${\displaystyle \varphi _{f}}$${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$${\görüntüleme stili f}$

yansımalı programlama

Yansıtıcı veya yansıtıcı programlama, programlarda kendi kendine referans kullanımını ifade eder. Jones, dönüşlü bir dile dayalı ikinci özyineleme teoreminin bir görünümünü sunar. Tanımlanan yansımalı dilin yansımasız bir dilden daha güçlü olmadığı gösterilmiştir (çünkü yansımalı dil için bir yorumlayıcı yansıma kullanılmadan uygulanabilir); daha sonra, özyineleme teoreminin dönüşlü dilde neredeyse önemsiz olduğu gösterilmiştir.

İlk özyineleme teoremi

İkinci özyineleme teoremi hesaplanabilir fonksiyonların sabit noktaları ile ilgiliyken, birinci özyineleme teoremi, endüktif tanımların hesaplanabilir bir analogu olan numaralandırma operatörleri tarafından belirlenen sabit noktalarla ilgilidir. Bir numaralandırma operatörü , A'nın bir ( a için kod ) sonlu sayılar kümesi ve n'nin tek bir doğal sayı olduğu bir çiftler ( A , n ) kümesidir . Genellikle, n , özellikle işlevler numaralandırma operatörleri aracılığıyla tanımlandığında, sıralı bir doğal sayı çifti için bir kod olarak görülecektir. Numaralandırma operatörleri, numaralandırma indirgenebilirliği çalışmasında merkezi öneme sahiptir .

Her numaralandırma operatörü Φ, doğal kümelerden doğal kümelere kadar bir işlevi belirler.

${\displaystyle \Phi (X)=\{n\mid \var A\subseteq X[(A,n)\in \Phi ]\}.}$

Bir yinelemeli operatör kısmi özyinelemeli fonksiyon grafiği verildiğinde, her bir kısmi özyinelemeli fonksiyon grafiği döndüren bir numaralandırma operatördür.

Bir numaralandırma operatör cp sabit bir nokta bir dizi F şekilde Φ ( K ) = F . İlk numaralandırma teoremi, numaralandırma operatörünün kendisi hesaplanabilirse, sabit noktaların etkin bir şekilde elde edilebileceğini gösterir.

Birinci özyineleme teoremi . Aşağıdaki ifadeler geçerlidir.

1. Herhangi bir hesaplanabilir numaralandırma operatörü Φ için , Φ( F ) = F ve F bu özelliğe sahip en küçük küme olacak şekilde yinelemeli olarak numaralandırılabilir bir F kümesi vardır.
2. Herhangi bir özyinelemeli operatör Ψ için, Ψ(φ) = φ ve φ bu özelliğe sahip en küçük kısmi hesaplanabilir fonksiyon olacak şekilde kısmi hesaplanabilir bir fonksiyon φ vardır.

Örnek

İkinci özyineleme teoremi gibi, birinci özyineleme teoremi de özyineleme denklem sistemlerini sağlayan fonksiyonları elde etmek için kullanılabilir. Birinci özyineleme teoremini uygulamak için, özyineleme denklemleri önce özyinelemeli bir operatör olarak yeniden oluşturulmalıdır.

İçin yineleme denklemlerini düşünün faktöryel fonksiyonu f :

${\görüntüleme stili f(0)=1}$

${\displaystyle f(n+1)=(n+1)\cdot f(n)}$

İlgili özyinelemeli operatör Φ , önceki değerden bir sonraki f değerine nasıl ulaşılacağını söyleyen bilgiye sahip olacaktır . Bununla birlikte, özyinelemeli operatör aslında f'nin grafiğini tanımlayacaktır . İlk olarak, Φ çiftini içerecektir . Bu, f (0)'ın kesinlikle 1 olduğunu ve dolayısıyla (0,1) çiftinin f'nin grafiğinde olduğunu gösterir . ${\görüntüleme stili (\varnothing ,(0,1))}$

Ardından, her n ve m için Φ çiftini içerecektir . Bu, f ( n ) m ise , f ( n  + 1)'nin ( n  + 1) m olduğunu , yani ( n  + 1, ( n  + 1) m ) çiftinin f'nin grafiğinde olduğunu gösterir . Temel durum f (0) = 1'den farklı olarak, özyinelemeli operatör , f ( n  + 1) değerini tanımlamadan önce f ( n ) hakkında bazı bilgilere ihtiyaç duyar . ${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$

Birinci yineleme teoremi (özellikle, bölüm 1) bir dizi olduğunu bildiren F Φ (şekilde F ) = F. set F doğal sayılar sıralı çiftlerinin tamamen oluşacak, ve faktör fonksiyon grafiği olacak f , istediğiniz gibi.

Özyinelemeli operatörler olarak yeniden biçimlendirilebilecek özyineleme denklemlerinin kısıtlaması, özyineleme denklemlerinin gerçekte en az sabit bir nokta tanımlamasını sağlar. Örneğin, özyineleme denklemleri kümesini göz önünde bulundurun:

${\görüntüleme stili g(0)=1}$

${\displaystyle g(n+1)=1}$

${\görüntüleme stili g(2n)=0}$

Bu denklemleri sağlayan bir g fonksiyonu yoktur , çünkü bunlar g (2) = 1 ve ayrıca g (2) = 0 anlamına gelir. Dolayısıyla, bu özyineleme denklemlerini sağlayan sabit bir g noktası yoktur . Bu denklemlere karşılık gelen bir numaralandırma operatörü yapmak mümkündür, ancak özyinelemeli bir operatör olmayacaktır.

İlk özyineleme teoremi için kanıt taslağı

Birinci özyineleme teoreminin 1. bölümünün kanıtı, boş kümeden başlayarak numaralandırma operatörü Φ yinelenerek elde edilir. İlk olarak, için bir F _k dizisi oluşturulur . Let F ₀ boş kümeden farklı olması. Her biri için, indüktif ilerlenerek k , let F _{k + 1} olmak . Son olarak, F olarak alınır . İspatın geri kalanı, F'nin yinelemeli olarak sayılabilir ve Φ'nin en az sabit noktası olduğunun bir doğrulamasından oluşur . Bu ispatta kullanılan F _k dizisi , Kleene sabit nokta teoreminin ispatındaki Kleene zincirine karşılık gelir . ${\displaystyle k=0,1,\ldots }$${\displaystyle F_{k}\cup \Phi (F_{k})}$${\displaystyle \bigcup F_{k}}$

Birinci özyineleme teoreminin ikinci kısmı, birinci kısımdan sonra gelir. Φ'nin özyinelemeli bir operatör olduğu varsayımı, Φ'nin sabit noktasının bir kısmi fonksiyonun grafiği olduğunu göstermek için kullanılır. Kilit nokta şudur ki, sabit F noktası bir fonksiyonun grafiği değilse, o zaman bazı k vardır, öyle ki F _k bir fonksiyonun grafiği değildir.

İkinci özyineleme teoremi ile karşılaştırma

İkinci özyineleme teoremi ile karşılaştırıldığında, ilk özyineleme teoremi daha güçlü bir sonuç üretir, ancak yalnızca daha dar hipotezler karşılandığında. Rogers , birinci yineleme teoremi için zayıf yineleme teoremi ve ikinci yineleme teoremi için güçlü yineleme teoremi terimini kullanır .

Birinci ve ikinci özyineleme teoremleri arasındaki bir fark, birinci özyineleme teoremi tarafından elde edilen sabit noktaların en az sabit noktalar olması garanti edilirken, ikinci özyineleme teoreminden elde edilenlerin en az sabit noktalar olmayabilmesidir.

İkinci bir fark, birinci özyineleme teoreminin yalnızca özyinelemeli operatörler olarak yeniden biçimlendirilebilen denklem sistemleri için geçerli olmasıdır. Bu kısıtlama, sürekli operatörlere sınırlama benzer Kleene sabit noktalı teoremi bir sipariş teorisi . İkinci özyineleme teoremi, herhangi bir toplam özyinelemeli işleve uygulanabilir.

genelleştirilmiş teorem

Numaralandırma teorisi bağlamında, Ershov , Kleene'nin özyineleme teoreminin herhangi bir önceden tamamlanmış numaralandırma için geçerli olduğunu gösterdi . Bir Gödel numaralandırması, hesaplanabilir fonksiyonlar kümesi üzerinde önceden tamamlanmış bir numaralandırmadır, bu nedenle genelleştirilmiş teorem, özel bir durum olarak Kleene özyineleme teoremini verir.

Önceden tamamlanmış bir numaralandırma verildiğinde , iki parametreli herhangi bir kısmi hesaplanabilir fonksiyon için , bir parametreli toplam hesaplanabilir fonksiyon vardır , öyle ki, ${\görüntüleme stili \nu }$${\görüntüleme stili f}$${\görüntüleme stili t}$

${\displaystyle \forall n\in \mathbb {N} :\nu \circ f(n,t(n))=\nu \circ t(n).}$

Ayrıca bakınız

• Birinci özyineleme teoremi ile aynı amaç için en az sabitlenmiş başka bir nokta teoreminin kullanıldığı düz anlambilim .
• İlk özyineleme teoremi ile aynı amaç için lambda hesabında kullanılan sabit nokta birleştiriciler .

Referanslar

• Ershov, Yuri L. (1999). "Bölüm 4: Matematik ve Hesaplanabilirlik Teorisi. 14. Numaralandırma Teorisi". Griffor'da Edward R. (ed.). Hesaplanabilirlik Teorisi El Kitabı . Mantık çalışmaları ve matematiğin temelleri. 140 . Amsterdam: Elsevier . s. 473-503. ISBN'si 9780444898821. OCLC  162130533 . Erişim tarihi: 6 Mayıs 2020 .
• Jones, Neil D. (1997). Hesaplanabilirlik ve karmaşıklık: Programlama Perspektifinden . Cambridge, Massachusetts : MIT Basını . ISBN'si 9780262100649. OCLC  981293265 .
• Kleene, Stephen C. (1952). Metamatematiğe Giriş . Bibliotheca Mathematica. Kuzey Hollanda Yayıncılık . ISBN'si 9780720421033. OCLC  459805591 . Erişim tarihi: 6 Mayıs 2020 .
• Rogers, Hartley (1967). Özyinelemeli fonksiyonlar teorisi ve etkin hesaplanabilirlik . Cambridge, Massachusetts : MIT Basını . ISBN'si 9780262680523. OCLC  933975989 . Erişim tarihi: 6 Mayıs 2020 .

Dipnotlar

daha fazla okuma

• Jockusch, CG ; Lerman, M.; Soare, RI ; Solovay, RM (1989). "Arslanov'un tamlık kriterinin modülo yinelenen atlamaları ve uzantıları yinelemeli olarak numaralandırılabilir kümeler". Sembolik Mantık Dergisi . 54 (4): 1288-1323. doi : 10.1017/S0022481200041104 . ISSN  0022-4812 . JSTOR  2274816 .

Dış bağlantılar

• "Yinelemeli Fonksiyonlar" tarafından giriş Piergiorgio Odifreddi içinde Felsefe Stanford Encyclopedia 2012.