كيفية فهم تعريف $ \ Pick $ في التسلسل الهرمي الحسابي

Question

أنا أقرأ نصا حول نظرية الكمبيوتر، ووفقا للنص، في كل مستوى $ K $ من التسلسل الهرمي الحسابي، لدينا مجموعتين، $ \ sigma_k $ و $ \ pi_k $ ، حيث $ \ pi_k $ يتم تعريف على النحو التالي:

$$ \ pi_k= co- \ sigma_k

بحيث

$ k= 0 $ ، لدينا فئة من مجموعات حلولها و $ \ sigma_0=pi_0 $ ، ول $ k= 1 $ ، لدينا $ \ sigma_1 $ as the فئة من مجموعات غير قابلة للتعدي (CE) و $ \ pi_1 $ كصف واحد من مجموعات غير قابلة للتعدي (وليس CE) ....

دع $ l (m_e) $ تدل على اللغة المعترف بها بواسطة آلة Turing $ m_e $ مع godel رقم $ e $ . جئت عبر اللغة التالية $ e $ ، حيث:

$$ E={E | L (M_E)=Sigma ^ *} $$

ie.e. $ e $ هي لغة جميع رموز آلة turing $ e $ التي تعد غير قابلة للتعدي. من خلال حجة قطرية، يمكن أن تظهر أن $ e $ ليس c.e. هذا يعني أن:

$$ ه \ في \ pi_1

ومع ذلك، إذا كان $ e \ in \ pi_1 $ ، فهذا يعني أن $ E= CO-A $ بالنسبة لبعض $ a \ sigma_1 $ ، باستخدام التعريف في العبارة أعلاه ... ومع ذلك، فإن تكمل $ e $ هو:

$$ \ Overline {e}=overline {\ {e | l (m_e)=sigma ^ * \}}

أي (أعتقد) يعني أن $ \ overline {e} $ هي لغة جميع أجهزة Turing $ e $ مثل ذلك على بعض المدخلات، $ e $ يتباعد ... ومع ذلك، فقد تبين أن $ \ Overline {e} \ equiv_m k ^ {2} $ ، أي $ \ overline {e} \ equiv_m k ^ k $ ، بحيث بالنظر إلى مجموعتين $ $ و $ B $ ، لدينا $ a \ equiv_m b $ IFF $ a \ leq_m b $ و $ b \ leq_m a $ < / span>، و $ \ leq_m $ يشير إلى الحد الأقصى لخفضها:

$$ \ Overline {e} \ equiv_m k ^ k \ in \ sigma_2

بالنظر إلى أن $ \ sigma_2 \ neq \ sigma_1 $ ، يبدو مثل هذا $ \ overline {e} $ < / span> غير قابل للتعدي بشكل كبير ... ولكن لا يتناقض هذا تعريف $ \ pi_1 $ والتي تنص على أن تكملها المجموعة C.E. ؟

أعتقد أن أفتقد شيئا في فهمي للتعريفات ...

Answer 1

for $ k $ حتى، لغة $ l $ هي في $ \ pi_k $ إذا كان هناك موجودة أداة التسديد العودية $ r $ مثل ذلك $$ x \ in l \ longleftrightrogle \ forall y_1 \ exist y_2 \ cdots \ forall y_ {k-1} \ {k-1} \ {k-1} \ {x، r (x، y_1، \ ldots، y_k) $ الكميات البديل بين $ \ forall $ $ \ exist $ .

عندما $ k $ أمر غريب، يعمل نفس التعريف، ولكن آخر الكم هو $ \ forall $ : $$ X \ في l \ longleftrightrightrow \ forall y_1 \ exist y_2 \ cdots \ exist y_ {k-1} \ forall y_k \، r (x، y_1، \ ldots، y_k)

على سبيل المثال، لغة جميع أجهزة Turing الكلية هي $ \ pi_2 $ منذ ذلك الحين $$ x \ in \ in \ mathsf {tot} \ longleftrightrightarrow \ forall y \ exist z \ {} $ x $ x $} $ x $ y dates $ z $}

الفئة $ \ sigma_k $ يتم تعريفها بنفس الطريقة، مع وجود أول الكم $ \ exist $ < / span> بدلا من $ \ forall $ .

إذا كنت تكمل لغة في $ \ sigma_k $ تحصل على واحدة في $ \ pi_k $ ، والعكس صحيح. ويرجع ذلك إلى قوانين دي مورغان للأكمام، وحقيقة أن نفي المسند العريط يتكرر أيضا.

على سبيل المثال، لغة غير - آلات TuringTal TuringTal هي $ \ sigma_2 $ منذ ذلك الحين $$ x \ in \ at \ mathsf {ntot} \ longleftrightrightrow x \ notin \ mathsf {tot} \ longleftrightrow \ exist y \ forall z \ z \ text {} $ x $ لا تتوقف عن الإدخال $ Y ضمن $ z $ z "}