قضیه پست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریهٔ محاسبه‌پذیری قضیهٔ پست، نام‌گرفته از امیل پست، رابطهٔ بینِ سلسله‌مراتب حسابی و درجهٔ تورینگ را نشان می‌دهد.

می‌گوییم زیرمجموعهٔ از یک است اگر فرمولِ -ای با متغیر آزادِ وجود داشته باشد که مقدارِ درست داشته باشد، اگر و فقط اگر در باشد.

به طور دقیق قضیهٔ پست می‌گوید:

  • برای هر ، اگر و فقط اگر یک مجموعهٔ بازگشتی محاسبه‌پذیر با یک غیب‌گو، از مجموعهٔ -ای، یا به طورِ مترادف، از -ای باشد.
  • ، یعنی برای هر ،n-اُمین جهش تورینگی مجموعه خالی کامل است.