3-4-mavzu: Primitiv rekursiv funksiyalar. Tyuring tezisi. Markovning normal algoritmi

U(a, b, f) = {(x, y) ∈ R 2 | a ≤ x ≤ b & 0 ≤ y ≤ f(x)}. Uning maydoni, u nima bo'lishidan qat'iy nazar,

• U(a, b, f) = {(x, y) ∈ R 2 | a ≤ x ≤ b & 0 ≤ y ≤ f(x)}. Uning maydoni, u nima bo'lishidan qat'iy nazar,

:= area(U(a, b, f)) . bilan belgilanadi.

• Bu x o'qi, f funktsiya grafigi va y = a va y = b vertikal chiziqlar bilan aniqlangan tekislikning bir qismining maydoni. Maydon va hosila o'rtasidagi ikkita asosiy munosabatlar quyidagicha.
• U(a, x, f), ya'ni F(x) = maydoni sifatida aniqlangan x ning F funksiyasini ko'rib chiqaylik.

•  

Hisoblashning birinchi fundamental teoremasi shuni aytadiki, har bir c ∈ [a, b] uchun bizda mavjud F’(c) = f(c) funksiyaning xosilasi. Argumenti x U(a, x, f) ning yuqori chegarasi va qiymati uning maydoni f asl funksiyaga teng.

• Hisoblashning birinchi fundamental teoremasi shuni aytadiki, har bir c ∈ [a, b] uchun bizda mavjud F’(c) = f(c) funksiyaning xosilasi. Argumenti x U(a, x, f) ning yuqori chegarasi va qiymati uning maydoni f asl funksiyaga teng.
• Bu F(x) = funksiya f funksiyaning primitiv funksiyasi deyiladi. f ning [a, b] ustidagi primitiv funksiyasi bo‘lgan har bir F funksiya uchun hisob-kitobning ikkinchi asosiy teoremasiga ko‘ra, u shunday bo’ladi:

•  

Lekin birinchi navbatda biz primitiv funktsiyalarning xususiyatlarini ko'rib chiqishimiz kerak - bu erda funksiya primitiv funksiyaga ega, u noyobmi va hokazo.

• Lekin birinchi navbatda biz primitiv funktsiyalarning xususiyatlarini ko'rib chiqishimiz kerak - bu erda funksiya primitiv funksiyaga ega, u noyobmi va hokazo.
• Hosilaning chiziqliligi tufayli primitiv funktsiyalar ham chiziqli bo'ladi:

Agar biz f ning primitive funksiyasini bilsak (elementar funksiyalarning hosilasi qoidalarini shunchaki teskari o'zgartirish orqali ko'pchilikni chiqarish mumkin), Biz zudlik bilan U(a, b, f) maydonini hisoblashimiz mumkin.

Primitiv rekursiv funktsiyalarda PRC klassi bo'lgan hisoblash funktsiyalari sinfi mavjud. Ta'rif: funktsiya ibtidoiy rekursiv hisoblanadi, agar uni boshlang'ich funktsiyalardan va cheklangan miqdordagi kompozitsiya va rekursiya bosqichlari orqali olish mumkin bo'lsa. Teorema: Agar funktsiya PRC sinfiga tegishli bo'lsa, u privmitiv rekursiv hisoblanadi