Hisoblanadigan izomorfizm - Computable isomorphism

Yilda hisoblash nazariyasi ikkita to'plam ${ displaystyle A; B subseteq mathbb {N}}$ ning natural sonlar bor hisoblash uchun izomorfik yoki rekursiv izomorfik agar mavjud bo'lsa a jami ikki tomonlama hisoblash funktsiyasi ${ displaystyle f colon mathbb {N} to mathbb {N}}$ bilan ${ displaystyle f (A) = B}$ . Tomonidan Myhill izomorfizm teoremasi,^[1] hisoblab chiqiladigan izomorfizmning munosabati bitta kamayish munosabati bilan mos keladi.

Ikki raqamlash ${ displaystyle nu}$ va ${ displaystyle mu}$ deyiladi hisoblash uchun izomorfik agar hisoblanadigan biektsiya mavjud bo'lsa ${ displaystyle f}$ Shuning uchun; ... uchun; ... natijasida ${ displaystyle nu = mu circ f}$

Hisoblanadigan izomorfik raqamlashlar to'plamdagi bir xil hisoblash tushunchasini keltirib chiqaradi.

Adabiyotlar

^ Teorema 7.VI, Xartli Rojers, kichik, Rekursiv funktsiyalar nazariyasi va samarali hisoblash imkoniyati

Rojers, Xartli, kichik (1987), Rekursiv funktsiyalar nazariyasi va samarali hisoblash imkoniyati (2-nashr), Kembrij, MA: MIT Press, ISBN 0-262-68052-1, JANOB 0886890.

P ≟ NP

Bu nazariy informatika - tegishli maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.

Bu matematik mantiq bilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.

[1] Teorema 7.VI, Xartli Rojers, kichik, Rekursiv funktsiyalar nazariyasi va samarali hisoblash imkoniyati

[1]