Ackermann işlevi - Ackermann function

İçinde hesaplanabilirlik teorisi, Ackermann işlevi, adını Wilhelm Ackermann, en basitlerinden biridir^[1] ve en erken keşfedilen örnekler Toplam hesaplanabilir işlev Bu değil ilkel özyinelemeli. Tüm ilkel özyinelemeli işlevler toplam ve hesaplanabilirdir, ancak Ackermann işlevi, tüm toplam hesaplanabilir işlevlerin ilkel özyinelemeli olmadığını gösterir. Ackermann'ın yayınından sonra^[2] (üç negatif olmayan tamsayı argümanı olan), birçok yazar onu çeşitli amaçlara uyacak şekilde değiştirdi, böylece bugün "Ackermann işlevi" orijinal işlevin çeşitli varyantlarından herhangi birine atıfta bulunabilir. Ortak bir versiyon, iki argüman Ackermann – Péter işlevi, negatif olmayan tamsayılar için aşağıdaki gibi tanımlanır m ve n:

{displaystyle {egin {dizi} {lcl} operatöradı {A} (0, n) & = & n + 1 operatöradı {A} (m + 1,0) & = & operatöradı {A} (m, 1) operatöradı { A} (m + 1, n + 1) & = & operatöradı {A} (m, operatöradı {A} (m + 1, n)) son {dizi}}}

Küçük girdiler için bile değeri hızla artar. Örneğin, Bir(4, 2) 19.729 ondalık basamaktan oluşan bir tamsayıdır^[3] (2'ye eşdeğer⁶⁵⁵³⁶−3 veya 2^{2^{2^2²}}−3).

Tarih

1920'lerin sonlarında matematikçiler Gabriel Sudan ve Wilhelm Ackermann, öğrencileri David Hilbert, hesaplamanın temellerini inceliyorlardı. Hem Sudan hem de Ackermann kredilidir^[4] keşfederek Toplam hesaplanabilir işlevler (bazı referanslarda sadece "yinelemeli" olarak adlandırılır) ilkel özyinelemeli. Sudan daha az bilinenleri yayınladı Sudan işlevi, kısa bir süre sonra ve bağımsız olarak 1928'de Ackermann işlevini yayınladı ${displaystyle varphi}$ (Yunanca mektup phi ). Ackermann'ın üç argüman işlevi, ${displaystyle varphi (m, n, p)}$ , şu şekilde tanımlanmıştır: p = 0, 1, 2, temel işlemlerini yeniden üretir ilave, çarpma işlemi, ve üs alma gibi

{displaystyle varphi (m, n, 0) = m + n,}

{displaystyle varphi (m, n, 1) = m imes n,}

{displaystyle varphi (m, n, 2) = m ^ {n},}

ve için p > 2 bu temel işlemleri, karşılaştırılabilecek bir şekilde genişletir. hiperoperasyonlar:

{displaystyle varphi (m, n, 3) = m [4] (n + 1) ,,!}

{displaystyle varphi (m, n, p) gtrapprox m [p + 1] (n + 1) {ext {, for}} p> 3.,!}

(Toplam-hesaplanabilir fakat ilkel olmayan-özyinelemeli bir işlev olarak tarihsel rolünün yanı sıra, Ackermann'ın orijinal işlevinin, Ackermann'ın işlevinin özel olarak tasarlanmış varyantları kadar sorunsuz olmasa da, temel aritmetik işlemlerini üs almanın ötesine genişlettiği görülmektedir. bu amaç - örneğin Goodstein'ın aşırı operasyon sıra.)

İçinde Sonsuzda,^[5] David Hilbert Ackermann işlevinin ilkel özyinelemeli olmadığını varsaydı, ancak Hilbert'in kişisel sekreteri ve eski öğrencisi olan Ackermann, makalesinde hipotezi kanıtladı. Hilbert'in Gerçek Sayıların İnşası Üzerine.^[2]^[6]

Rózsa Péter^[7] ve Raphael Robinson^[8] daha sonra, birçok yazar tarafından tercih edilen Ackermann işlevinin iki değişkenli bir sürümünü geliştirdi.

Genelleştirilmiş hiperoperasyon dizisi, Örneğin. ${displaystyle operatorname {G} (m, a, b) = a [m] b}$ , Ackermann işlevinin bir sürümüdür.^[9]

1963'te R.C. Buck sezgisel iki değişkenli bir varyantı (F^[10]) üzerinde hiperoperasyon dizisi:^[11]

{görüntü stili operatör adı {F} (m, n) = 2 [m] n}

.

Diğer birçok sürümle karşılaştırıldığında Buck'ın işlevinin gereksiz ofsetleri yoktur:

{displaystyle {egin {dizi} {lr} operatöradı {F} (0, n) = 2 [0] n = n + 1 operatöradı {F} (1, n) = 2 [1] n = 2 + n operatöradı {F} (2, n) = 2 [2] n = 2 imes n operatöradı {F} (3, n) = 2 [3] n = 2 ^ {n} operatöradı {F} (4, n ) = 2 [4] n = 2 ^ {2 ^ {2 ^ {{} ^ {., ^ {., ^ {., ^ {2}}}}}} ... end {dizi}} }

Tanım ve özellikler

Ackermann'ın orijinal üç argüman işlevi ${displaystyle varphi (m, n, p)}$ tanımlanmış tekrarlı negatif olmayan tamsayılar için aşağıdaki gibi m, n, ve p:

{displaystyle {egin {dizi} {lr} varphi (m, n, 0) = m + n varphi (m, 0,1) = 0 varphi (m, 0,2) = 1 varphi (m, 0 , p) = m {ext {for}} p> 2 varphi (m, n, p) = varphi (m, varphi (m, n-1, p), p-1) {ext {for}} n > 0 {harici {ve}} p> 0. son {dizi}}}

Çeşitli iki argüman versiyonlarından Péter ve Robinson tarafından geliştirilen (bazı yazarlar tarafından "Ackermann fonksiyonu olarak adlandırılır) negatif olmayan tamsayılar için tanımlanmıştır. m ve n aşağıdaki gibi:

{displaystyle {egin {dizi} {lcl} operatöradı {A} (0, n) & = & n + 1 operatöradı {A} (m + 1,0) & = & operatöradı {A} (m, 1) operatöradı { A} (m + 1, n + 1) & = & operatöradı {A} (m, A (m + 1, n)) son {dizi}}}

Değerlendirmesinin hemen belli olmayabilir. ${displaystyle A (m, n)}$ her zaman sona erer. Ancak, özyineleme sınırlıdır çünkü her özyinelemeli uygulamada ya m azalır veya m aynı kalır ve n azalır. Her seferinde n sıfıra ulaşır, m azalır, bu yüzden m sonunda da sıfıra ulaşır. (Daha teknik olarak ifade edildi, her durumda çift (m, n) içinde azalır sözlük düzeni çiftler üzerinde iyi sipariş, negatif olmayan tek tam sayıların sıralaması gibi; bu, birinin sırayla sonsuz sayıda art arda aşağı inilemeyeceği anlamına gelir.) Ancak, ne zaman m azalır ne kadar üst sınır yoktur n artabilir ve genellikle büyük ölçüde artacaktır.

Péter-Ackermann işlevi, Ackermann işlevinin çeşitli diğer sürümleriyle ilişkili olarak da ifade edilebilir:

aşırı operasyon:

{displaystyle A (m, n) = {egin {case} 0 [m] n & {ext {, if}} m = 0 2 [m] (n + 3) -3 & {ext {, if}} m> 0 end {vakalar}}}

aşırı operasyon temsil edilir Knuth'un yukarı ok gösterimi (tamsayı endekslerine genişletilmiş −2):

{displaystyle A (m, n) = {egin {case} 0uparrow ^ {m-2} n & {ext {, if}} m = 0 2uparrow ^ {m-2} (n + 3) -3 & {ext { , if}} m> 0 end {vakalar}}}

aşırı operasyon temsil edilir Conway zincirleme ok gösterimi:

{displaystyle A (m, n) = (2ightarrow (n + 3) iightarrow (m-2)) - 3}

için

{displaystyle mgeq 3}

dolayısıyla

{displaystyle 2hightarrow nightarrow m = A (m + 2, n-3) +3}

için

{displaystyle n> 2}

.

(n = 1 ve n = 2 karşılık gelecek Bir(m, −2) = −1 ve Bir(m, −1) = 1mantıksal olarak eklenebilir.)

Küçük değerler için m 1, 2 veya 3 gibi, Ackermann işlevi görece yavaş büyür n (en fazla üssel olarak ). İçin m ≥ 4ancak çok daha hızlı büyür; hatta Bir(4, 2) yaklaşık 2×10¹⁹⁷²⁸ve ondalık açılımı Bir(4, 3) herhangi bir tipik ölçüye göre çok büyüktür.

(Péter-) Ackermann işlevinin ilginç bir yönü, şimdiye kadar kullandığı tek aritmetik işlemin 1'in eklenmesi olmasıdır. Hızlı büyüyen gücü yalnızca iç içe geçmiş özyinelemeye dayanır. Bu aynı zamanda çalışma süresinin en azından çıktısıyla orantılı olduğu anlamına gelir ve bu nedenle de çok büyüktür. Gerçekte, çoğu durumda çalışma süresi çıktıdan çok daha fazladır; aşağıya bakınız.

Tek bağımsız değişkenli bir versiyon f(n) = Bir(n, n) bu ikisini de artırır m ve n aynı zamanda her ilkel özyinelemeli işlevi cüceler, örneğin çok hızlı büyüyen işlevler dahil üstel fonksiyon, faktöriyel işlev, çoklu ve yüzeysel işlevler ve hatta Knuth'un yukarı ok gösterimi kullanılarak tanımlanan işlevler (dizine alınmış yukarı ok kullanılması dışında). Görülebilir ki f(n) kabaca karşılaştırılabilir f_ω(n) içinde hızlı büyüyen hiyerarşi. Bu aşırı büyüme, bunu göstermek için kullanılabilir. fgibi sonsuz belleğe sahip bir makinede hesaplanabilir olduğu açıktır. Turing makinesi ve bu da hesaplanabilir işlev, herhangi bir ilkel özyinelemeli işlevden daha hızlı büyür ve bu nedenle ilkel özyinelemeli değildir.

Bir kategoride üstel izomorfizmi kullanarak ${displaystyle ((X imes Y) ightarrow Z) cong (Xightarrow (Yightarrow Z))}$ (bilgisayar biliminde buna denir köri ), Ackermann işlevi, aşağıdaki gibi yüksek dereceli işlevler üzerinden ilkel özyineleme yoluyla tanımlanabilir:

{displaystyle {egin {dizi} {lcl} operatorname {Ack} (0) & = & operatorname {S} operatorname {Ack} (m + 1) & = & operatorname {Iter} (operatorname {Ack} (m)) end { dizi}}}

nerede $S (n) = n + 1$ normal mi ardıl işlevi ve Iter, işlevsel güç ilkel özyineleme ile de tanımlanan işleç:

{displaystyle {egin {dizi} {lcl} operatöradı {Iter} (f) (0) & = & f (1) operatöradı {Sure} (f) (n + 1) & = & f (operatöradı {Iter} (f) (n)). son {dizi}}}

İşlev ${displaystyle mathrm {Ack}}$ bu şekilde tanımlanan Ackermann işlevi ile uyumludur ${displaystyle A}$ yukarıda tanımlanmıştır: ${displaystyle mathrm {Ack} (m) (n) = A (m, n)}$ .

Ackerman'ın dönüşünden önceki yineleme sayısı (3,3)

Örnek genişletmeler

Ackermann işlevinin nasıl bu kadar hızlı büyüdüğünü görmek için, orijinal tanımdaki kuralları kullanarak bazı basit ifadeleri genişletmeye yardımcı olur. Örneğin, tam olarak değerlendirilebilir ${displaystyle A (1,2)}$ Aşağıdaki şekilde:

{displaystyle {egin {hizalı} A (1,2) & = A (0, A (1,1)) & = A (0, A (0, A (1,0))) & = A ( 0, A (0, A (0,1))) & = A (0, A (0,2)) & = A (0,3) & = 4. uç {hizalı}}}

Nasıl olduğunu göstermek için ${displaystyle A (4, 3)}$ hesaplaması birçok adımda ve çok sayıda sonuçlanır:

{displaystyle {egin {hizalı} A (4,3) & = A (3, A (4,2)) & = A (3, A (3, A (4,1))) & = A ( 3, A (3, A (3, A (4,0)))) & = A (3, A (3, A (3, A (3,1)))) & = A (3, A (3, A (3, A (2, A (3,0))))) & = A (3, A (3, A (3, A (2, A (2,1)))) ) & = A (3, A (3, A (3, A (2, A (1, A (2,0)))))) & = A (3, A (3, A (3, A (2, A (1, A (1,1)))))) & = A (3, A (3, A (3, A (2, A (1, A (0, A (1, 0))))))) & = A (3, A (3, A (3, A (2, A (1, A (0, A (0,1))))))) & = A (3, A (3, A (3, A (2, A (1, A (0,2)))))) & = A (3, A (3, A (3, A (2, A (1,3))))) & = A (3, A (3, A (3, A (2, A (0, A (1,2)))))) & = A (3 , A (3, A (3, A (2, A (0, A (0, A (1,1))))))) & = A (3, A (3, A (3, A ( 2, A (0, A (0, A (0, A (1,0)))))))) & = A (3, A (3, A (3, A (2, A (0, A (0, A (0, A (0,1))))))) & = A (3, A (3, A (3, A (2, A (0, A (0, A ( 0,2))))))) & = A (3, A (3, A (3, A (2, A (0, A (0,3)))))) & = A (3 , A (3, A (3, A (2, A (0,4))))) & = A (3, A (3, A (3, A (2,5)))) & = ldots & = A (3, A (3, A (3,13))) & = ldots & = A (3, A (3,65533)) & = ldots & = A (3,2 ^ {65536} -3) & = ldots & = 2 ^ {2 ^ {taşan {65536} {}}} - 3. end {hizalı}}}

Değer tablosu

Ackermann işlevinin hesaplanması, sonsuz bir tablo cinsinden yeniden ifade edilebilir. İlk olarak, doğal sayıları en üst sıraya yerleştirin. Tabloda bir sayı belirlemek için, numarayı hemen sola alın. Ardından, bu numarayla verilen sütunda gerekli numarayı ve bir satır yukarı aramak için bu numarayı kullanın. Solunda numara yoksa, önceki satırdaki "1" başlıklı sütuna bakın. İşte tablonun küçük bir sol üst kısmı:

Değerleri *Bir*(m, n)
n m	0	1	2	3	4	n
0	1	2	3	4	5	${displaystyle n + 1}$
1	2	3	4	5	6	${displaystyle n + 2 = 2 + (n + 3) -3}$
2	3	5	7	9	11	${displaystyle 2n + 3 = 2cdot (n + 3) -3}$
3	5	13	29	61	125	${displaystyle 2 ^ {(n + 3)} - 3}$
4	13 ${displaystyle = {2 ^ {2 ^ {2}}} - 3}$ ${displaystyle = 2uparrow uparrow 3-3}$	65533 ${displaystyle = {2 ^ {2 ^ {2 ^ {2}}}} - 3}$ ${displaystyle = 2uparrow uparrow 4-3}$	2⁶⁵⁵³⁶ − 3 ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 5-3}$	${displaystyle {2 ^ {2 ^ {65536}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}} - 3}$ ${displaystyle = 2uparrow yukarı 6-3}$	${displaystyle {2 ^ {2 ^ {2 ^ {65536}}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 7-3}$	${displaystyle {egin {matrix} underbrace {{2 ^ {2}} ^ {{cdot} ^ {{cdot} ^ {{cdot} ^ {2}}}}} _ {n + 3} -3end {matrix} }}$ ${displaystyle = 2uparrow uparrow (n + 3) -3}$
5	65533 ${displaystyle = 2uparrow uparrow (2uparrow uparrow 2) -3}$ ${displaystyle = 2uparrow uparrow 3-3}$	${displaystyle 2uparrow uparrow 4-3}$	${displaystyle 2uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow (n + 3) -3}$
6	${displaystyle 2uparrow uparrow uparrow 3-3}$	${displaystyle 2uparrow uparrow uparrow 4-3}$	${displaystyle 2uparrow uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow uparrow (n + 3) -3}$
m	${displaystyle (2ightarrow (3) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (4) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (5) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (6) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (7) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (n + 3) ightarrow (m-2)) - 3}$

Buradaki sayılar yalnızca yinelemeli üs alma veya Knuth okları çok büyüktür ve düz ondalık rakamlarla not etmek için çok fazla yer kaplar.

Tablonun bu erken bölümünde ortaya çıkan büyük değerlere rağmen, bazı daha da büyük sayılar tanımlanmıştır. Graham'ın numarası, az sayıda Knuth okuyla yazılamaz. Bu sayı, Ackermann işlevini kendisine yinelemeli olarak uygulamaya benzer bir teknikle oluşturulmuştur.

Bu, yukarıdaki tablonun bir tekrarıdır, ancak modeli net bir şekilde göstermek için işlev tanımındaki ilgili ifadeyle değiştirilen değerler ile:

Değerleri *Bir*(m, n)
n m	0	1	2	3	4	n
0	0 + 1	1 + 1	2 + 1	3 + 1	4 + 1	n + 1
1	Bir(0, 1)	Bir(0, Bir(1, 0)) = Bir(0, 2)	Bir(0, Bir(1, 1)) = Bir(0, 3)	Bir(0, Bir(1, 2)) = Bir(0, 4)	Bir(0, Bir(1, 3)) = Bir(0, 5)	Bir(0, Bir(1, n−1))
2	Bir(1, 1)	Bir(1, Bir(2, 0)) = Bir(1, 3)	Bir(1, Bir(2, 1)) = Bir(1, 5)	Bir(1, Bir(2, 2)) = Bir(1, 7)	Bir(1, Bir(2, 3)) = Bir(1, 9)	Bir(1, Bir(2, n−1))
3	Bir(2, 1)	Bir(2, Bir(3, 0)) = Bir(2, 5)	Bir(2, Bir(3, 1)) = Bir(2, 13)	Bir(2, Bir(3, 2)) = Bir(2, 29)	Bir(2, Bir(3, 3)) = Bir(2, 61)	Bir(2, Bir(3, n−1))
4	Bir(3, 1)	Bir(3, Bir(4, 0)) = Bir(3, 13)	Bir(3, Bir(4, 1)) = Bir(3, 65533)	Bir(3, Bir(4, 2))	Bir(3, Bir(4, 3))	Bir(3, Bir(4, n−1))
5	Bir(4, 1)	Bir(4, Bir(5, 0))	Bir(4, Bir(5, 1))	Bir(4, Bir(5, 2))	Bir(4, Bir(5, 3))	Bir(4, Bir(5, n−1))
6	Bir(5, 1)	Bir(5, Bir(6, 0))	Bir(5, Bir(6, 1))	Bir(5, Bir(6, 2))	Bir(5, Bir(6, 3))	Bir(5, Bir(6, n−1))

Ackermann işlevinin ilkel özyinelemeli olmadığının kanıtı

Bir anlamda, Ackermann işlevi diğerlerinden daha hızlı büyüyor ilkel özyinelemeli işlev ve bu nedenle kendisi ilkel özyinelemeli değildir.

Özellikle, her ilkel özyinelemeli işlev için ${displaystyle f (x_ {1}, ldots, x_ {n})}$ negatif olmayan bir tam sayı var ${displaystyle t}$ öyle ki tüm negatif olmayan tamsayılar için ${displaystyle x_ {1}, ldots, x_ {n}}$ ,

{displaystyle f (x_ {1}, ldots, x_ {n})

Bu bir kez kurulduktan sonra şunu takip eder: ${displaystyle A}$ kendisi ilkel özyinelemeli değildir, çünkü aksi takdirde ${displaystyle x_ {1} = x_ {2} = t}$ çelişkiye yol açar ${displaystyle A (t, t)$ .

Kanıt^[12] aşağıdaki gibi ilerler: sınıfı tanımlayın ${displaystyle {mathcal {A}}}$ Ackermann işlevinden daha yavaş büyüyen tüm işlevlerin

{displaystyle {mathcal {A}} = sol {fmid var t for all x_ {1} cdots for all x_ {n}: f (x_ {1}, ldots, x_ {n})

ve bunu göster ${displaystyle {mathcal {A}}}$ tüm ilkel özyinelemeli işlevleri içerir. İkincisi, bunu göstererek elde edilir ${displaystyle {mathcal {A}}}$ sabit fonksiyonları, ardıl fonksiyonu, projeksiyon fonksiyonlarını ve fonksiyon kompozisyonu ve ilkel özyineleme işlemleri altında kapatıldığını içerir.

Ters

İşlevinden beri f(n) = Bir(n, n) yukarıda düşünüldüğünde çok hızlı büyür, ters fonksiyon, f⁻¹, çok yavaş büyür. Bu ters Ackermann işlevi f⁻¹ genellikle ile gösterilir α. Aslında, α(n) herhangi bir pratik giriş boyutu için 5'ten küçüktür n, dan beri Bir(4, 4) siparişinde ${displaystyle 2 ^ {2 ^ {2 ^ {2 ^ {16}}}}}$ .

Bu ters, zamanda görünür karmaşıklık bazı algoritmalar, benzeri ayrık kümeli veri yapısı ve Chazelle için algoritması minimum uzanan ağaçlar. Bazen Ackermann'ın orijinal işlevi veya diğer varyasyonları bu ayarlarda kullanılır, ancak hepsi benzer şekilde yüksek oranlarda büyür. Özellikle, bazı değiştirilmiş işlevler, −3 ve benzer terimleri ortadan kaldırarak ifadeyi basitleştirir.

Ters Ackermann fonksiyonunun iki parametreli bir varyasyonu aşağıdaki gibi tanımlanabilir, burada ${displaystyle lfloor xfloor}$ ... zemin işlevi:

{displaystyle alpha (m, n) = min {igeq 1: A (i, lfloor m / nfloor) geq log _ {2} n}.}

Bu işlev, yukarıda bahsedilen algoritmaların daha hassas analizlerinde ortaya çıkar ve daha rafine bir zaman sınırı verir. Ayrık set veri yapısında, m işlemlerin sayısını temsil eder n elemanların sayısını temsil eder; minimum yayılan ağaç algoritmasında, m kenarların sayısını temsil ederken n köşe sayısını temsil eder. α(m, n) var olmak; Örneğin, günlük₂ n bazen ile değiştirilir nve kat işlevi bazen bir tavan.

Diğer çalışmalar, m'nin sabit olarak ayarlandığı, tersi belirli bir satıra uygulanacak şekilde ters fonksiyon tanımlayabilir. ^[13]

Ackermann işlevinin tersi ilkel özyinelemelidir.^[14]

Karşılaştırma olarak kullan

Ackermann işlevi, aşırı derin özyineleme açısından tanımından dolayı, bir ölçüt olarak kullanılabilir. derleyici özyinelemeyi optimize etme yeteneği. Ackermann'ın işlevinin bu şekilde yayınlanan ilk kullanımı 1970 yılında Dragoș Vaida tarafından yapılmıştır.^[15] ve neredeyse aynı anda, 1971'de Yngve Sundblad tarafından.^[16]

Sundblad'ın ufuk açıcı makalesi Brian Wichmann ( Whetstone kıyaslama ) 1975 ve 1982 arasında yazılmış bir üçleme makalesinde.^[17]^[18]^[19]

Ayrıca bakınız

Referanslar

^ Monin ve Hinchey 2003, s. 61.
^ ^a ^b Ackermann 1928.
^ "A (4,2) 'nin ondalık açılımı". kosara.net. 27 Ağustos 2000. Arşivlenen orijinal 20 Ocak 2010.
^ Calude, Marcus ve Tevy 1979.
^ Hilbert 1926, s. 185.
^ van Heijenoort 1967.
^ Péter 1935.
^ Robinson 1948.
^ Ritchie 1965, s. 1028.
^ değiştirilmiş parametre sırası ile
^ Buck 1963.
^ Woo Chi (2009-12-17). "Ackermann işlevi ilkel özyinelemeli değildir | planetmath.org". planetmath.org. Arşivlenen orijinal 2013-05-09 tarihinde.
^ Pettie 2002.
^ Matos 2014.
^ Vaida 1970.
^ Sundblad 1971.
^ Wichmann 1976.
^ Wichmann 1977.
^ Wichmann 1982.

Kaynakça

Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007 / BF01459088.
Buck, R.C. (1963). "Matematiksel Tümevarım ve Özyinelemeli Tanımlar". American Mathematical Monthly. 70 (2): 128–135. doi:10.2307/2312881.
Calude, Cristian; Marcus, Solomon; Tevy, Ionel (Kasım 1979). "İlkel özyinelemeli olmayan özyinelemeli işlevin ilk örneği". Historia Math. 6 (4): 380–84. doi:10.1016/0315-0860(79)90024-7.
van Heijenoort, Jean (1967). Frege'den Gödel'e: Matematiksel Mantıkta Bir Kaynak Kitap, 1879–1931. Harvard Üniversitesi Yayınları.
Hilbert, David (1926). "Über das Unendliche". Mathematische Annalen. 95: 161–190. doi:10.1007 / BF01206605.
Matos, Armando B (7 Mayıs 2014). "Ackermann işlevinin tersi ilkel özyinelemelidir" (PDF).
Monin, Jean-Francois; Hinchey, M. G. (2003). Biçimsel Yöntemleri Anlamak. Springer. s. 61. ISBN 9781852332471.
Péter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Mathematische Annalen. 111: 42–60. doi:10.1007 / BF01472200.
Pettie, S. (2002). "Çevrimiçi minimum yayılma ağacı doğrulama sorunu için ters Ackermann tarzı bir alt sınır". Bilgisayar Biliminin Temelleri üzerine 43. Yıllık IEEE Sempozyumu, 2002. Bildiriler: 155–163. doi:10.1109 / SFCS.2002.1181892.
Ritchie, Robert Wells (Kasım 1965). "Ackermann'ın işlevine dayalı yinelemeli işlev sınıfları". Pacific Journal of Mathematics. 15 (3): 1027–1044. doi:10.2140 / pjm.1965.15.1027.
Robinson, Raphael M. (1948). "Özyineleme ve Çift Özyineleme". Amerikan Matematik Derneği Bülteni. 54 (10): 987–93. doi:10.1090 / S0002-9904-1948-09121-2.
Sundblad, Yngve (Mart 1971). "Ackermann işlevi. Teorik, hesaplamalı ve formül manipülatif bir çalışma". BIT Sayısal Matematik. 11 (1): 107–119. doi:10.1007 / BF01935330.
Vaida, Dragoș (1970). "Algol Benzeri Dil için Derleyici Doğrulaması". Bulletin Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie, Nouvelle Série. 14 (60) (4): 487–502. JSTOR 43679758.
Wichmann, Brian A. (Mart 1976). "Ackermann'ın işlevi: Arama prosedürlerinin verimliliği üzerine bir çalışma". BIT Sayısal Matematik. 16: 103–110. doi:10.1007 / BF01940783.
Wichmann, Brian A. (Temmuz 1977). "Ackermann'ın işlevi hakkında prosedürler veya ikinci düşünceler nasıl çağırılır". BIT Sayısal Matematik. 16: 103–110. doi:10.1002 / spe.4380070303.
Wichmann, Brian A. (Temmuz 1982). "Ackermann'ın işlevi olan prosedür çağırma testinden en son sonuçlar" (PDF).

Dış bağlantılar

"Ackermann işlevi". Matematik Ansiklopedisi. EMS Basın. 2001 [1994].
Weisstein, Eric W. "Ackermann işlevi". MathWorld.
Bu makale içerir kamu malı materyal -denNIST belge:Siyah, Paul E. "Ackermann'ın işlevi". Algoritmalar ve Veri Yapıları Sözlüğü.
Animasyonlu bir Ackermann fonksiyon hesaplayıcısı
Scott Aaronson, En büyük sayıyı kim söyleyebilir? (1999)
Ackermann fonksiyonları. Bazı değerlerin bir tablosunu içerir.
Hiper işlemler: Ackermann'ın İşlevi ve Yeni Aritmetik İşlem
Robert Munafo'nun Büyük Sayıları tanımının çeşitli varyasyonlarını tanımlar Bir.
Gabriel Nivasch, Ackermann tersine ağrısız ters Ackermann fonksiyonu üzerinde.
Raimund Seidel, Ters Ackermann fonksiyonunu anlama (PDF sunumu).
Ackermann işlevi farklı programlama dillerinde yazılmıştır, (açık Rosetta Kodu )
Ackermann'ın İşlevi (Arşivlendi 2009-10-24) —Harry J. Smith tarafından bazı çalışma ve programlama.

[FOOTNOTEMoninHinchey200361-1] Monin ve Hinchey 2003, s. 61.

[FOOTNOTEAckermann1928-2] Ackermann 1928.

[3] "A (4,2) 'nin ondalık açılımı". kosara.net. 27 Ağustos 2000. Arşivlenen orijinal 20 Ocak 2010.

[FOOTNOTECaludeMarcusTevy1979-4] Calude, Marcus ve Tevy 1979.

[FOOTNOTEHilbert1926185-5] Hilbert 1926, s. 185.

[FOOTNOTEvan_Heijenoort1967-6] van Heijenoort 1967.

[FOOTNOTEPéter1935-7] Péter 1935.

[FOOTNOTERobinson1948-8] Robinson 1948.

[FOOTNOTERitchie19651028-9] Ritchie 1965, s. 1028.

[10] ğiştirilmiş parametre sırası ile

[FOOTNOTEBuck1963-11] Buck 1963.

[12] Woo Chi (2009-12-17). "Ackermann işlevi ilkel özyinelemeli değildir | planetmath.org". planetmath.org. Arşivlenen orijinal 2013-05-09 tarihinde.

[FOOTNOTEPettie2002-13] Pettie 2002.

[FOOTNOTEMatos2014-14] Matos 2014.

[FOOTNOTEVaida1970-15] Vaida 1970.

[FOOTNOTESundblad1971-16] Sundblad 1971.

[FOOTNOTEWichmann1976-17] Wichmann 1976.

[FOOTNOTEWichmann1977-18] Wichmann 1977.

[FOOTNOTEWichmann1982-19] Wichmann 1982.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

Hiper operasyonlar
Birincil	Halef (0) Ekleme (1) Çarpma (2) Üs alma (3) Tetrasyon (4) Pentasyon (5)
Sol argüman için ters	Çıkarma (1) Bölüm (2) ninci kök (3) Süper kök (4)
Doğru argüman için ters	Çıkarma (1) Bölüm (2) Logaritma (3) Süper logaritma (4)
İlgili Makaleler	Ackermann işlevi Conway zincirleme ok gösterimi Grzegorczyk hiyerarşisi Knuth'un yukarı ok gösterimi Steinhaus-Moser gösterimi