هل هناك لغات في $ \ Mathsf {core} \ setminus \ mathsf {r} $ have آلات turing؟

Question

ماذا يمكننا أن نقول عن اللغات في $ \ mathsf {core} \ setminus \ mathsf {r} $ ؟هل هناك آلات تورينج لهذه اللغات؟

أعرف أن $ \ overline {hp} \ in \ mathsf {core} $ لا يحتوي على آلة turing، وكذلك كل اللغة التي تفعلتناول آلات Turing في $ \ mathsf {re} $ ، فهل صحيح عن أي لغة في $ \Mathsf {core} \ setminus \ mathsf {r} $ لا يوجد آلة turing؟أتساءل لماذا هو ذلك، هل يمكن لشخص ما وضعه؟

Answer 1

يمكننا ربط لغة لجهاز Turing بعدة طرق.

إذا توقف آلة Turing على جميع المدخلات، فإن اللغة المقبول من خلال آلة Turing تتكون من جميع الكلمات التي تتسبب في وقف آلة Turing في حالة قبولها. يتكون A $ Class Class="حاوية الرياضيات"> $ \ Mathsf {r} $ من جميع اللغات التي تم قبولها بواسطة بعض آلة Turing.

للحصول على آلة تورينج التعسفي، تتكون لغة المعترف بها بواسطة آلة Turing من جميع الكلمات التي تسبب آلة turing لوقف (في أي حالة). يتألف من جميع اللغات التي يتم التعرف عليها بواسطة بعض اللغات.

إذا كنت $ l \ in \ mathsf {core} \ setminus \ mathsf {r} $ ، ثم على وجه الخصوص $ l \ notin \ mathsf {r} $ ، وبالتالي لا تقبل أي آلة turing $ l $ . إذا تم التعرف على $ L $ بواسطة بعض آلة turing ثم $ l \ in \ mathsf {re} $ . ومع ذلك، هذا مستحيل، منذ ذلك الحين $ l \ in \ mathsf {re} \ cap \ mathsf {core}=mathsf {r} $ .

Answer 2

اسمحوا لي أن أتوسع في الجملة الأولى من إجابة Filmus Yuval:

يمكننا ربط لغة لجهاز Turing بعدة طرق.

yuval يذكر اثنين: قبول (الذي يميز $ \ mathsf {r} $ ) و التعرف على ( التي تميز $ \ mathsf {re} $ ). هناك آخرون، ومع ذلك. الأكثر وضوحا، يمكننا النظر في "التعرف التعاوني" - قل أن آلة تورينج $ M $ "التعايش التعرف على" لغة $ L $ إذا كانت السلاسل في $ L $ هي بالضبط السلاسل التي $ m $ هل توقف . بعد ذلك، تميز التعرف المشارك بالطبع $ \ mathsf {core} $ .

ومع ذلك، هذا غير طبيعي بعض الشيء. أكثر طبيعية في رأيي هو فكرة الحد من الحماية . صياغة من حيث الأرقام الطبيعية للبساطة، وهذا ما يلي:

وظيفة $ f: \ mathbb {n} \ rawrow \ mathbb {n} $ هو الحد المحدد IFF هناك حساب حسابي وظيفة $ h: \ mathbb {n} ^ 2 \ rawrow \ mathbb {n} $ مثل هذا $$ f (x )=lim_ {s \ rawrow \ infty} h (x، s)، $ أو أكثر بدقة مثل هذا $ x $ هناك بعض $ n $ مثل كل $ s> n $ لدينا $ h (x، s)= f (x) $ .

مجموعة مجموعة $ X $ هو الحد المحسم، وفي الوقت نفسه، IFF هناك بعض الوظائف المحددة المحددة $ f $ مثل هذا $ x={i: f (i)= 1 \} $ . (هناك العديد من التركيبات المكافئة الأخرى لهذا.)

اتضح أن الحد الأقصى للحساب لديه وصف بديل لطيف للغاية:

(shoenfield) وظيفة $ f $ هو الحد المحسوبية IFF IFF هو محسوبة بالنسبة إلى مشكلة وقف $ \ emptyset '$ .

(وعبر النشر نحصل على توصيف آخر من حيث "التعقيد التعريفي". ")

بالطبع يتضمن ذلك كل من $ \ mathsf {re} $ و $ \ mathsf {core} $ ، وأكثير أكثر من ذلك بكثير: هناك مجموعات محسوبة بالنسبة لمشكلة توقف المشكلة والتي لا تتلقى مكافئ لأي مجموعة في $ \ mathsf {re} $ . (من الصعب إثبات ذلك!)

وهناك المزيد من الطرق لتعيين اللغات للحزانات؛ على سبيل المثال، يمكننا التحدث عن "الحد من التعرف" (الذي يتمثل في الحد من الحساب هو التعرف على القبول)، مما يعطينا $ \ sigma ^ 0_2 $ اللغات.