قضیه پست
از ویکی‌پدیا، دانشنامهٔ آزاد.
 |
در متن این مقاله از هیچ منبع و ماخذی نام برده نشده‌است. شما می‌توانید با افزودن منابع بر طبق اصول اثبات‌پذیری و شیوه‌نامهٔ ارجاع به منابع، به ویکی‌پدیا کمک کنید. مطالب بی‌منبع احتمالاً در آینده حذف خواهند شد. |
در نظریهٔ محاسبات قضیهٔ پست، نام‌گرفته از امیل پست، رابطهٔ بینِ سلسله‌مراتب حسابی و درجهٔ تورینگ را نشان می‌دهد.
می‌گوییم زیرمجموعهٔ X از ω یک Σn است اگر فرمولِ Σn-ای با متغیر آزادِ n وجود داشته باشد که مقدارِ درست داشته باشد، اگر و فقط اگر n در X باشد.
به طور دقیق قضیهٔ پست می‌گوید:
- برای هر
، 
اگر و فقط اگر B یک مجموعهٔ بازگشتی محاسبه‌پذیر با یک غیب‌گو، از مجموعهٔ Πn-ای، یا به طورِ مترادف، از Σn-ای باشد.
, یعنی برای هر n > 0 ،n-اُمین جهش تورینگی مجموعه خالی Σn کامل است.
