ما هو تورينج الكامل؟
https://stackoverflow.com/questions/7284
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
ماذا تعني عبارة "Turing Complete"؟
هل يمكنك تقديم تفسير بسيط، دون الخوض في الكثير من التفاصيل النظرية؟
المحلول
وإليكم التوضيح الأبسط:
نظام تورينج الكامل يعني نظام يمكن فيه كتابة برنامج سيجد إجابة (على الرغم من عدم وجود ضمانات فيما يتعلق بوقت التشغيل أو الذاكرة).
لذلك، إذا قال شخص ما "الشيء الجديد الخاص بي هو Turing Complete" فهذا يعني من حيث المبدأ (على الرغم من أنه ليس عمليًا في كثير من الأحيان) أنه يمكن استخدامه لحل أي مشكلة حسابية.
أحياناً تكون مزحة..كتب رجل محاكاة آلة تورينج في السادس، لذلك من الممكن أن نقول أن السادس هو المحرك الحسابي الوحيد المطلوب في العالم.
نصائح أخرى
هنا هو أبسط تفسير
أنشأ آلان تورينج آلة يمكنها أخذ برنامج وتشغيل هذا البرنامج وإظهار بعض النتائج.ولكن بعد ذلك كان عليه إنشاء آلات مختلفة لبرامج مختلفة.لذلك قام بإنشاء "آلة تورينج العالمية" التي يمكنها أخذ أي برنامج وتشغيله.
تشبه لغات البرمجة تلك الآلات (رغم أنها افتراضية).يأخذون البرامج ويديرونها.الآن، تُسمى لغة البرمجة "Turing Complete"، إذا كان بإمكانها تشغيل أي برنامج (بغض النظر عن اللغة) يمكن لآلة Turing تشغيله مع توفير الوقت والذاكرة الكافيين.
على سبيل المثال:لنفترض أن هناك برنامجًا يأخذ 10 أرقام ويضيفها.يمكن لآلة تورينج تشغيل هذا البرنامج بسهولة.لكن تخيل الآن لسبب ما أن لغة البرمجة الخاصة بك لا تستطيع القيام بنفس الإضافة، إذن فإن آلة تورينج غير مكتملة.من ناحية أخرى، إذا كان بإمكانه تشغيل أي برنامج مثل ما يمكن لآلة تورينج العالمية تشغيله، فهذا يعني أن برنامج تورينج مكتمل.
معظم لغات البرمجة الحديثة مثل Java وJavaScript وPerl وغيرها كلها مكتملة لأنها جميعها تنفذ جميع الميزات المطلوبة لتشغيل البرامج مثل الجمع والضرب وشرط if-else وعبارات الإرجاع وطرق تخزين/استرداد/محو البيانات وما إلى ذلك. .
تحديث:يمكنك معرفة المزيد في منشور مدونتي: "اكتمل تورينج JavaScript" — موضح
من ويكيبيديا:
يعد اكتمال Turing ، الذي سمي على اسم Alan Turing ، مهمًا في أن كل تصميم معقول لجهاز الحوسبة المتقدم حتى الآن يمكن أن يتم محاكاته بواسطة آلة تورينج عالمية-وهي ملاحظة أصبحت تُعرف باسم أطروحة الكنيسة.وبالتالي ، يمكن للجهاز الذي يمكن أن يعمل كآلة تورينج عالمية ، من حيث المبدأ ، إجراء أي عملية حسابية يمكن لأي جهاز كمبيوتر آخر قابل للبرمجة قادرًا عليه.ومع ذلك ، لا علاقة لهذا الجهد المطلوب لكتابة برنامج للجهاز ، والوقت الذي قد يستغرقه الجهاز لإجراء الحساب ، أو أي قدرات قد تمتلكها الجهاز لا علاقة لها بالحساب.
على الرغم من أن الآلات الكاملة حقًا من المحتمل أن تكون مستحيلة جسديًا ، حيث إنها تتطلب تخزينًا غير محدود ، إلا أن اكتمال Turing غالبًا ما يعزى بشكل فضفاض إلى الآلات المادية أو لغات البرمجة التي ستكون عالمية إذا كانت لديهم تخزين غير محدود.جميع أجهزة الكمبيوتر الحديثة تتكامل بهذا المعنى.
لا أعرف كيف يمكنك أن تكون غير تقني أكثر من ذلك إلا بقول "التحويل الكامل يعني" القدرة على الإجابة على مشكلة قابلة للحساب مع توفير الوقت والمساحة الكافية "".
تعريف غير رسمي
لغة تورينج الكاملة هي اللغة التي يمكنها إجراء أي عملية حسابية.ال أطروحة الكنيسة تورينج ينص على أن أي عملية حسابية قابلة للتنفيذ يمكن إجراؤها بواسطة آلة تورينج.أ آلة تورينج هي آلة ذات ذاكرة وصول عشوائي لا نهائية و"برنامج" محدود يملي عليها متى يجب أن تقرأ، وتكتب، وتتحرك عبر تلك الذاكرة، ومتى يجب أن تنتهي بنتيجة معينة، وما يجب عليها فعله بعد ذلك.يتم وضع المدخلات إلى آلة تورينج في ذاكرتها قبل أن تبدأ.
الأشياء التي يمكن أن تجعل اللغة غير تورينج كاملة
يمكن لآلة تورينج اتخاذ القرارات بناءً على ما تراه في الذاكرة - "اللغة" التي تدعم فقط +, -, *, ، و / على الأعداد الصحيحة، لا يعد تورينج مكتملًا لأنه لا يمكنه الاختيار بناءً على مدخلاته، لكن آلة تورينج يمكنها ذلك.
يمكن لآلة تورينج أن تعمل إلى الأبد - إذا أخذنا Java أو Javascript أو Python وقمنا بإزالة القدرة على القيام بأي نوع من الحلقات أو GOTO أو استدعاء الوظائف، فلن يكون Turing كاملاً لأنه لا يمكنه إجراء عملية حسابية عشوائية لا تنتهي أبدًا. كوك هو مُبرهن نظري لا يمكنه التعبير عن البرامج التي لا تنتهي، لذا فهو ليس تورينج كاملاً.
يمكن لآلة تورينج استخدام ذاكرة غير محدودة - اللغة التي تشبه لغة Java تمامًا ولكنها تنتهي بمجرد استخدامها لأكثر من 4 غيغابايت من الذاكرة لن تكون لغة تورينج كاملة، لأن آلة تورينج يمكن أن تستخدم ذاكرة غير محدودة.وهذا هو السبب في أننا لا نستطيع في الواقع يبني آلة تورينج، ولكن جافا لا تزال لغة تورينج كاملة لأن جافا لغة ليس لديه أي قيود تمنعه من استخدام الذاكرة اللانهائية.هذا هو أحد أسباب عدم اكتمال تورينج للتعبيرات العادية.
تحتوي آلة تورينج على ذاكرة وصول عشوائي - لغة تتيح لك العمل بالذاكرة فقط push و pop العمليات على المكدس لن تكتمل مع تورينج.إذا كان لدي "لغة" تقرأ سلسلة مرة واحدة ويمكنه فقط استخدام الذاكرة عن طريق الدفع والخروج من المكدس، ويمكنه إخباري ما إذا كان كل ذلك ( في السلسلة لديها خاصة بها ) في وقت لاحق عن طريق الضغط عندما يرى ( وظهرت عندما ترى ).ومع ذلك، لا يمكن أن تخبرني إذا كان كل ( لديها خاصة بها ) لاحقا و كل [ لديها خاصة بها ] في وقت لاحق (لاحظ ذلك ([)] يستوفي هذه المعايير ولكن ([]] لا).يمكن لآلة تورينج استخدام ذاكرة الوصول العشوائي الخاصة بها للتتبع ()'رمل []بشكل منفصل، ولكن هذه اللغة التي تحتوي على مكدس فقط لا يمكنها ذلك.
يمكن لآلة تورينج محاكاة أي آلة تورينج أخرى - يمكن لآلة تورينج، عند إعطائها "برنامجًا" مناسبًا، أخذ "برنامج" آلة تورينج أخرى ومحاكاته عند إدخال عشوائي.إذا كانت لديك لغة محظورة من تنفيذ مترجم بايثون، فلن تكون لغة تورينج كاملة.
أمثلة على لغات تورينج كاملة
إذا كانت لغتك تحتوي على ذاكرة وصول عشوائي لا نهائية، وتنفيذ مشروط، وبعض أشكال التنفيذ المتكرر، فمن المحتمل أن تكون لغة تورينج كاملة.هناك أنظمة أكثر غرابة لا يزال بإمكانها تحقيق كل ما تستطيع آلة تورينج تحقيقه، مما يجعلها تورينج كاملة أيضًا:
- حساب التفاضل والتكامل لامدا غير مكتوب
- لعبة كونواي للحياة
- قوالب سي++
- مقدمة
في الأساس، يعد اكتمال تورينج أحد المتطلبات الموجزة والتكرار غير المحدود.
ولا يحدها حتى الذاكرة.
فكرت في هذا بشكل مستقل، ولكن هنا بعض المناقشة من التأكيد. تعريفي لـ LSP يوفر المزيد من السياق.
الإجابات الأخرى هنا لا تحدد بشكل مباشر الجوهر الأساسي لاكتمال تورينج.
تعني Turing Complete أنها على الأقل بنفس قوة ملف آلة تورينج.وهذا يعني أن أي شيء يمكن حسابه بواسطة آلة تورينج يمكن حسابه بواسطة نظام تورينج الكامل.
لم يعثر أحد حتى الآن على نظام أقوى من آلة تورينج.لذا، في الوقت الحالي، فإن القول بأن النظام هو Turing Complete هو نفس القول بأن النظام قوي مثل أي نظام حاسوبي معروف (انظر أطروحة الكنيسة تورينج).
في أبسط العبارات، يمكن لنظام تورينج الكامل أن يحل أي مشكلة حسابية محتملة.
أحد المتطلبات الأساسية هو أن يكون حجم لوحة المسودة غير محدود، ومن الممكن إرجاعها للوصول إلى عمليات الكتابة السابقة على لوحة المسودة.
وبالتالي، من الناحية العملية، لا يوجد نظام مكتمل تورينج.
بدلاً من ذلك، تقترب بعض الأنظمة من اكتمال تورينج من خلال نمذجة الذاكرة غير المحدودة وإجراء أي حساب محتمل يمكن أن يتناسب مع ذاكرة النظام.
أعتقد أن أهمية مفهوم "Turing Complete" تكمن في القدرة على تحديد جهاز حاسوبي (وليس بالضرورة "كمبيوتر" ميكانيكي/كهربائي) يمكن تفكيك عملياته إلى تعليمات "بسيطة"، تتألف من تعليمات أبسط وأبسط. التعليمات التي يمكن للآلة العالمية تفسيرها ثم تنفيذها.
أوصي بشدة بكتاب تورينج المشروح
@ Mark أعتقد أن ما تشرحه هو مزيج بين وصف آلة تورينج العالمية وتورينج الكامل.
الشيء الذي يعد Turing Complete، بالمعنى العملي، سيكون عبارة عن آلة/عملية/حسابية يمكن كتابتها وتمثيلها كبرنامج، ليتم تنفيذها بواسطة آلة عالمية (كمبيوتر مكتبي).مع أنها لا تأخذ في الاعتبار الوقت أو التخزين كما ذكر آخرون.
ما أفهمه بكلمات بسيطة:
تورينج كاملة: لغة البرمجة/البرنامج الذي يمكنه القيام بالحسابات هو تورينج كامل.
على سبيل المثال :
هل يمكنك إضافة رقمين باستخدام Just لغة البرمجة.(الجواب هو"لا"، يجب عليك استخدام جافا سكريبت لإجراء عملية الإضافة.)، وبالتالي فإن HTML ليس Turing Complete.
لغات مثل Java وC++ وPython وJavascript وSolidity for Ethereum وما إلى ذلك هي Turing Complete لأنه يمكنك إجراء عمليات حسابية مثل إضافة رقمين باستخدام هذه اللغات.
أتمنى أن يساعدك هذا.
مثل قال وايلون فلين:
تعني Turing Complete أنها على الأقل بنفس قوة آلة Turing.
أعتقد أن هذا غير صحيح، فالنظام يكون تورينج مكتملًا إذا كان بنفس قوة آلة تورينج، أي.كل عملية حسابية تقوم بها الآلة يمكن إجراؤها بواسطة النظام، ولكن أيضًا كل عملية حسابية يقوم بها النظام يمكن إجراؤها بواسطة آلة تورينج.
في المصطلحات اللغوية العملية المألوفة لدى معظم المبرمجين، الطريقة المعتادة لاكتشاف اكتمال تورينج هي إذا كانت اللغة تسمح أو تسمح بمحاكاة عبارات while المتداخلة غير المحدودة (على عكس أسلوب باسكال للبيانات ذات الحدود العليا الثابتة).
هل يمكن لقاعدة بيانات علائقية إدخال خطوط الطول والعرض للأماكن والطرق، وحساب أقصر مسار بينها - لا.هذه إحدى المشكلات التي توضح أن SQL غير مكتمل من خلال Turing.
لكن لغة C++ يمكنها فعل ذلك، ويمكنها حل أي مشكلة.هكذا هو الحال.
