ترقيم غودل

في المنطق الرياضي ، يُعرف ترقيم غودل بأنه دالة تُسند لكل رمز وصيغة سليمة في لغة صورية ما عددًا طبيعيًا فريدًا ، يُسمى عدد غودل . وقد طوّر كورت غودل هذا المفهوم لإثبات نظريات عدم الاكتمال الخاصة به . ^{[ 1 ] : 173-198}

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

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

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

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

• تُمثل كلمة "ثعلب" بـ102 111 120 121 .
• الصيغة المنطقية x=y => y=xممثلة بـ120 061 121 032 061 062 032 121 061 120 .

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

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

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

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

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

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

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

${\displaystyle 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 ليكون قوة للعدد 10، فإن هذا المخطط يجعل من السهل نسبيًا على الإنسان التحويل بين سلسلة من الرموز ورقم غودل الخاص بها، لأن رقم غودل المُمثل بالأساس 10 هو مجرد سلسلة من الرموز.${\displaystyle n}$الأعداد العشرية${\displaystyle h(s_{i})}$.

على سبيل المثال، الترقيم الموصوف هنا يحتوي على K=1000. ^{[ ii ]}

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

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

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

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

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

• ناجل، إرنست ؛ نيومان، جيمس ر. (1959). برهان غودل .

• هوفستاتر، دوغلاس (1979). غودل، إيشر، باخ: ضفيرة ذهبية أبدية . دار بيسيك بوكس. رقم ISBN 978-0-465-02656-2.يُعرّف ويستخدم ترقيم غودل البديل.
• هوفستاتر، دوغلاس (2007). أنا حلقة غريبة . دار بيسيك بوكس. رقم ISBN 978-0-465-03078-1.يتضمن تاريخ ترقيم غودل.
• هيمان، جيسون؛ هولك، إريك (15 يونيو 2013). "تصور مأزق تورينج" (ملف PDF) . وقائع ورشة عمل ACM SIGPLAN الأولى حول الفن الوظيفي والموسيقى والنمذجة والتصميم . الصفحات 71-76 . doi : 10.1145/2505341.2505348 . ISBN  978-1-4503-2386-4تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 27 سبتمبر 2016.يستخدم ترقيم غودل لترميز البرامج.