وقف في لغات غير تورينج كاملة

Question

لا يمكن حل مشكلة وقف للغات تورينج كاملة ويمكن حلها بشكل مسلي لبعض اللغات غير TC-مثل regexes حيث توقف دائما.

وأنا أتساءل عما اذا كان هناك أي اللغات التي على حد سواء القدرة على وقف ولا وقف لكنها تعترف خوارزمية يمكن تحديد ما إذا كان توقف.

Answer 1

نعم. واحد فئة هامة من هذا النوع هي مهام متكررة البدائية . وتشمل هذه الفئة جميع الأشياء الأساسية التي نتوقع أن تكون قادرة على القيام مع أرقام (الجمع والضرب، وما إلى ذلك)، وكذلك بعض الطبقات المعقدة مثل وقد ذكرadrian (التعابير العادية / لدن محدود، قواعد النحو خالية من السياق / تصميم التوسيع لأسفل لدن). هناك بذلك، ومع ذلك، توجد وظائف ليست متكررة البدائية، مثل أكرمان وظيفة .

وانها في الواقع من السهل جدا لفهم وظائف متكررة البدائية. انهم الوظائف التي يمكن أن تحصل في لغة البرمجة التي ليس لديها العودية الحقيقية (حتى وظيفة و لا يمكن استدعاء نفسها، سواء بشكل مباشر أو عن طريق استدعاء الدالة ز آخر ثم يدعو و، الخ) وليس لديها بينما الحلقات، بدلا من ذلك بعد أن يحدها لالحلقات. ويحدها لحلقة واحدة مثل "لأنني من 1 إلى ص" حيث r هو المتغير الذي سبق حسابها في البرنامج في وقت سابق. أيضا، أنا لا يمكن تعديلها ضمن حلقة ل. وجهة مثل لغة البرمجة هي أن <م> كل يوقف البرنامج.

ومعظم البرامج نكتب هي في الواقع البدائية العودية (أعني، يمكن أن يترجم إلى هذه اللغة).

Answer 2

مشكلة وقف لا يتصرف في اللغات. بدلا من ذلك، فإنه يعمل على الأجهزة (أي البرامج): يسأل ما إذا كان برنامج معين يوقف على مدخلات معينة

وربما كنت تعني أن نسأل ما إذا كان يمكن حلها عن نماذج أخرى من حساب (مثل التعابير العادية، التي أذكر لكم، ولكن أيضا مثل دفع إلى أسفل الآلي ).

ووقف يمكن، بشكل عام، يتم الكشف عن نماذج في بموارد محدودة (مثل التعابير العادية أو مكافئ، الآلي المحدودة، التي لديها الثابتة عدد من الدول وعدم تخزين خارجي). ويتم إنجاز هذا بسهولة عن طريق تعداد كافة التشكيلات الممكنة وفحص ما إذا كان الجهاز يدخل نفس التكوين مرتين (مما يشير إلى حلقة لا نهائية)؛ مع محدود الموارد، ونحن يمكن أن يضع حدا أعلى على مقدار الوقت قبل أن <م> يجب رؤية تكوين المتكررة إذا كان الجهاز لا توقف.

وعادة، ونماذج بموارد لانهائية (ذاكرات الترجمة وأجهزة المساعد الرقمي الشخصي غير محدود، على سبيل المثال)، لا يمكن وقف إيداعه، ولكن سيكون من الأفضل للتحقيق في النماذج و مشاكلهم مفتوحة بشكل فردي.

و(عذرا لجميع الروابط ويكيبيديا، ولكنه في الواقع موردا جيدا للغاية ل هذا النوع من الأسئلة.)

Answer 3

والجواب القصير هو نعم، ويمكن لمثل هذه اللغات حتى تكون مفيدة للغاية.

وكان هناك نقاش حول هذا الموضوع قبل بضعة أشهر على LTU: http://lambda-the-ultimate.org/node/2846