ما هي الإرشادات العملية لتقييم "اكتمال" اللغة؟
https://stackoverflow.com/questions/449014
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا قد قرأت "ماذا-هو مكتمل" وصفحة ويكيبيديا ، لكنني أقل اهتمامًا بإثبات رسمي مقارنة بالآثار العملية المتمثلة في أن تكون Turing كاملة.
ما أحاول بالفعل أن أقرره هو ما إذا كانت لغة الألعاب التي صممتها للتو يمكن استخدامها كلغة للأغراض العامة. أعلم أنه يمكنني إثبات أنه إذا كان بإمكاني كتابة آلة تورينج معها. لكني لا أريد أن أذهب إلى هذا التمرين حتى أكون متأكداً من النجاح.
هل هناك حد أدنى من الميزات التي بدون اكتمال تورينج مستحيل؟ هل هناك مجموعة من الميزات التي تضمن الاكتمال تقريبًا؟
(أظن أن هذا المتفرعة الشرطية ومتجر ذاكرة قابل للقراءة/القابل للكتابة سيحصل على معظم الطريق إلى هناك)
تعديل:
أعتقد أنني خرجت من الظل بقول "Turing كاملة". أحاول أن أخمن بثقة معقولة أن لغة تم اختراعها حديثًا مع مجموعة ميزة معينة (أو بالتناوب ، VM مع مجموعة تعليمات معينة) ستكون قادرة على حساب أي شيء يستحق الحوسبة. أعلم أن بإمكانك بناء آلة تورينج معها هي طريقة واحدة ، ولكن ليس الطريقة الوحيدة.
ما كنت آمل فيه هو مجموعة من الإرشادات مثل: "إذا كان بإمكانها القيام بـ X و Y و Z ، فيمكنها المحتمل افعل أي شيء".
المحلول
تحتاج إلى بعض أشكال بناء التخصيص الديناميكي (malloc أوnew أو cons سوف تفعل) وإما الوظائف العودية أو طريقة أخرى لكتابة حلقة لا حصر لها. إذا كان لديك هؤلاء ويمكنك فعل أي شيء على الإطلاق مثير للاهتمام ، فمن المؤكد أنك تكتمل.
حساب حساب Lambda مكافئ في الطاقة لآلة Turing ، وإذا قمت بتطبيق حساب حساب Lambda ، فمن الممتع في الواقع كتابة برامج حساب حساب Lambda. طريق أكثر متعة من برنامج الكتابة لآلة تورينج!
إن التأثير العملي الوحيد لتكامل التورينج الذي أدركه هو أنه يمكنك كتابة البرامج التي لا تنتهي. لقد استخدمت بعض اللغات ذات الأغراض الخاصة التي تضمن الإنهاء وبالتالي فهي ليس Turing-Complete. في بعض الأحيان يكون من المفيد التخلي عن الطاقة التعبيرية الإضافية في مقابل الإنهاء المضمون.
نصائح أخرى
"اكتمال تورينج" يصف خاصية القدرة على التعبير عن أي تعسفي حساب الخوارزمية ، الذي كان الهدف من آلة تورينج في المقام الأول. يمكن وصف اللغة أو النظام المنطقي بأنه "Turing كاملة" إذا كان لديها هذه الخاصية. من المنظور العملي ، يمكن لجميع لغات البرمجة للأغراض العامة - وعدد كبير من الأغراض الخاصة بشكل مدهش - القيام بذلك من أجل تعريف فضفاض بشكل مناسب (انظر أدناه).
ومع ذلك ، فإن التعريف الصارم لاكتمال Turing ينطوي على سعة تخزين غير محدودة ، وهو بالطبع غير ممكن جسديًا. بالنظر إلى هذا ، لا يمكن أن يكون أي آلة فعلية كاملة ، ولكن عادةً ما يتم استرخاء هذا القيد (على الأقل بشكل غير رسمي) عند إكمال اكتمال Turing إلى لغة البرمجة. أحد الاختبارات التافهة لاكتمال Turing للغة ما هو ما إذا كان يمكن استخدام اللغة لتنفيذ محاكاة آلة Turing.
مثال على نظام واسع الانتشار غير الكامل هو الجبر العلائقي ، الأساس النظري وراء SQL كما هو موضح في ورقة CODD نموذج علائقي لبنوك البيانات المشتركة الكبيرة. الجبر العلائقي له ملك اكتمال جوديل, مما يعني أنه يمكن أن يعبر عن أي حساب يمكن تعريفه من حيث حساب حساب المسند الأول من الدرجة الأولى (أي التعبيرات المنطقية العادية). ومع ذلك ، فإنه ليس مكتملًا لأنه لا يمكنه التعبير عن حساب خوارزمي تعسفي.
لاحظ أن معظم لهجات SQL العملية إن لم تكن جميعها تعمل على تمديد النموذج العلائقي الخالص مع بنيات إجرائية إلى الحد الذي تتم فيه إكمالها من خلال التعريف كما هو مطبق عادة على لغات البرمجة. ومع ذلك ، فإن استعلام SQL الفردي من قبل إلى حد كبير ليس كذلك.
بعض الأمثلة الفظيعة للغات الكاملة للمجال الخاصة تكس و sendmail.cf ،. في الحالة الأخيرة ، يوجد في الواقع مثال مشهور لشخص يستخدم sendmail.cf تنفيذ محاكاة آلة تورينج العالمية.
إذا كنت تستطيع كتابة أ Brainf $ &# المترجم في لغتك ، إنه مكتمل. lolcode ثبت أن تورنج مكتمل بهذه الطريقة بالضبط.
أمثلة على اللغات التي لا تكتمل بشكل متكرر حلقات محددة, ، مثل:
for i=1 to N {...}لكن الافتقار غير محدود الحلقات التي تحقق حالة أكثر عمومية ، مثل:
while bool_expr {...}إذا كانت جميع بنيات الحلقات الممكنة محدودة ، يتم ضمان برنامجك. وعلى الرغم من أن ضمان الإنهاء غير المشروط أمر مفيد ، إلا أنه مؤشر على أن اللغة لا تكتمل.
لاحظ أيضًا أن تسمير الأسفل كله ممكن يمكن أن تكون بنيات الحلقات صعبة ؛ على سبيل المثال ، أنا متأكد تمامًا من أن قوالب C ++ لم يكن المقصود منها أن تكون مكتملة ...
لست متأكدًا مما إذا كان هناك "مجموعة أدنى من الميزات" ، ولكن لإثبات أن اللغة كاملة ، عليك فقط إثبات أنه يمكن أن تحاكي نظامًا كاملًا آخر (وليس بالضرورة آلة تورينج) ، طالما من المعروف أن نظام آخر هو turing كاملة. http://en.wikipedia.org/wiki/turing_complete#examples لديه قائمة كاملة من Turing الأنظمة الكاملة. بعضها أبسط من آلات تورينج.
أرغب في إضافة تحذير واحد إلى ما قاله نورمان رامزي: إن آلة تورينج لها ذاكرة لا حصر لها ، وبالتالي فإن لغات البرمجة التي تعتبر تورونج كاملة هي فقط على افتراض أن الذاكرة غير محدودة أيضًا.
Brainfuck هو Turing كامل ، وله هياكل حلقة فقط وزيادة/انخفاض الذاكرة لذلك هذا يكفي.
من ناحية أخرى ، لا توجد وسيلة لتعديل أي قيمة في حساب حساب Lambda ، ولكن من الممكن أن تفعل ذلك دون ذاكرة قابلة للتغيير.
على الأرجح أن البرنامج لا علاقة له بتكامل Lambda ، لذلك يجب أن يكون الحد الأدنى للإجابة العملية
- طريقة للكتابة إلى متغير
- طريقة للقراءة لمتغير
- شكل من أشكال GOTO الشرطية (إذا كان البيان ، بينما الحلقة ، إلخ)
لا أستطيع أن أتذكر رؤية أي شيء مثل الحد الأدنى للميزات لاكتمال تورينج. ومع ذلك ، إذا كانت لغتك تدعم الحلقات والفروع الشرطية ، فإن فرص تورنج كاملة. ومع ذلك ، فإن الطريقة الوحيدة لإثبات أنها لا تزال تشابه آلة تورينج أو لغة أخرى كاملة.
إذا تمكنت من تنفيذ جهاز تورينج (بقدر ما يمكن تنفيذه ، حيث يتم بنيات رياضية بذاكرة غير محدودة [حجم الشريط هو infinte]) فيمكنك التأكد من أنها كاملة.
بعض المؤشرات:
- يمكنك التحقق من الذاكرة ومعالجتها بناءً على القيمة الحالية وكذلك استخدامها للتحكم في تدفق البرنامج.
- يمكن تخصيص هذه الذاكرة ، والسلاسل التي يمكنك إلحاقها ، وهي مكدس يمكنك تخصيص الذاكرة من خلال العودية وما إلى ذلك.
- يمكن أن يكون تدفق البرنامج من خلال التكرار أو من خلال التكرار القائم على الاختيار.
أي لغة قادرة على عدم الانتهاء هو turing إلى حد كبير. يمكنك جعل لغة غير قادرة على إنهاء من خلال إعطائها هياكل حلقات غير محدودة (مثل أثناء الحلقات أو GOTO التي يمكن أن تصل إلى نفسها مرة أخرى) ، أو عن طريق إعطائها عودية عامة (عن طريق السماح بوظيفة تدعو نفسها دون تقييد.)
بمجرد نكون Turing Complete ، يمكنك القيام بأشياء مثل تفسير اللغات الكاملة الأخرى ، بما في ذلك.
السؤال الحقيقي هو "ما هو جيد؟" إذا تم استخدام لغتك في مجال معين لحل مشاكل محددة ، فقد يكون من الأفضل إيجاد طريقة لعبارة الحلول بلغة غير كاملة ، وبالتالي مضمونة لإعطاء إجابة.
يمكنك دائمًا إضافة اكتمال Turing عن طريق كتابة "قم بذلك ، أو أي شيء ؛ ولكن القيام بذلك بالنتيجة التي توفرها X" في أي لغة أخرى كاملة ، حيث يتم توفير X من خلال لغة كاملة غير الترجيح.
بالطبع ، إذا كنت ترغب في استخدام لغة واحدة فقط ، فمن الأفضل أن يكون من الأفضل تورينج ...
يمكنك محاولة محاكاة OISC (جهاز كمبيوتر واحد للتعليمات). إذا تمكنت من محاكاة إحدى الإرشادات هناك ، فمنذ أن هذه التعليمات الفردية يمكن استخدامها لتكوين جهاز كامل ، فقد أثبتت أن لغتك يجب أن تكون كاملة أيضًا.
هل هناك حد أدنى من الميزات التي بدون اكتمال تورينج مستحيل؟ هل هناك مجموعة من الميزات التي تضمن الاكتمال تقريبًا؟
نعم ، تحتاج إلى تدفق التحكم الشرطي على البيانات: ما يتم التعبير عنه غالبًا if. على سبيل المثال أ +-*/ حاسبة الجيب ليست كاملة ، حيث لا توجد وسيلة للتعبير عن الشرطية.
تحتاج أيضًا إلى أن تكون قادرًا على التعبير عن القفز إلى نقطة سابقة في البرنامج ، والتي يمكنك من خلالها تنفيذ حلقة. على سبيل المثال BPF ، الذي يمنع القفزات للخلف لضمان إنهاء البرنامج ، لم يكتمل أيضًا.
أنت بحاجة إلى بعض التخزين القابل للقراءة وقابل للكتابة وكبيرة بشكل تعسفي. على سبيل المثال ، فإن اللغة التي تحتوي على متغيرين 32 بت فقط محدودة في ما يمكن أن يحسب. لديك العديد من الخيارات لكيفية تنظيم التخزين: الذاكرة التي تناولتها المؤشرات ، المصفوفات ، المداخن ، خلايا السلبيات ، هياكل البيانات الخالصة ، إلخ.
علاوة على ذلك ، يمكنك بناء كل لغة برمجة أخرى: قد لا تكون سهلة أو سريعة ، لكنها كافية.
... مما هو عليه في الآثار العملية لكونه turing كاملة.
أشك في أن هناك أي آثار عملية على أن يكون Turing كاملة.
إذا نظرت إلى بعض الأمثلة على الآلات الكاملة Turing ، على سبيل المثال ، الأصل آلة تورينج, ، سترى أن هذا بعيد جدًا عن كونه مفيدًا للحسابات الحقيقية بحيث يجب أن يكون المفهوم ذا أهمية نظرية فقط.
