حساب کاربری
​
زمان تقریبی مطالعه: 1 دقیقه
لینک کوتاه

قضیه پست

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

می‌گوییم زیرمجموعهٔ X {\displaystyle X\!}

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

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

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