نظرية S m n

في نظرية الحوسبة، تُعدّ نظرية Smn ، التي   تُكتب أيضًا " نظرية smn " أو " نظرية smn " (وتُسمى أيضًا مبرهنة الإزاحة ، ونظرية المعامل ، ونظرية المعاملية )، نتيجةً أساسيةً تتعلق بلغات البرمجة (وبشكلٍ أعم، بترقيم غودل للدوال القابلة للحوسبة الجزئية ) (Soare 1987، Rogers 1967). وقد أثبتها لأول مرة ستيفن كول كلين (1943).${\displaystyle S_{m}^{n}}$ينشأ ذلك من حدوث${\displaystyle S}$مع رمز سفلي${\displaystyle n}$وأعلى${\displaystyle m}$في الصيغة الأصلية للنظرية (انظر أدناه).

من الناحية العملية، تنص النظرية على أنه بالنسبة للغة برمجة معينة وأعداد صحيحة موجبة${\displaystyle m}$و${\displaystyle n}$توجد خوارزمية معينة تقبل كمدخلات شفرة المصدر لبرنامج مع${\displaystyle m+n}$المتغيرات الحرة ، بالإضافة إلى${\displaystyle m}$القيم. تُولّد هذه الخوارزمية شفرة مصدرية تستبدل في جوهرها القيم بالقيم الأولى.${\displaystyle m}$المتغيرات الحرة، تاركة بقية المتغيرات حرة.

ينطبق الشكل الأساسي للنظرية على الدوال ذات المتغيرين (نيس 2009، ص  6). مع الأخذ في الاعتبار ترقيم غودل${\displaystyle \varphi }$من بين الدوال القابلة للحساب الجزئي، توجد دالة تكرارية أولية${\displaystyle s}$من وسيطين بالخاصية التالية: لكل عدد غودل${\displaystyle e}$دالة قابلة للحساب جزئيًا${\displaystyle f}$باستخدام وسيطين، التعبيرات${\displaystyle \varphi _{s(e,x)}(y)}$و${\displaystyle f(x,y)}$يتم تعريفها لنفس مجموعات الأعداد الطبيعية${\displaystyle x}$و${\displaystyle y}$وتكون قيمها متساوية لأي تركيبة من هذا القبيل. بعبارة أخرى، تتحقق المساواة الامتدادية التالية للدوال لكل${\displaystyle x}$:

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

وبشكل أعم، بالنسبة لأي${\displaystyle m,n>0}$، توجد دالة تكرارية أولية${\displaystyle S_{n}^{m}}$ل${\displaystyle m+1}$الوسائط التي تتصرف على النحو التالي: لكل عدد غودل${\displaystyle e}$دالة قابلة للحساب جزئيًا مع${\displaystyle m+n}$الوسائط، وجميع قيم${\displaystyle x_{1},x_{2},...,x_{m}}$:

${\displaystyle \varphi _{S_{n}^{m}(e,x_{1},\dots ,x_{m})}\simeq \lambda y_{1},\dots ,y_{n}.\varphi _{e}(x_{1},\dots ,x_{m},y_{1},\dots ,y_{n}).}$

الوظيفة${\displaystyle s}$يمكن اعتبار ما سبق ذكره${\displaystyle S_{1}^{1}}$.

الرتب المعطاة${\displaystyle m}$و${\displaystyle n}$لكل آلة تورينج${\displaystyle {\text{TM}}_{x}}$من التعددية${\displaystyle m+n}$ولجميع القيم الممكنة للمدخلات${\displaystyle y_{1},\dots ,y_{m}}$توجد آلة تورينج${\displaystyle {\text{TM}}_{k}}$من التعددية${\displaystyle n}$بحيث

${\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}).}$

علاوة على ذلك، توجد آلة تورينج${\displaystyle S}$وهذا يسمح${\displaystyle k}$يتم حسابها من${\displaystyle x}$و${\displaystyle y}$ويُشار إليه بـ${\displaystyle k=S_{n}^{m}(x,y_{1},\dots ,y_{m})}$.

بشكل غير رسمي،${\displaystyle S}$يجد آلة تورينج${\displaystyle {\text{TM}}_{k}}$هذا نتيجة لتضمين قيم ثابتة في الكود.${\displaystyle y}$داخل${\displaystyle {\text{TM}}_{x}}$. يمكن تعميم النتيجة على أي نموذج حوسبة كامل تورينج .

الكود التالي المكتوب بلغة Lisp ينفذ s ₁₁ للغة Lisp.

( defun s11 ( f x ) ( let (( y ( gensym ))) ( list 'lambda ( list y ) ( list f x y ))))

على سبيل المثال، يتم تقييمها إلى ، حيث يمثل رمز "جديد".(s11'(lambda(xy)(+xy))3)(lambda(g42)((lambda(xy)(+xy))3g42))g42

• الكاري
• نظرية كلين للتكرار
• التقييم الجزئي

• كلين، إس سي (1936). "الدوال التكرارية العامة للأعداد الطبيعية" . حوليات الرياضيات . 112 (1): 727-742 . doi : 10.1007/BF01565439 . S2CID 120517999 . 
• كلين، إس سي (1938). "حول رموز الأعداد الترتيبية" (ملف PDF) . مجلة المنطق الرمزي . 3 (4): 150-155 . doi : 10.2307/2267778 . JSTOR 2267778. S2CID 34314018 .  (هذا هو المرجع الذي ورد في طبعة عام 1989 من كتاب أوديفردي "نظرية الاستدعاء الكلاسيكية" في الصفحة  131 لـ${\displaystyle S_{n}^{m}}$(نظرية.)
• نيس، أ. (2009). الحوسبة والعشوائية . أدلة أكسفورد المنطقية. المجلد  51. أكسفورد: مطبعة جامعة أكسفورد. ISBN 978-0-19-923076-1. Zbl 1169.03034 . 
• أوديفردي، ب. (1999). نظرية الاستدعاء الذاتي الكلاسيكية . نورث هولاند. ISBN 0-444-87295-7.
• روغرز، هـ. (1987) [1967]. نظرية الدوال التكرارية والحوسبة الفعالة . الطبعة الأولى ذات الغلاف الورقي من مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 0-262-68052-1.
• سواري، ر. (1987). المجموعات والدرجات القابلة للتعداد بشكل متكرر . منظورات في المنطق الرياضي. سبرينغر-فيرلاغ. ISBN 3-540-15299-7.

• وايسشتاين، إريك دبليو. " نظرية كلين إس - إم - إن " . عالم الرياضيات .