قضیه پست

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

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

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

• برای هر $n \geq 0 \!$، $B \in \Sigma_{n+1} \!$ اگر و فقط اگر $B \!$ یک مجموعهٔ بازگشتی محاسبه‌پذیر با یک غیب‌گو، از مجموعهٔ $\Pi_n \!$-ای، یا به طورِ مترادف، از $\Sigma_n \!$-ای باشد.

• $\emptyset^{(n)} \!$، یعنی برای هر $n > 0 \!$ ،n-اُمین جهش تورینگی مجموعه خالی $\Sigma_n \!$ کامل است.