قضیه پست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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