WikiDer > Smn teoremasi - Vikipediya

Yilda hisoblash nazariyasi The S m
n  teorema, (deb ham nomlanadi tarjima lemmasi, parametr teoremasi, va parametrlash teoremasi) haqida asosiy natijadir dasturlash tillari (va umuman, Gödel raqamlari ning hisoblash funktsiyalari) (Soare 1987, Rogers 1967). Bu birinchi marta isbotlangan Stiven Koul Klayn (1943). Ism S m
n  ning paydo bo'lishidan kelib chiqadi S pastki yozuv bilan n va yuqori harf m teoremaning asl formulasida (pastga qarang).

Amaliy ma'noda, teorema ma'lum bir dasturlash tili va musbat butun sonlar uchun aytiladi m va n, ma'lum bir narsa mavjud algoritm kirish sifatida qabul qiladi manba kodi bilan dasturning m + n erkin o'zgaruvchilarbilan birga m qiymatlar. Ushbu algoritm dastlabki qiymatlarni samarali tarzda almashtiradigan manba kodini yaratadi m qolgan o'zgaruvchilarni bo'sh qoldirib, erkin o'zgaruvchilar.

Tafsilotlar

Teoremaning asosiy shakli ikkita argumentning funktsiyalariga taalluqlidir (Nies 2009, 6-bet). Gödel raqami berilgan ${ displaystyle varphi}$ rekursiv funktsiyalar, a mavjud ibtidoiy rekursiv funktsiya s quyidagi xususiyatga ega ikkita argument: har bir Gödel raqami uchun p qisman hisoblanadigan funktsiya f ikkita dalil, iboralar bilan ${ displaystyle varphi _ {s (p, x)} (y)}$ va ${ displaystyle f (x, y)}$ natural sonlarning bir xil birikmalari uchun aniqlanadi x va yva ularning qiymatlari har qanday bunday kombinatsiya uchun tengdir. Boshqacha qilib aytganda, quyidagilar kengaytirilgan tenglik funktsiyalar har biriga mos keladi x:

${ displaystyle varphi _ {s (p, x)} simeq lambda y. varphi _ {p} (x, y).}$

Umuman olganda, har qanday kishi uchun m, n > 0, ibtidoiy rekursiv funktsiya mavjud ${ displaystyle S_ {n} ^ {m}}$ ning m + 1 argumenti quyidagicha ishlaydi: har bir Gödel raqami uchun p bilan qisman hisoblanadigan funktsiyaning m + n argumentlari va ning barcha qiymatlari x₁, …, x_m:

${ displaystyle varphi _ {S_ {n} ^ {m} (p, x_ {1}, nuqtalar, x_ {m})} simeq lambda y_ {1}, nuqtalar, y_ {n}. varphi _ {p} (x_ {1}, nuqta, x_ {m}, y_ {1}, nuqta, y_ {n}).}$

Funktsiya s yuqorida tavsiflangan bo'lishi mumkin ${ displaystyle S_ {1} ^ {1}}$.

Rasmiy bayonot

Aritalar berilgan ${ displaystyle m}$ va ${ displaystyle n}$, har bir Turing mashinasi uchun ${ displaystyle { text {TM}} _ {x}}$ arity ${ displaystyle m + n}$ va kirishning barcha mumkin bo'lgan qiymatlari uchun ${ displaystyle y_ {1}, nuqtalar, y_ {m}}$, Turing mashinasi mavjud ${ displaystyle { text {TM}} _ {k}}$ arity ${ displaystyle n}$, shu kabi

${ displaystyle forall z_ {1}, dots, z_ {n}: { text {TM}} _ {x} (y_ {1}, dots, y_ {m}, z_ {1}, dots , z_ {n}) = { text {TM}} _ {k} (z_ {1}, dots, z_ {n}).}$

Bundan tashqari, Turing mashinasi mavjud ${ displaystyle S}$ bu imkon beradi ${ displaystyle k}$ dan hisoblash kerak ${ displaystyle x}$ va ${ displaystyle y}$; u belgilanadi ${ displaystyle k = S_ {n} ^ {m} (x, y_ {1}, nuqtalar, y_ {m})}$.

Norasmiy, ${ displaystyle S}$ Turing mashinasini topadi ${ displaystyle { text {TM}} _ {k}}$ bu qiymatlarini qattiq kodlash natijasidir ${ displaystyle y}$ ichiga ${ displaystyle { text {TM}} _ {x}}$. Natija hamma uchun umumlashtiriladi Turing to'liq hisoblash modeli.

Misol

Quyidagi Lisp kodni amalga oshiradi₁₁ Lisp uchun.

 (bekor qilish s11 (f x)   (ruxsat bering ((y (gensim)))     (ro'yxat 'lambda (ro'yxat y) (ro'yxat f x y))))

Masalan, (s11 '(lambda (x y) (+ x y)) 3) ga baho beradi (lambda (g42) ((lambda (x y) (+ x y)) 3 g42)).

Shuningdek qarang

• Koriing
• Klaynning rekursion teoremasi
• Qisman baholash

Adabiyotlar

• Kleene, S. C. (1936). "Natural sonlarning umumiy rekursiv funktsiyalari". Matematik Annalen. 112 (1): 727–742. doi:10.1007 / BF01565439.
• Kleene, S. C. (1938). "Oddiy raqamlar uchun yozuvlar to'g'risida" (PDF). The Symbolic Logic jurnali. 3: 150–155. (Bu Odifreddining "Klassik rekursiya nazariyasi" ning 1989 yildagi nashrida 131-betda berilgan. ${ displaystyle S_ {n} ^ {m}}$ teorema.)
• Nies, A. (2009). Hisoblash va tasodifiylik. Oksford mantiqiy qo'llanmalari. 51. Oksford: Oksford universiteti matbuoti. ISBN 978-0-19-923076-1. Zbl 1169.03034.
• Odifreddi, P. (1999). Klassik rekursiya nazariyasi. Shimoliy-Gollandiya. ISBN 0-444-87295-7.
• Rogers, H. (1987) [1967]. Rekursiv funktsiyalar nazariyasi va samarali hisoblash. MIT matbuotining birinchi qog'ozli nashri. ISBN 0-262-68052-1.
• Soare, R. (1987). Rekursiv ravishda sanab o'tilgan to'plamlar va darajalar. Matematik mantiqning istiqbollari. Springer-Verlag. ISBN 3-540-15299-7.

Tashqi havolalar

• Vayshteyn, Erik V. "Kleinniki s-m-n Teorema ". MathWorld.