Chegarada hisoblash - Computation in the limit

Yilda hisoblash nazariyasi, funktsiya deyiladi limitni hisoblash mumkin agar bu teng ravishda hisoblanadigan funktsiyalar ketma-ketligining chegarasi bo'lsa. Shartlar chegarada hisoblash mumkin, limit rekursiv va rekursiv ravishda taxminiy ham ishlatiladi. Hisoblanadigan funktsiyalarni haqiqiy qiymati bo'yicha oxir-oqibat to'g'ri hisoblash protsedurasini tan oladiganlar deb hisoblash mumkin. To'plam, agar u bo'lsa, uni hisoblash mumkin xarakterli funktsiya chegara hisoblanadi.

Agar ketma-ketlik nisbatan bir xil hisoblansa D., keyin funktsiya limit in input D..

Rasmiy ta'rif

A umumiy funktsiya ${ displaystyle r (x)}$ a mavjud bo'lsa, limitni hisoblash mumkin jami hisoblash funktsiyasi ${ displaystyle { hat {r}} (x, s)}$ shu kabi

${ displaystyle displaystyle r (x) = lim _ {s to infty} { hat {r}} (x, s)}$

Jami funktsiya ${ displaystyle r (x)}$ ichida chegara hisoblanadi D. agar umumiy funktsiya bo'lsa ${ displaystyle { hat {r}} (x, s)}$ hisoblash mumkin D. ham qoniqarli

${ displaystyle displaystyle r (x) = lim _ {s to infty} { hat {r}} (x, s)}$

To'plam natural sonlar chegarasida hisoblash mumkin deb belgilanadi, agar u bo'lsa xarakterli funktsiya limitda hisoblanadi. Aksincha, to'plam hisoblash mumkin va agar u funktsiya bilan chegarada hisoblanadigan bo'lsa ${ displaystyle phi (t, i)}$ va kiritishni qabul qiladigan ikkinchi hisoblanadigan funktsiya mavjud men va qiymatini qaytaradi t etarlicha katta ${ displaystyle phi (t, i)}$ barqarorlashdi.

Lemmani cheklang

The limma limiti natural sonlar to'plami chegara hisoblash mumkin, agar bu to'plam hisoblash mumkin bo'lsa ${ displaystyle 0 '}$ (the Turing sakrash bo'sh to'plamdan). Relyativizatsiya qilingan limm lemmasi to'plamning hisoblash mumkin bo'lgan chegarani bildiradi ${ displaystyle D}$ va agar u hisoblash mumkin bo'lsa ${ displaystyle D '}$.Bundan tashqari, chegara lemmasi (va uning relyativizatsiyasi) bir xilda saqlanadi. Shunday qilib funktsiya uchun indeksdan o'tish mumkin ${ displaystyle { hat {r}} (x, s)}$ uchun indeksga ${ displaystyle { hat {r}} (x)}$ ga bog'liq ${ displaystyle 0 '}$. Uchun indeksdan ham o'tish mumkin ${ displaystyle { hat {r}} (x)}$ ga bog'liq ${ displaystyle 0 '}$ ba'zilar uchun indeksga ${ displaystyle { hat {r}} (x, s)}$ bu chegara bor ${ displaystyle { hat {r}} (x)}$.

Isbot

Sifatida ${ displaystyle 0 '}$ [hisoblash mumkin bo'lgan] to'plamdir, u chegaraning o'zida hisoblanishi kerak, chunki hisoblash mumkin funktsiyani aniqlash mumkin

${ displaystyle displaystyle { hat {r}} (x, s) = { begin {case} 1 & { text {agar bosqichma-bosqich}} s, x { text {sanab chiqilsa}} 0 ' 0 & { text {if not}} end {case}}}$

kimning chegarasi ${ displaystyle r (x)}$ kabi ${ displaystyle s}$ cheksizlikka boradi bu xarakterli funktsiya ${ displaystyle 0 '}$.

Shuning uchun agar chegara hisoblash qobiliyati saqlanib qolsa, buni ko'rsatish kifoya Turingni kamaytirish, chunki bu barcha to'plamlarni hisoblash mumkinligini ko'rsatadi ${ displaystyle 0 '}$ chegara hisoblanadi. To'plamlarni tuzatish ${ displaystyle X, Y}$ xarakterli funktsiyalari va hisoblash funktsiyasi bilan aniqlangan ${ displaystyle X_ {s}}$ chegara bilan ${ displaystyle X}$. Aytaylik ${ displaystyle Y (z) = phi ^ {X} (z)}$ Turingning qisqarishi uchun ${ displaystyle phi}$ va hisoblash funktsiyasini aniqlang ${ displaystyle Y_ {s}}$ quyidagicha

${ displaystyle displaystyle Y_ {s} (z) = { begin {case} phi ^ {X_ {s}} (z) & { text {if}} phi ^ {X_ {s}} { matn {ko'pi bilan birlashadi}} s { text {qadamlar.}} 0 va { text {aks holda}} end {case}}}$

Endi hisoblash deb taxmin qiling ${ displaystyle phi ^ {X} (z)}$ yaqinlashadi ${ displaystyle s}$ qadamlar va faqat birinchisiga qaraydi ${ displaystyle s}$ bit ${ displaystyle X}$. Endi tanlang ${ displaystyle s '> s}$ hamma uchun shunday ${ displaystyle z$ ${ displaystyle X_ {s '} (z) = X (z)}$. Agar ${ displaystyle t> s '}$ keyin hisoblash ${ displaystyle phi ^ {X_ {t}} (z)}$ ko'pi bilan yaqinlashadi ${ displaystyle s '$ qadamlar ${ displaystyle phi ^ {X} (z)}$. Shuning uchun ${ displaystyle Y_ {s} (z)}$ ning chegarasi bor ${ displaystyle phi ^ {X} (z) = Y (z)}$, shuning uchun ${ displaystyle Y}$ chegara hisoblanadi.

Sifatida ${ displaystyle Delta _ {2} ^ {0}}$ to'plamlar faqat hisoblash mumkin bo'lgan to'plamlardir ${ displaystyle 0 '}$ tomonidan Post teoremasi, chegara lemmasi, shuningdek, chegara hisoblanadigan to'plamlar ning bo'lishiga olib keladi ${ displaystyle Delta _ {2} ^ {0}}$ to'plamlar.

Hisoblanadigan haqiqiy sonlarni cheklash

A haqiqiy raqam x bu chegarada hisoblash mumkin agar hisoblash mumkin bo'lgan ketma-ketlik bo'lsa ${ displaystyle r_ {i}}$ ning ratsional sonlar (yoki bu teng, hisoblash mumkin bo'lgan haqiqiy raqamlar ) ga yaqinlashadigan x. Aksincha, haqiqiy raqam hisoblash mumkin agar unga va unga hisoblanadigan ratsional sonlar ketma-ketligi mavjud bo'lsa konvergentsiya moduli.

Haqiqiy son bitlar ketma-ketligi sifatida qaralganda, quyidagi ekvivalent ta'rif bajariladi. Cheksiz ketma-ketlik ${ displaystyle omega}$ ikkilik raqamlarning chegarasida hisoblash mumkin, agar faqat umumiy hisoblash funktsiyasi mavjud bo'lsa ${ displaystyle phi (t, i)}$ to'plamdagi qiymatlarni olish ${ displaystyle {0,1 }}$ har biri uchun shunday men chegara ${ displaystyle lim _ {t rightarrow infty} phi (t, i)}$ mavjud va tengdir ${ displaystyle omega (i)}$. Shunday qilib har bir kishi uchun men, kabi t ning qiymatini oshiradi ${ displaystyle phi (t, i)}$ oxir-oqibat doimiy bo'ladi va tenglashadi ${ displaystyle omega (i)}$. Hisoblanadigan haqiqiy sonlarda bo'lgani kabi, chegara hisoblanadigan reallarning ikkala tasviri o'rtasida samarali harakat qilish mumkin emas.

Misollar

• Ikkilik kengayish kodlangan haqiqiy muammoni to'xtatish limitda hisoblab chiqiladi, ammo hisoblanmaydi.
• Ikkilik kengayish haqiqat to'plamini kodlaydigan haqiqiy birinchi darajali arifmetik limitda hisoblanmaydi.

Shuningdek qarang

• Specker ketma-ketligi

Adabiyotlar

1. J. Shmidxuber, "Kolmogorovning umumlashtirilgan murakkabliklari ierarxiyalari va chegarada hisoblab chiqiladigan behisob universal chora-tadbirlar", Xalqaro kompyuter fanlari asoslari jurnali, 2002.
2. R. Soare. Rekursiv ravishda sanab o'tilgan to'plamlar va darajalar. Springer-Verlag 1987 yil.