تعداد غودل

معلومات عامة
جزء من	منطق رياضي
جانب من جوانب	Gödelization (en)
سُمِّي باسم	كورت غودل
تعريف الصيغة

تعداد غودل^[1] أو ترقيم غودل (بالإنجليزية: Gödel numbering)‏ في المنطق الرياضي هو دالة تعين لكل رمز وصيغة جيدة التكوين لبعض اللغات المتصرفة عددًا طبيعيًا فريدًا، يسمى عدد غودل^[2] الخاص به. طور كورت غودل هذا المفهوم للإثبات مبرهناته حول عدم الاكتمال.^[3]

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

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

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

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

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

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

ترميز غودل

الترميز الأصلي لغودل^[4]
								متغيرات العدد				متغيرات الخاصية			...
رمز	0	س	¬	∨	∀	(	)	×₁	×₂	×₃	...	ص₁	ص₂	ص₃	...
عدد	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}}.

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

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

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

مثال

في تعداد غودل المحدد المستخدم من قبل ناجل ونيومان، فإن عدد غودل للرمز "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.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}

مراجع

^ شحود، ارنستو (10 مارس 2014). "«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز". ثقافات. اطلع عليه بتاريخ 2024-12-21.
^ "«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز – مجلة نزوى". نزوى. 1 يناير 2014. اطلع عليه بتاريخ 2024-12-21.
^ ^ا ^ب Gödel 1931
^ See Gödel 1931, p. 179; Gödel's notation (see p. 176) has been adapted to modern notation.

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.

[1] شحود، ارنستو (10 مارس 2014). "«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز". ثقافات. اطلع عليه بتاريخ 2024-12-21.

[2] "«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز – مجلة نزوى". نزوى. 1 يناير 2014. اطلع عليه بتاريخ 2024-12-21.

[ReferenceA-3] ا ^ب Gödel 1931

[4] See Gödel 1931, p. 179; Gödel's notation (see p. 176) has been adapted to modern notation.

[1]

[2]

[3]

[4]

بحاجة لمصدر