قضیه پست

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

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

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

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