تعداد غودل

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

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

مثلًا، التعداد الموصوف هنا هو K=1000.

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

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

التعميمات

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

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

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

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

التعبير عن العبارات والبراهين بالأعداد

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

ثم

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

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

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

الكلمة تمثلالثعلبي بالعدد .

الصيغة المنطقية يتم تمثيلها بواسطة .

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

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

مثال

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

التكرار

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

ترميز غودل

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

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

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

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

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

مجموعات غودل

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

• انظر كذلك
• نظريات عدم الاكتمال لغودل
• نظرية عدم الاكتمال لتشايتين