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