التعبير عن وظائف باستخدام القاموس الحسابي

Question

لقد رأيت في فئة "المنطق إلى CS" وأخذ - نظرية تنص على ذلك: "كل وظيفة متكررة (حسابية) $ f $ يمكن التعبير عنها باستخدامالقاموس الحسابي { $ c_0، c_1، f _ + (،)، f_x (،)، r_ le (،) $ } مع الهيكل { $ d=mathbb {n}، c_0= 0، c_1= 1، f _ + + (a، b)= a + b، f_x (a، b)= ab، r_ le (a،ب)= A \ LE B $ } "

لكننا لم نثبت هذا النظرية لأن جزءا من الطلاب لم يأخذ دورة "النماذج الحسابية" (أفعل ذلك رغم ذلك)

أين يمكنني العثور على دليل على هذا النظرية؟شكرا مقدما!

Answer 1

أنا لست متأكدا من أن هذا هو بالضبط ما تبحث عنه، ولكن قد تجد ما تريده في نظرية 3.2.1 من نظرية حسابية بواسطة S. Barry Cooper:

جميع الوظائف العودية هي تمثيلية في السلطة الفلسطينية.

ذلك هو لأي وظيفة متكررة $ f $ ، هناك موجة ثنائية المسند $ f $ في لغة الحساب بحيث لأي أرقام طبيعية $ x $ و $ y $ لدينا $$ f (x)= y ~ \ charnarrow ~ \ vdash_ {pa} f (x، y) $$ و $$ f (x) \ Neq y ~ \ charearrow ~ \ vdash_ {pa} \ lnot f (x، y) $$ حيث $ \ vdash_ {pa} $ يعني "السلطة الفلسطينية تثبت".

هذا نظرية هو أمر أساسي في نظرية Gödel الشهيرة غير المكتملة ، لذلك قد ترغب أيضا في إلقاء نظرة على الفصل. 8 من الكتاب المذكور حيث تمت مناقشته، وتم تمديد فكرة "الممثل" هذه إلى "إمكانية الممثلين"، لتضمين C.E. مجموعات كذلك.