İlkel özyinelemeli işlev

İlkel özyinelemeli işlevler , basit temel işlevlerden (sabit 0 işlevi, bir argümana yansıtma ve ardıl işlev) birleştirme ve (ilkel) özyineleme yoluyla oluşturulabilen toplam işlevlerdir . İlkel tekrarlama geri takip edilebilir Richard Dedekind içinde 126 teoremi nelerdir ve sayılar nedir? (1888). İlkel özyinelemeli aritmetik Thoralf Skolem'e (1923) kadar gider . İlkel özyinelemeli fonksiyon terimi , Macar matematikçi Rózsa Péter tarafından yapılmıştır . İlkel özyinelemeli işlevler , teorik bilgisayar biliminin bir dalı olan özyineleme kuramında rol oynar . Öngörülebilirlik kavramının açıklanmasıyla bağlantılı olarak ortaya çıkarlar .

Tüm ilkel özyinelemeli işlevler sezgisel anlamda hesaplanabilir. Bununla birlikte, sezgisel olarak hesaplanabilen tüm işlevleri tüketmezler; örnekler, her ikisi de hesaplanabilir olan ancak ilkel özyinelemeli olmayan Ackermann işlevi ve Sudan işlevidir . Hesaplanabilirlik kavramının tam olarak anlaşılması ancak µ-özyinelemeli fonksiyonlarla mümkündür .

İlkel özyinelemeli fonksiyonlar için bir karmaşıklık ölçüsü tanımlamak mümkündür, i. Yani, fonksiyon değerlerinden birinin hesaplama süresi önceden belirlenebilir.

İlkel özyinelemeli işlevlerin sınıfı ve LOOP hesaplanabilir işlevlerin sınıfı (bkz. LOOP programı ) eşdeğerdir.

tanım

1. Herhangi biri için , k basamaklı 0 işlevi ile tanımlanır .${\ displaystyle k \ in \ mathbb {N}}$ ${\ displaystyle 0 ^ {k} \ iki nokta üst üste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle 0 ^ {k} \ sol (n_ {1}, \ nokta, n_ {k} \ sağ): = 0}$
2. Bir keyfi ve bir keyfi için , i-inci parametreye k-basamaklı izdüşüm ile tanımlanır .${\ displaystyle k \ in \ mathbb {N}}$${\ displaystyle 1 \ leq ben \ leq k}$${\ displaystyle \ pi _ {i} ^ {k} \ iki nokta üst üste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle \ pi _ {i} ^ {k} \ sol (n_ {1}, \ nokta, n_ {k} \ sağ): = n_ {i}}$
3. Ardıl fonksiyonu ile tanımlanır .${\ displaystyle \ nu \ iki nokta üst üste \ mathbb {N} \ to \ mathbb {N}}$${\ displaystyle \ nu \ sol (n \ sağ): = n + 1}$
4. Herhangi biri için , bileşim bir fonksiyonu olan m fonksiyonları olan fonksiyonu olarak tanımlanan ile .${\ displaystyle k, m \ in \ mathbb {N}}$${\ displaystyle g \ iki nokta üst üste \ mathbb {N} ^ {m} \ to \ mathbb {N}}$${\ displaystyle h_ {1}, \ dots, h_ {m} \ iki nokta üst üste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ dots, h_ {m}] \ iki nokta üst üste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ dots, h_ {m}] \ sol (n_ {1}, \ dots, n_ {k} \ sağ): = g \ sol (h_ {1} \ sol (n_ {1}, \ nokta, n_ {k} \ sağ), \ nokta, h_ {m} \ sol (n_ {1}, \ nokta, n_ {k} \ sağ) \ sağ)}$
5. Herhangi biri için olduğu ilkel yineleme iki fonksiyon ve fonksiyonu olarak tanımlanan ile${\ displaystyle k \ in \ mathbb {N} \ setminus \ {0 \}}$${\ displaystyle g \ iki nokta üst üste \ mathbb {N} ^ {k-1} \ to \ mathbb {N}}$${\ displaystyle h \ iki nokta üst üste \ mathbb {N} ^ {k + 1} \ to \ mathbb {N}}$${\ displaystyle R [g, h] \ iki nokta üst üste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$

${\ displaystyle R [g, h] \ sol (n_ {1}, n_ {2}, \ dots, n_ {k} \ sağ): = {\ {durumlar} g \ sol (n_ {2}, \ noktalar, n_ {k} \ sağ) & {\ mbox {düşme}} n_ {1} = 0 \\ h \ sol (R [g, h] \ sol (n_ {1} -1, n_ {2}) , \ dots, n_ {k} \ sağ), n_ {1} -1, n_ {2}, \ dots, n_ {k} \ sağ), & {\ mbox {aksi halde}} \ son {durumlar}} }$

İlkel özyinelemeli işlevler kümesi daha sonra tüm boş işlevleri, tüm projeksiyonları ve ardıl işlevi içeren ve bileşim ve ilkel özyineleme altında kapatılan en küçük küme olarak tanımlanır. Daha gündelik terimlerle, bunun anlamı şudur: Bir işlev, ancak ve ancak belirtilen araçlar kullanılarak bir ifade olarak yazılabilirse ilkel-özyinelemelidir. İlkel-özyinelemeli olduğu zaten kanıtlanmış olan işlevler, ifadeleri eklenerek ortadan kaldırılabildikleri için ifadede görünebilir. ${\ görüntü stili Pr}$

Özellikle, her k -place ilkel özyinelemeli işlev her zaman tam olarak tanımlanır. İlkel-özyinelemeli işlevler elde etmek için , daha küçük etki alanına sahip işlevler, ilk önce uygun şekilde tam olarak sürdürülmelidir. ${\ displaystyle \ matematik {N} ^ {k}}$${\ displaystyle \ matematik {N} ^ {k}}$

Örnekler

ilave

Ekleme özyinelemeli olarak tanımlanır ${\ displaystyle + \ iki nokta üst üste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m + n = {\ start {cases} n, & {\ mbox {if}} m = 0, \\ ((m-1) + n) +1, & {\ mbox {aksi halde}} \ {durumlar}}} sona erdir$

herkes için . Bu nedenle , eklemenin ilkel-özyinelemeli olduğu doğrudur . ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle + = R [\ pi _ {1} ^ {1}, C [\ nu, \ pi _ {1} ^ {3}]]}$

çarpma işlemi

Çarpma , toplama yoluyla özyinelemeli olarak tanımlanır: ${\ displaystyle \ cdot \ iki nokta üst üste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m \ cdot n = {\ {durumlar} 0, & {\ mbox {if}} m = 0, \\ (m-1) \ cdot n + n, & {\ mbox {aksi halde}} \ {durumlar}}} sona erdir$

herkes için . Çarpma ilkel-özyinelemelidir çünkü . ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle \ cdot = R [0 ^ {1}, C [+, \ pi _ {1} ^ {3}, \ pi _ {3} ^ {3}]]}$

güç

Güç anlam çarpma yoluyla yinelemeli tanımlanır: ${\ displaystyle pot \ iki nokta üst üste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$${\ displaystyle pot (m, n) = m ^ {n}}$

${\ displaystyle pot (m, n) = {\ start {cases} 1, & {\ mbox {if}} n = 0, \\ pot (m, n-1) * m, & {\ mbox {aksi halde} } \ bitiş {durumlar}}}$

herkes için . Güç ilkel-özyinelemelidir çünkü . Buradaki bağlamın amacı , iki parametre m ve n'yi birbiriyle değiştirmektir. ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle pot = C [R [C [\ nu, 0 ^ {1}], C [*, \ pi _ {1} ^ {3}, \ pi _ {3} ^ {3}]], \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$${\ displaystyle C [\ _, \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$

öncül işlevi

Öncül fonksiyon 0 konumunda tanımlı değil. Yani ilkel özyinelemeli değildir. 0 konumunda, örneğin 0 değeriyle devam ederek, bunun dışında bir ilkel özyinelemeli işlev yapabilirsiniz.

Tarafından tanımlanan değiştirilmiş öncül işlevi${\ displaystyle p \ iki nokta üst üste \ mathbb {N} \ to \ mathbb {N}}$

${\ displaystyle p (n): = {\ {durumlar} 0, & {\ mbox {if}} n = 0, \\ n-1, & {\ mbox {aksi halde}} \ bitiş {durumlar}}}$

for all ilkel-özyinelemelidir, çünkü . ${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle p = R [0 ^ {0}, \ pi _ {2} ^ {2}]}$

çıkarma

Çıkarma da tüm doğal sayı çiftlerinde tanımlanmamıştır. Böylece, bütüne sıfırları doldurarak çıkarma işlemine devam edersiniz . Bu toplam çıkarma , özyinelemeli olarak şu şekilde karakterize edilebilir: ${\ displaystyle \ matematik {N} ^ {2}}$${\ displaystyle alt \ iki nokta üst üste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle sub (m, n) = {\ start {cases} m, & {\ mbox {if}} n = 0, \\ p (sub (m, n-1)), & {\ mbox {aksi halde }} \ bitiş {durumlar}}}$

herkes için . Toplam çıkarma için aşağıdakiler geçerlidir ; yani ilkel-özyinelemeli. Bu değiştirilmiş fark, aritmetik fark olarak da adlandırılır . ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle alt = C [R [\ pi _ {1} ^ {1}, C [p, \ pi _ {1} ^ {3}]], \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$

Diğer örnekler

• İki basamaklı fonksiyonlar ve ilkel olarak özyinelemelidir.${\ görüntü stili \ maks}$${\ görüntü stili \ dak}$
• Asal sayıların dizisi, ilkel özyinelemeli bir işlevdir.
• Bir doğal sayı ve bir asal sayı için in asal çarpanlarının sayısını bulan fonksiyon ilkel olarak özyinelemelidir.${\ görüntü stili n}$${\ görüntü stili p}$${\ görüntü stili p}$${\ görüntü stili n}$
• Doğal sayıların sonlu dizilerinin ilkel özyinelemeli aritmetik işlemleri vardır .
• Ackermann fonksiyonu ve Sudan'da işlevi olmayan ilkel yinelemeli ama olan μ-yinelemeli .
• Çalışkan Kunduzlar (meşgul kunduz) işlevi , ilkel özyinelemeli ve özyinelemeli olmayan μ- değildir .

Ayrıca bakınız

• µ özyineleme
• Turing makinesi

Edebiyat

• Hans Hermes : Numaralandırılabilirlik, karar verilebilirlik, tahmin edilebilirlik . 2. Baskı. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4 . 
• Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Matematiksel mantığa giriş . 4. baskı. Spektrum, Akademik Yayınevi, Heidelberg ve diğerleri. 1996, ISBN 3-8274-0130-5 ( üniversite ciltsiz ). 
• Arnold Oberchelp : Özyineleme Teorisi . BI-Wissenschaftlicher-Verlag, Mannheim ve ark. 1993, ISBN 3-411-16171-X . 
• Wolfgang Rautenberg : Matematiksel Mantığa Giriş . 3. Baskı. Vieweg+Teubner , Wiesbaden , ISBN 978-3-8348-0578-2 . 

Bireysel kanıt

1. ↑ Peter Schroeder-Heister , Mathematical Logic II (Gödel'in eksiklik teoremleri), senaryo, s. 39