قضیه پست

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

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

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

 منابع 
 Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ; 
 Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. 

رده:سلسله‌مراتب منطق ریاضیاتی
رده:قضایای بنیان‌های ریاضیات
رده:قضیه‌های ریاضی
رده:نظریه بازگشت