قضیه پست

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

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

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

• برای هر ${\displaystyle n\geq 0\!}$، ${\displaystyle B\in \Sigma _{n+1}\!}$ اگر و فقط اگر ${\displaystyle B\!}$ یک مجموعهٔ بازگشتی محاسبه‌پذیر با یک غیب‌گو، از مجموعهٔ ${\displaystyle \Pi _{n}\!}$-ای، یا به طورِ مترادف، از ${\displaystyle \Sigma _{n}\!}$-ای باشد.
• ${\displaystyle \emptyset ^{(n)}\!}$، یعنی برای هر ${\displaystyle n>0\!}$ ،n-اُمین جهش تورینگی مجموعه خالی ${\displaystyle \Sigma _{n}\!}$ کامل است.