English  

كتب identification by group

اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.

عرض المزيد

التعريف بواسطة مجموعة (معلومة)


الشكل الاعتيادي لمسائل التقرير يكون على شكل مجموعة من الاشياء التي تحقق السؤال. مجموعة التوقف (halting set) هي:

{البرنامج i سوف يتوقف في حين أن x هو المدخل للبرنامج |(K:= {(i,x

وهذه المجموعة تمثل مسألة التوقف وهي مجموعة مجموعة مرقمة بشكل تراجعي اي انه يوجد دالة قابلة للحساب التي تعدد كل زوج (i,x) ولكن المجموعة المكملة غير قابلة للترقيم أو التعداد.

يوجد الكثير من المسائل التي هي اعادة صياغة لمسألة التوقف حيث أن كل مسألة يوجد لها نفس درجة تيورنج هي كذلك. امثلة لمجموعات كهذه منها:

  • { i | برنامج i سوف يتوقف عندما نشغله مع المدخل 0 }
  • { i | يوجد مدخل x بحيث أن البرنامج i سوف يتوقف على المدخل x }.
المصدر: wikipedia.org