قضیه پست

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

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

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

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

منابع

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. الگو:Isbn; الگو:Isbn
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. الگو:Isbnالگو:ریاضی-خرد