مرجع
آخر الزيارات

مجموعة مرقمة بشكل تراجعي

1٬166 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: طبقًا لنظرية الحوسبة، والمعروفة عادةً بنظرية العدد أو التكرار، فإن مجموعة الأعداد الطبيعية S تكون مرقّمة بشكلٍ عوديّ (تراجعي)، وقابلة للعد أو الإحصاء حسابيًا، وتكون قابلة للحسم جزئيًا، ويمكن إثباتها بالبرهان أو يمكن لآلات تورنغ تمييزها…. في هذه المقالة 4 أقسام: «أمثلة»، «التعريف المنهجيّ» و«الخصائص» وغيرها.
المحتويات
  1. أمثلة
  2. التعريف المنهجيّ
  3. الخصائص
  4. صِيَغ متكافِئة

على سبيل التعريف، طبقًا لنظرية الحوسبة، والمعروفة عادةً بنظرية العدد أو التكرار، فإن مجموعة الأعداد الطبيعية S تكون مرقّمة بشكلٍ عوديّ (تراجعي)، وقابلة للعد أو الإحصاء حسابيًا، وتكون قابلة للحسم جزئيًا، ويمكن إثباتها بالبرهان أو يمكن لآلات تورنغ تمييزها والتعرُّف عليها بسهولة إذا:

من جانب آخر، وفي نظرية التعقيد الحسابي، تكون فئة التعقيد التي تحتوي على جميع المجموعات التي يمكن إحصاء تكرارها (أو المرقّمة بشكلٍ عوديّ) هي كذلك فئة مرقّمة بشكلٍ عوديّ. أمّا في النظرية العودية أو الحاسوبية، فإنّ شبكة المجموعات المرقّمة بشكلٍ عوديّ والتي تكون تحت الإدراج يُرمَز لها بـ .

من جهة ثانية، كان هناك خوارزمية ما بحيث تكون مجموعة الأرقام المدْخَلة فيها والتي تنتهي وتتوقّف عندها هذه الخوارِزِمية هي نفسها مجموعة الأرقام الموجودة في S.

إضافةً إلى ذلك، إذا كان هناك خوارِزِميّة تسرد وتحصي بشكلٍ دقيق عناصر المجموعة S. فإنّ هذا يعني أنّ نواتج هذه الخوارِزِميّة ما هي إلا قائمة بعناصر المجموعة S: s1، s2، s3.... وإذا لزِم الأمر، فإن هذه الخوارِزِميّة قد لا تتوقّف أبدًا.

أو، بشكلٍ مساوٍ،

ومن ناحية أخرى، فالحالة الأولى توضِّح لماذا يُسْتَخدَم مصطلح «قابلة للحسم جزئيًا» في بعض الأحيان؛ في حين أنّ الحالة الثانية تشير إلى سبب استخدام مصطلح «قابلة للإحصاء حسابيًا». وغالبًا ما تُسْتَخدَم الاختصارات r.e. (مرقّمة بشكلٍ عوديّ)، و c.e. (قابلة للإحصاء حسابيًا)، بدلاً من العبارة كاملة حتى في الوسائل المطبوعة.

أمثلة

من جهة ثانية، إنّ المجموعة المكوِّنة لجميع الجمل التي يمكن إثباتها بالبرهان وبنظام بدهيٍّ مُقدّم بشكلٍ فعّال هي مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها).

  • إنّ المجموعات البسيطة هي مجموعات مرقّمة بشكلٍ عوديّ ولكنها غير متكرِّرة.
  • إنّ المجموعات المبتكَرة هي مجموعات مرقّمة بشكلٍ عوديّ ولكنها غير متكرِّرة.
  • إن أي مجموعة ذات نواتج ليست مرقمةً بشكلٍ عوديّ.

كذلك، تُفيد نظرية ماتياسيفيتش بأنّ كل مجموعة مرقّمة بشكلٍ عوديّ هي مجموعة ديوفانتية (والعكس يمكن إثبات صحته بسهولة).

علاوةً على ذلك، إن كل مجموعة متكررة هي مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها)، ولكن ليست كل مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها) هي في الأصل مجموعة متكرّرة.

علاوةً على ذلك، باستخدام الدالة الجزئية ƒ والتي تبدأ بالأعداد الطبيعية وتنتهي بالأعداد الطبيعية، تكون ƒ دالة جزئية متكررة فقط إذا كان الرسم البياني للدالة ƒ يعبر عن مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها) وتمثِّل تلك المجموعة جميع الأطراف الثنائية بالطريقة التي يكون فيها f(x) معرّفًا.

وفي السياق ذاته، باستخدام ترقيم جودل في الدوال القابلة للحساب، تكون المجموعة مرقمة بشكلٍ عوديّ. وتقوم هذه المجموعة بترميز مسألة حساب قيمة دالة.

إضافةً إلى ذلك، أي لغة يمكن إحصاء تكرارها هي مجموعة يمكن إحصاء تكرارها وتمثِّل جزءًا من أي لغة اصطلاحية.

من جهة ثانية، باستخدام ترقيم جودل في الدوال القابلة للحساب، تكون المجموعة مرقمة بشكلٍ عوديّ (حيث أنّ هي دالة كانتور الثنائية و تشير إلى أنّ مُعرّف). وتقوم هذه المجموعة بترميز المشكلة الخاصة بإيقاف التشغيل حيث أنّها تصف العوامل المتغيرة المُدْخَلة والتي تتوقف عندها كل آلة تورنغ عن العمل.

التعريف المنهجيّ

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

من جانب آخر، ويمكن أنْ يمتّد التعريف ليشمل المجموعة العشوائية A القابلة للعّد باستخدام ترقيم جودِل، فيبيّن هذا الترقيم عناصر المجموعة مؤكِّدًا أن أي مجموعة جزئية من A هي مجموعة مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها) وذلك إذا كانت مجموعة أرقام جودِل المناظِرة لها مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها).

الخصائص

من جهة ثانية، إنّ الصورة العكسية لأي مجموعة يمكن إحصاء تكرارها في ظل دالة جزئية متكرِّرة هي كذلك مجموعة يمكن إحصاء تكرارها.

في هذا الإطار، إذا كانت A و B مجموعتان مرقّمتان بشكلٍ عوديّ، فإنّ A ∩ B, A ∪ B and A × B هي مجموعات (يمكن إحصاء تكرارها) مرقّمة بشكلٍ عوديّ، (حيث يرتبط زوج الأعداد الطبيعية المرتب مع عدد طبيعي واحد ليشكِّلا دالة كانتور الثنائية).

في هذا الإطار، وتتصِّف بعض المجموعات الثنائية التي يمكن إحصاء تكرارها بأنّه يمكن فصلها بنجاح بينما لايمكن فصل بعضها الآخر.

كذلك، ويمكن القول بأنّ المجموعة T مرقمة بشكلٍ عودي ومكمِّل أو co-r.e. إذا كان المكمِّل لها مرقّم بشكلٍ عوديّ (أو يمكن إحصاء تكراره). وبالمثل تكون أي مجموعة مرقمة بشكلٍ عودي ومكمِّل فقط إذا كانت عند المستوى من الهرم الحسابي.

وفي السياق ذاته، تكون المجموعة A متكرِّرة (المعنى المرادف: قابلة للحساب) فقط عندما يكون كلاً من A ومتتمة A مرقمًا بشكلٍ عوديّ. وتكون أي مجموعة متكرِّرة فقط إذا كانت تمثِّل مجال أي دالة متزايدة كلية ومتكرّرة أو إذا كانت محدودة.

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

صِيَغ متكافِئة

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

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

إضافةً إلى ذلك، إنّ المجموعة S هي مجال لأي دالة كلية متكرِّرة أو خالية. فإذا كانت S مجموعة مُطْلقة (أو لانهائية)، فإنّه يمكن اختيار الدالة في هذه الحالة لتصبح دالة متباينة.

قابلية الحسم جزئيًا:

في هذا الإطار، إنّ المجموعة S هي مجال لأي دالة بدائية متكرِّرة أو خالية. فحتى إذا كانت S مجموعة مُطْلقة (أو لانهائية)، فقد يكون من الضروريّ في هذه الحالة تكرار وإعادة القيِم العددية.

وفي هذا الصدد، إنّ المجموعة S مرقّمة بشكلٍ عوديّ (أو يمكن إحصاء تكرارها)، وهذا يعني أنّ S هي مجال (أو مجال مساوٍ) لأي دالة جزئية متكرِّرة.

الديوفانتية:

وفي السياق ذاته، إذا كان هناك كثيرة حدود رمزها P، وكانت تحتوي على المعاملات الصحيحة والمتغيرات x, a, b, c, d, e, f, g, h, i في نطاق مجموعة الأعداد الطبيعية بهذه الطريقة:

  • فيما يلي مثال على دالة جزئية متكرِّرة (F):
  • قابلية العد:
  • إنّ المجموعة S هي مجال لأي دالة جزئية متكرِّرة.

من جهة ثانية، ويمكن تحقيق التكافؤ بين قابلية الحسم جزئيًا وقابلية العد عن طريق استخدام منهج الدمج أو التداخل.

فيما يلي جميع الخصائص المتكافئة لمجموعة الأعداد الطبيعية S:

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.