Rays-Shapiro teoremasi - Rice–Shapiro theorem

Yilda hisoblash nazariyasi, Rays-Shapiro teoremasi ning umumlashtirilishi Rays teoremasi, va nomi berilgan Genri Gordon Rays va Norman Shapiro.^[1]

Rasmiy bayonot

Ruxsat bering A qisman-rekursiv unary to'plami bo'lishi funktsiyalari domenida natural sonlar shunday qilib to'plam ${displaystyle Ix (A): = {nmid varphi _ {n} A da}}$ bu rekursiv ravishda sanab o'tish mumkin, qayerda ${displaystyle varphi _ {n}}$ belgisini bildiradi ${displaystyle n}$ a-dagi qisman-rekursiv funktsiya Gödel raqamlash.

Keyin har qanday unary qisman-rekursiv funktsiya uchun ${displaystyle psi}$ , bizda ... bor:

{ALeftrightarrow-da displaystyle psi mavjud}

cheklangan funktsiya

{displaystyle heta subseteq psi}

shu kabi

{displaystyle heta A. da.}

Berilgan bayonotda chekli funktsiya - bu cheklangan domenga ega funktsiya ${displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ va ${displaystyle heta subseteq psi}$ bu har bir kishi uchun degan ma'noni anglatadi ${displaystyle xin {x_ {1}, x_ {2}, ..., x_ {m}}}$ buni ushlab turadi ${displaystyle psi (x)}$ aniqlangan va unga tenglashtirilgan ${displaystyle heta (x)}$ .

Samarali topologiyadan istiqbol

Har qanday cheklangan unary funktsiyasi uchun ${displaystyle heta}$ butun sonlarda, ruxsat bering ${displaystyle C (heta)}$ aniqlangan va unga qo'shilgan barcha qisman-rekursiv funktsiyalarning "umidsizligini" belgilang ${displaystyle heta}$ , kuni ${displaystyle heta}$ domen.

Barcha qisman-rekursiv funktsiyalar to'plamini thisfrusta tomonidan ishlab chiqarilgan topologiya bilan jihozlang tayanch. E'tibor bering, har bir ko'ngilsizlik uchun ${displaystyle C}$ , ${displaystyle Ix (C)}$ rekursiv ravishda sanab o'tiladi. Umuman olganda u har bir to'plam uchun amal qiladi ${displaystyle A}$ qisman-rekursiv funktsiyalar:

${displaystyle Ix (A)}$ iff rekursiv ravishda sanab o'tiladi ${displaystyle A}$ frustaning rekursiv ravishda sanab o'tiladigan birlashmasi.

Izohlar

^ Kichik Rojers, Xartli (1987). Rekursiv funktsiyalar nazariyasi va samarali hisoblash. MIT Press. ISBN 0-262-68052-1.

Adabiyotlar

Kutland, Nayjel (1980). Hisoblash: rekursiv funktsiyalar nazariyasiga kirish. Kembrij universiteti matbuoti.; Teorema 7-2.16.
Kichik Rojers, Xartli (1987). Rekursiv funktsiyalar nazariyasi va samarali hisoblash. MIT Press. p. 482. ISBN 0-262-68052-1.
Odifreddi, Pierjiorgio (1989). Klassik rekursiya nazariyasi. Shimoliy Gollandiya.

Ushbu hisoblash maqolasi a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.

[rogers_1987-1] Kichik Rojers, Xartli (1987). Rekursiv funktsiyalar nazariyasi va samarali hisoblash. MIT Press. ISBN 0-262-68052-1.

[1]