قضیه پست

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

می‌گوییم زیرمجموعهٔ $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}\!$ کامل است.

منابع

• 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. شابک ‎۳−۵۴۰−۱۵۲۹۹−۷