ترقيم غودل

  لnumberings of the set of computable functions، طالع Numbering (computability theory).

في المنطق الرياضي ، ترقيم غودلGödel) numbering) هو دالة تعين لكل رمز وصيغة جيدة التكوين لبعض اللغات الرسمية عددًا طبيعيًا فريدًا، يسمى رقم غودل الخاص به. تم تطوير هذا المفهوم من قبل كورت غودل لإثبات نظرياته حول عدم الاكتمال . ( Gödel 1931 )

يمكن تفسير ترقيم غودل على أنه تشفير يتم فيه تعيين رقم لكل رمز من رموز التدوين الرياضي ، وبعد ذلك يمكن لسلسلة من الأرقام الطبيعية أن تمثل سلسلة من الرموز بعدها. مما يمكن من تمثيل هذه التسلسلات من الأعداد الطبيعية مرة أخرى بأعداد طبيعية مفردة، مما يسهل معالجتها في النظريات الرسمية للحساب.

منذ نشر ورقة غودل في عام 1931، تم استخدام مصطلح "ترقيم غودل" أو "شفرة جودل" للإشارة إلى تعيينات أكثر عمومية للأعداد الطبيعية للأشياء الرياضية.

نظرة عامة مبسطة

لاحظ غودل أن كل عبارة داخل النظام يمكن تمثيلها بعدد طبيعي ( عدد غودل الخاص بها). كانت أهمية هذا الأمر هي أن خصائص العبارة - مثل صحتها أو كذبها - ستكون معادلة لتحديد ما إذا كان رقم غودل الخاص بها يتمتع بخصائص معينة ما. قد تكون الأعداد المعنية كبيرة جدًا بالفعل، ولكن هذا لا يشكل عائقًا؛ كل ما يهم هو إمكانية إنشاء مثل هذه الأعداد.

وبمصطلحات بسيطة، ابتكر طريقة يتم من خلالها منح كل صيغة أو بيان يمكن صياغته في النظام رقمًا فريدًا، بحيث يمكن تحويل الصيغ وأرقام غودل ميكانيكيًا ذهابًا و إيابًا من خلال العديد من الطرق التي تمكن من القيام بذلك. و من الأمثلة البسيطة على ذلك الطريقة التي يتم بها تخزين اللغة الإنجليزية على شكل سلسلة من الأرقام في أجهزة الكمبيوتر باستخدام ASCII . فنظرًا لأن رموز ASCII تقع في النطاق من 0 إلى 127، فمن الكافي أن نملأها بثلاثة أرقام عشرية ثم نربطها معًا:

• الكلمةfoxyيمثل الثعلبي بالرقم 102111120121 .
• الصيغة المنطقية x=y => y=x يتم تمثيلها بواسطة 120061121032061062032121061120 .

ترميز غودل

الترميز الأصلي لغودل

								متغيرات العدد				متغيرات الخاصية			...
رمز	0	س	¬	∨	∀	(	)	× 1	× 2	× 3	...	ص 1	ص 2	ص 3	...
رقم	1	3	5	7	9	11	13	17	19	23	...	289	361	529	...

استخدم غودل نظامًا يعتمد على التحليل إلى عوامل أولية . حيث قام أولاً بتعيين عدد طبيعي فريد لكل رمز أساسي في اللغة الرسمية للحساب الذي كان يتعامل معه.

لتشفير صيغة كاملة، وهي عبارة عن سلسلة من الرموز، استخدم غودل النظام التالي. نظرا للتسلسل $(x_{1},x_{2},x_{3},...,x_{n})$ بالنسبة للأعداد الصحيحة الموجبة، فإن ترميز غودل للتسلسل هو حاصل ضرب أول n من الأعداد الأولية مرفوعة إلى قيمها المقابلة في التسلسل:

$\mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.$

وفقًا للنظرية الأساسية في الحساب ، يمكن تحليل أي عدد (وخاصة أي عدد تم الحصول عليه بهذه الطريقة) إلى عوامل أولية بشكل فريد، وبالتالي من الممكن استعادة التسلسل الأصلي من رقم غودل الخاص به (لأي عدد معين من الرموز المراد ترميزها).

استخدم غودل هذا المخطط على وجه التحديد على مستويين: الأول، لتشفير تسلسلات الرموز التي تمثل الصيغ، والثاني، لتشفير تسلسلات الصيغ التي تمثل البراهين. و هذا سمح له بإظهار التطابق بين البيانات حول الأعداد الطبيعية والبيانات حول إمكانية إثبات النظريات حول الأعداد الطبيعية، و هي الغاية الأساسية للإثبات. ( Gödel 1931 )

هناك طرق أكثر تطوراً (وأكثر إيجازاً) لإنشاء ترقيم غودل للتسلسلات .

مثال

في ترقيم غودل المحدد المستخدم من قبل ناجل ونيومان، فإن رقم غودل للرمز "0" هو 6 ورقم غودل للرمز "=" هو 5. وهكذا، في نظامهم، فإن رقم غودل للصيغة "0 = 0" هو 2 ⁶ × 3 ⁵ × 5 ⁶ = 243,000,000.

عدم وجود التفرد

من الممكن استخدام عدد لا نهائي من ترقيمات غودل المختلفة. على سبيل المثال، بافتراض وجود K رمزًا أساسيًا، يمكن إنشاء ترقيم غودل بديل عن طريق تعيين هذه المجموعة من الرموز بشكل عكسي (من خلال، على سبيل المثال، دالة قابلة للعكس h ) إلى مجموعة أرقام نظام رقمي ثنائي القاعدة <i id="mwfQ">K.</i> صيغة تتكون من سلسلة من n رمزًا $s_{1}s_{2}s_{3}\dots s_{n}$ سيتم بعد ذلك ربطها بالرقم

$h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.$

بعبارة أخرى، عن طريق وضع مجموعة K من الرموز الأساسية في ترتيب ثابت، بحيث $i$ - يتوافق الرمز -th بشكل فريد مع $i$ الرقم - من نظام الأعداد الثنائية ذات القاعدة K ، يمكن لكل صيغة أن تعمل بمثابة الرقم نفسه لرقم جودل الخاص بها.

على سبيل المثال، الترقيم الموصوف هنا هو K=1000.

تطبيق على علم الحساب الرسمي

التكرار

من الممكن استخدام ترقيم غودل لإظهار كيف أن الوظائف المحددة من خلال التكرار في مسار القيم هي في الواقع وظائف تكرارية بدائية .

التعبير عن العبارات والبراهين بالأرقام

بمجرد إنشاء ترقيم غودل لنظرية رسمية، يمكن التعبير عن كل قاعدة استدلال للنظرية كدالة على الأعداد الطبيعية. إذا كانت f هي تعيين غودل و r هي قاعدة استدلال، فيجب أن تكون هناك دالة حسابية g _r للأعداد الطبيعية بحيث إذا تم اشتقاق الصيغة C من الصيغتين A و B من خلال قاعدة استدلال r ، أي

$A,B\vdash _{r}C,$

ثم

$g_{r}(f(A),f(B))=f(C).$

وهذا ينطبق على الترقيم الذي استخدمه غودل، وعلى أي ترقيم آخر حيث يمكن استرداد الصيغة المشفرة حسابيًا من رقم غودل الخاص بها.

وهكذا، في نظرية رسمية مثل مسلمات بيانو ، حيث يمكن للمرء أن يدلي ببيانات حول الأرقام وعلاقاتها الحسابية مع بعضها البعض، يمكن استعمال ترقيم جودل للإدلاء ببيانات غير مباشرة حول النظرية نفسها. و بذلك، سمحت هذه التقنية لغودل بإثبات نتائج حول خصائص الاتساق والاكتمال للأنظمة الرسمية .

التعميمات

في نظرية الحساب ، يتم استخدام مصطلح "ترقيم غودل" في إعدادات أكثر عمومية من تلك الموصوفة أعلاه. فيمكن أن يشير إلى:

1. أي تعيين لعناصر لغة رسمية إلى أرقام طبيعية بطريقة تجعل الأرقام قابلة للتلاعب بها بواسطة خوارزمية لمحاكاة التلاعب بعناصر اللغة الرسمية.</link>
2. بشكل عام، تعيين عناصر من كائن رياضي قابل للعد، مثل مجموعة قابلة للعد، إلى أعداد طبيعية للسماح بالتلاعب الخوارزمي بالكائن الرياضي.</link>

بالإضافة إلى ذلك، يُستخدم مصطلح ترقيم غودل أحيانًا عندما تكون "الأرقام" المخصصة عبارة عن سلاسل في الواقع، وهو أمر ضروري عند النظر في نماذج الحوسبة مثل آلات تورينج التي تتعامل مع السلاسل بدلاً من الأرقام.</link>

مجموعات غودل

تُستخدم مجموعات غودل أحيانًا في نظرية المجموعات لتشفير الصيغ، والتي تشبه إلى حد كبير أرقام غودل، إلا أنها تستخدم المجموعات بدلاً من الأرقام للقيام بالتشفير. مما يعني أنه، في الحالات البسيطة، عندما يستخدم المرء مجموعة محدودة وراثيًا لترميز الصيغ، يكون هذا معادلًا بشكل أساسي لاستخدام أرقام غودل، ولكنه أسهل إلى حد ما في التعريف لأن بنية شجرة الصيغ يمكن نمذجتها من خلال بنية شجرة المجموعات. يمكن أيضًا استخدام مجموعات غودل لترميز الصيغ في اللغات اللانهائية .

انظر أيضا

• ترميز الكنيسة
• رقم الوصف
• ترقيم جودل للتسلسلات
• نظريات عدم الاكتمال لغودل
• نظرية عدم الاكتمال لتشايتين

ملحوظات

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

مراجع

• Gödel، Kurt (1931)، "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF)، Monatshefte für Mathematik und Physik، ج. 38، ص. 173–198، DOI:10.1007/BF01700692، مؤرشف من الأصل (PDF) في 2018-04-11، اطلع عليه بتاريخ 2013-12-07.
• Gödel's Proof by Ernest Nagel and James R. Newman (1959). This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering.