عرض مصدر تعداد غودل

{{يتيمة|تاريخ =أكتوبر 2024}}
{{بطاقة عامة}}
'''تعداد غودل'''<ref>{{استشهاد بويب|عنوان=«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز|مسار=https://thaqafat.com/2014/03/22758|تاريخ-الوصول=2024-12-21|صحيفة=ثقافات|تاريخ=2014-03-10|مؤلف=شحود|الأول=ارنستو|لغة=ar}}</ref> أو '''ترقيم غودل''' {{إنج|Gödel numbering}} في [[منطق رياضي|المنطق الرياضي]] هو [[دالة]] تعين لكل رمز [[صيغة جيدة التكوين|وصيغة جيدة التكوين]] لبعض [[لغة متصرفة|اللغات المتصرفة]] [[عدد طبيعي|عددًا طبيعيًا]] فريدًا، يسمى '''عدد غودل'''<ref>{{استشهاد بويب|عنوان=«الذكاء الاصطناعي والمنهج العلمي» للفيلسوف دونالد غيليز – مجلة نزوى|مسار=https://www.nizwa.om/%D8%A7%D9%84%D8%B0%D9%83%D8%A7%D8%A1-%D8%A7%D9%84%D8%A7%D8%B5%D8%B7%D9%86%D8%A7%D8%B9%D9%8A-%D9%88%D8%A7%D9%84%D9%85%D9%86%D9%87%D8%AC-%D8%A7%D9%84%D8%B9%D9%84%D9%85%D9%8A-%D9%84%D9%84/|تاريخ-الوصول=2024-12-21|لغة=ar|تاريخ = 1 يناير 2014|موقع = نزوى}}</ref> الخاص به. طور  [[كورت غودل]] هذا المفهوم للإثبات [[مبرهنات عدم الاكتمال لغودل|مبرهناته حول عدم الاكتمال]].<ref name="ReferenceA">{{استشهاد بهارفارد دون أقواس|Gödel|1931}}</ref>

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

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

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

ببساطة شديدة، ابتكر طريقة يتم من خلالها منح كل صيغة أو بيان يمكن صياغته في النظام عددًا فريدًا، بحيث يمكن تحويل الصيغ وأعداد غودل ميكانيكيًا ذهابًا وإيابًا من خلال العديد من الطرق التي تمكن من القيام بذلك. ومن الأمثلة البسيطة على ذلك الطريقة التي يتم بها تخزين اللغة الإنجليزية على شكل سلسلة من الأعداد في أجهزة الكمبيوتر باستخدام [[أسكي|ASCII]]. فنظرًا لأن رموز ASCII تقع في النطاق من 0 إلى 127، فمن الكافي أن نملأها بثلاثة أعداد عشرية ثم نربطها معًا:
* الكلمة'''{{مونو|foxy}} '''تمثل'''<span class="monospaced" data-ve-ignore="true">الثعلبي</span>''' بالعدد {{Val|102111120121}}.
* الصيغة المنطقية '''{{كود|1=x=y => y=x}}''' يتم تمثيلها بواسطة {{Val|120061121032061062032121061120}}.

== ترميز غودل ==
{| class="wikitable" style="float:left;"
| colspan="8" |
! colspan="4" |متغيرات العدد
! colspan="3" | متغيرات الخاصية
|...
|-
! رمز
| 0
| ''س''
| ¬
| ∨
| ∀
| (
|)
| ''×''<sub>1</sub>
| ''×''<sub>2</sub>
| ''×''<sub>3</sub>
|...
| ''ص''<sub>1</sub>
| ''ص''<sub>2</sub>
| ''ص''<sub>3</sub>
|...
|-
! عدد
| 1
| 3
| 5
| 7
| 9
| 11
| 13
| 17
| 19
| 23
|...
| 289
| 361
| 529
|...
|+ الترميز الأصلي لغودل<ref>See Gödel 1931, p. 179; Gödel's notation (see p. 176) has been adapted to modern notation.</ref>
|}
استخدم غودل نظامًا يعتمد على [[تحليل عدد صحيح إلى عوامل|التحليل إلى عوامل أولية]]. حيث قام أولاً بتعيين عدد طبيعي فريد لكل رمز أساسي في اللغة الرسمية للحساب الذي كان يتعامل معه.

لتشفير صيغة كاملة، وهي عبارة عن سلسلة من الرموز، استخدم غودل النظام التالي. نظرا للتسلسل <math>(x_1,x_2,x_3,...,x_n)</math> بالنسبة للأعداد الصحيحة الموجبة، فإن ترميز غودل للتسلسل هو حاصل ضرب أول ''n'' من الأعداد الأولية مرفوعة إلى قيمها المقابلة في التسلسل:

: <math>\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}.</math>

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

استخدم غودل هذا المخطط على وجه التحديد على مستويين: الأول، لتشفير تسلسلات الرموز التي تمثل الصيغ، والثاني، لتشفير تسلسلات الصيغ التي تمثل البراهين. وهذا سمح له بإظهار التطابق بين البيانات حول الأعداد الطبيعية والبيانات حول إمكانية إثبات النظريات حول الأعداد الطبيعية، وهي الغاية الأساسية للإثبات.<ref name="ReferenceA"/>

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

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

== عدم وجود التفرد ==
من الممكن استخدام عدد لا نهائي من تعدادات غودل المختلفة. على سبيل المثال، بافتراض وجود ''K'' رمزًا أساسيًا، يمكن إنشاء تعداد غودل بديل عن طريق تعيين هذه المجموعة من الرموز بشكل عكسي (من خلال، على سبيل المثال، [[دالة عكسية|دالة قابلة للعكس]] ''h'') إلى مجموعة أعداد نظام عددي ثنائي القاعدة <nowiki><i id="mwfQ">K.</i></nowiki> صيغة تتكون من سلسلة من ''n'' رمزًا <math> s_1 s_2 s_3 \dots s_n</math> سيتم بعد ذلك ربطها بالعدد

: <math> 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.</math>

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

على سبيل المثال، التعداد الموصوف هنا هو K=1000.{{للهامش|1}}

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

=== التعبير عن العبارات والبراهين بالأعداد ===
بمجرد إنشاء تعداد غودل لنظرية رسمية، يمكن التعبير عن كل [[قاعدة الاستدلال|قاعدة استدلال]] للنظرية كدالة على الأعداد الطبيعية. إذا كانت ''f'' هي تعيين غودل و''r'' هي قاعدة استدلال، فيجب أن تكون هناك [[دالة حسابية]] ''g<sub>r</sub>'' للأعداد الطبيعية بحيث إذا تم اشتقاق الصيغة ''C'' من الصيغتين ''A'' و''B'' من خلال قاعدة استدلال ''r''، أي

: <math> A, B \vdash_r C, </math>

ثم

: <math> g_r(f(A),f(B)) = f(C). </math>

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

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

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

# أي تعيين لعناصر [[لغة متصرفة|لغة رسمية]] إلى أعداد طبيعية بطريقة تجعل الأعداد قابلة للتلاعب بها بواسطة [[خوارزمية]] لمحاكاة التلاعب بعناصر اللغة الرسمية.{{بحاجة لمصدر}}
# بشكل عام، تعيين عناصر من كائن رياضي قابل للعد، مثل [[زمرة (رياضيات)|مجموعة]] قابلة للعد، إلى أعداد طبيعية للسماح بالتلاعب الخوارزمي بالكائن الرياضي.{{بحاجة لمصدر}}

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

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

== انظر أيضا ==
* [[مبرهنات عدم الاكتمال لغودل|نظريات عدم الاكتمال لغودل]]
* [[تعقيد كولموغروف|نظرية عدم الاكتمال لتشايتين]]

== ملحوظات ==
* {{هامش|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}

== مراجع ==
{{مراجع}}
* {{استشهاد|الأخير=Gödel|الأول=Kurt|عنوان=Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I|صحيفة=[[Monatshefte für Mathematik und Physik]]|المجلد=38|سنة=1931|صفحات=173–198|DOI=10.1007/BF01700692|مسار=http://www.w-k-essler.de/pdfs/goedel.pdf|تاريخ الوصول=2013-12-07|مسار أرشيف=https://web.archive.org/web/20180411113347/http://www.w-k-essler.de/pdfs/goedel.pdf|تاريخ أرشيف=2018-04-11|حالة المسار=dead}}.
* ''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.

{{شريط بوابات|رياضيات|علم الحاسوب|منطق}}

[[تصنيف:النظرية الحسابية]]
[[تصنيف:منطق رياضي]]
[[تصنيف:صفحات بترجمات غير مراجعة]]