مجموعات العودية مقابل الوظائف العودية

Question

ما هو الفرق بين مجموعة متكررة وظيفة العودية؟

Answer 1

وظائف العودية والمجموعات العودية هي المصطلحات المستخدمة في نظرية الكمبيوتر. تعرفهم ويكيبيديا على النحو التالي:

يقال إن مجموعة من الأرقام الطبيعية هي مجموعة محسنة (تسمى أيضا مجموعة محسنة جدا أو متكررة أو تورينج أو تورينج) إذا كان هناك آلة تورينج، مع إعطاء رقم N، توقف مع الإخراج 1 إذا كان N في المجموعة والتسال مع الإخراج 0 إذا كان n ليس في المجموعة. وظيفة من الأرقام الطبيعية لأنفسها هي وظيفة مكانية أو (تورينج) محوسة إذا كان هناك آلة تورينج تعمل، على الإدخال n، توقف وإرجاع الإخراج f (n).

في هذا السياق، لا تعني الوظيفة العديدة وظيفة في لغة البرمجة تستدعي نفسها. أي الرياضيات الوظيفة التي تلبي متطلبات التعريف أعلاه هي وظيفة متكررة، بما في ذلك تلك التافهة مثل وظيفة الهوية أو تعيين وظيفة جميع الأرقام إلى 1 (أي إرجاع الرقم 1 بغض النظر عن الإدخال).

Answer 2

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

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

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

يترك F يتم تعريفه كدالة حيث f (x) = 1 لو X ∈ ∈. و f (x) = 0 لو X ∉ ∉.

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

هذا حيث مفهوم وظيفة العودية يأتي في اللعب، كدالة متكررة (أو إجمالي وظيفة العودية) يمكن حسابها بواسطة آلة تورينج وتتوقف لكل إدخال. حيث يمكن حساب وظيفة متكررة جزئية فقط لجهاز Turing بدون أي ضمان فيما يتعلق بوقف السلوك. أو في جوهرها وظيفة العودية هي النظير إلى مجموعة العودية.

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

قراءة متعمقة:

• M. Siper - مقدمة لنظرية الحساب (الطبعة الثانية)
• جي هوبكروفت، ر. معاني، دينار jd ullman - مقدمة في نظرية السيارات واللغات والحساب (الطبعة الثالثة)
• Hr Lewis، Chapadimitriou - عناصر نظرية الحساب (الطبعة الثانية)
• fd لويس - أساسيات علوم الكمبيوتر النظرية (النص الرقمي)

Answer 3

ربما كان يجب أن يكون السؤال "لماذا تعتاد كلمة" العودية "لوصف كلا المجموعتين والوظائف؟"

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

أعتقد أن الاقتباس من Wikipedia يستخدم مصطلح "العودية" كمرادف "بحساب" - الذي نتوافق عليه، كمبرمجين، بحذر مع، ولكن فقط في سياقات معينة فقط.